APP下载

一种基于线段树的动态规划优化算法

2014-12-13邹玉金

软件工程师 2014年12期

摘  要:动态规划是解决多阶段决策最优化问题的一种思想方法,也是ACM程序设计竞赛中常用的算法。本文首先讨论了动态规划的基本思想和解题步骤。但基本动态规划对于数据规模很大的问题,在解题过程中还是存在效率和占用空间非常大的问题,本文巧妙利用线段树优化动态规划,提高对大规模数据处理的方法和技巧,在线段树基础上利用树状数组合理地解决了动态规划占用大量内存的问题。

关键词:动态规划;数据结构;线段树

中图分类号:TP301           文献标识码:A

1   引言(Introduction)

动态规划与分治法和贪心法类似,它们都是将问题分解为更小的、相似的子问题,但是动态规划又有自己的特点。能用贪心法解决的问题必须具备贪心的性质,所以有很大的局限性[1]。采用分治法解决问题时,由于子问题的数目往往是问题规模的指数函数,因此对时间的消耗太大。为了节约重复求相同子问题的时间,引入一个数组,不管它们是否对最终解有用,把所有子问题的解存于该数组中,这就是动态规划法所采用的基本方法。动态规划的实质是分治思想和解决冗余,动态规划的思想在于,如果各个子问题不是独立的,不同的子问题的个数只是多项式量级,如果能够保存已经解决的子问题的答案,而在需要的时候再找出已求得的答案,这样就可以避免大量的重复计算[2]。

2   线段树(Segment tree)

2.1   线段树定义

美国数学家R.E.Bellman等人创立的最优化原理(principle of optimality),可以很好的解决多阶段决策过程(multistep decision process)的优化问题[3]。……

登录APP查看全文