动态规划详解 第二章...

2008-12-10  太阳000
动态规划详解 第二章

通过上一章的学习,相信大家对动态规划已经有了一个初步的了解,如果您将上一章的推荐习题全部掌握,那么您可以开始这一章的学习内容了。
这一章,我们将讲解一些动态规划的设计技巧。
相信大家在做动态规划一类题目的时候,往往不容易看出来这道题目是动态规划。其实这并不是您的IQ低,几乎所有的初学者都会存在这样的问题,我同样也不例外,不过凭借我超人的天赋,终于总结出来如何看出来某道题是不是动态规划的终极方法:
做题做题在做题!在一年半的学习中,我深刻的体会到了:动态规划是做出来的!这个硬道理,没有题目数量的保证,学好动态规划是很困难的。
但是动态规划也并非是无章可循,下面就为大家介绍几种常见的类型:
1.极值问题
这类问题的显著特征就是让您求出最X值,并且往往具有最后子结构的性质,因为其模型变化丰富,并且和实际联系紧密,所以在动态规划类问题中占有很大的重量
2.总数问题
3.一类博弈问题
4.某些杂题
一般情况下,动态规划类的问题往往就这几种类型,因此当大家看到以上几种类型的时候,不妨向动态规划的方向作些思考。

学习动态规划的另一个难点就是状态的设计,可以说,只要有了状态,那么决策和阶段也就迎刃而解了。
一个好的状态,首先要把问题描述清楚,其次转移的时候应当尽量“简单”,这里的简单,主要指状态之间的“距离”,譬如A[I]=MAX(A[J]) J<=I就没有A[I]=A[I-1]好。
下面让我们看一道题目:
例:排队买票
问题描述:一场演唱会即将举行。现有N(O〈N〈=200〉个歌迷排队买票,一个人买一张,而售票处规定,一个人每次最多只能买两张票。假设第I位歌迷买一张票需要时间Ti(1〈=I〈=n〉,队伍中相邻的两位歌迷(第j个人和第j+1个人)可以由前一个人买两张票,也可由后一位买两张票,则另一位就可以不用排队了,则这两位歌迷买两张票的时间变为Rj,现给出N,Tj和Rj,求使每个人都买到票的最短时间和方法。
因为可以从前一个人买票,又可以从后一个人买票,似乎不符合无后效性的原则,没有办法用动态规划求解。
所以我们不妨采用加一维的策略:
设F(I,**)为到第i个人为止所需的最短时间.
设Ti为第I个人单独买票的时间。
设 Ri为第I个人买2张票的时间。
则:状态转移方程分5种情况:
F(I,仅买1张)=MIN{F(I-1,仅买1张),F(I-1,买2张代前一位),F(I-1,不买由前代)}+Ti
F(I,买2张代前一位)=MIN{F(I-2,仅买1张),F(I-2,买2张代前一位),F(I-2,不买由前代)}+Ri
F(I,买2张代后一位)=MIN{F(I-1,仅买1张),F(I-1,买2张代前一位),F(I-1,不买由前代)}+Ri
F(I,不买由前代)= F(I-1,买2张代后一位)
F(I,不买由后代)=MIN{ F(I-1,仅买1张),F(I-1,买2张代前一位),F(I-1,不买由前代)}
注:本题的状态还可以继续优化到3种,请大家自己思考。

从上面的例子我们可以看到,当遇到题目的状态无论如何也无法免除后效形时,可以采用加一维的方法来解决,有的时候甚至需要加两维甚至三维。

处理动态规划时还有几种技巧:
1.对于一些需要计算出权函数的题目,不妨把函数的计算放置到动态规划之外,同时还可以尝试对一些权函数进行合并,这类处理权函数的技巧还有很多,相信大家在做题的过程中都会遇到,就不再详细展开了
2.对于某些状态,不妨对约束条件加以宽松,往往会起到出其不意的效果。
3.可以采用循环数组技术,比较经典的应用就是上一章的数字三角形,因为只和上一层的状态有关,和其他的状态无关,所以不妨只保存上一层的结果,每次计算出新的结果后就把上一层的结果舍弃,这样会让空间复杂度大大降低,是非常有用的一种优化方法。
4.采用状态压缩技术,这个优化的应用较为复杂,变形很多,有兴趣的不妨在网上查找相关资料

<<<<<<<<<<<<<<<<<<<<TO BE CONTINUE >>>>>>>>>>>>>>>>>>>>>>>>

    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。如发现有害或侵权内容,请点击这里 或 拨打24小时举报电话:4000070609 与我们联系。

    猜你喜欢

    0条评论

    发表

    请遵守用户 评论公约

    类似文章
    喜欢该文的人也喜欢 更多