动态规划思想入门(论文)

1、动态规划思想入门陈喻2008年10月7日关键字：动态规划，最优子结构，记忆化搜索引言动态规划(dynamicprogramming)是运筹学的一个分支，是求解决策过程(decisionprocess)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistepdecisionprocess)的优化问题时，提出了著名的最优化原理(principleofoptimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法动态规划。1957年出版了他的名著DynamicProgramming，这是该领域的第一本著

2、作。动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。动态规划的基本思想动态规划是：将待求的问题分解成假设干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它直接求解，并把答案保存起来，让以后再次遇到是直

3、接引用答案，不必从新求解，其实质是分治思想和解决冗余。例1:求A>B的最短路径图1这是一个利用动态规划思想的经典问题，通过直接观察图1我们可以枚举出20多条路径，并可以计算出其中最短的路径长度为16用动态规划的思想来分析，我们可以把这个问题转换成下面这个模型阶段：根据问题的特点和需要，将问题按时间或空间特征分解为假设干相互联系的阶段。在本例中，我们根据空间特性将问题分成了6个阶段。状态：各阶段的开始条件，本例中，A,B,CP这些节点都属于状态，表示从该点到B的最短路径，在这里我们计做S(i),表示从第i个节点状态到B的最短路径决策：某阶段状态确定后，从该状态到下阶段某状态的选择。比方S(

4、A),它可以选择通过C到达B,也可以选择通过D到达B。状态转移方程：系统由某阶段的一个状态转变到下一阶段的另一状态称状态转移，表达转移规律的方程称状态转移方程。在本例中，我们不难推出S(A尸MINS(C)+4,S(D)+3,S(C尸MINS(E)+5,S(F)+3S(B)=0,由此我们可以得出状态转移方程S(i)=MINS(j)+Vij(j为与i相邻接的节点,Vij表示邻接节点i,j之间的距离)。一个动态规划模型应该满足以下几个性质:最优子结构可这样阐述：一个最优化策略具有这样的性质，不管过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的

5、子策略总是最优的。例如在图2的模型中，S(A)是A到B的最短路径(最优策略)，而它所依赖的S(C)和S(D)作为S(A)的子策略分别是C到B的最短路径和D到B的最短路径，也是最优的。因此根据最优子结构性质我们得出了上面的状态转移方程。证明：如图2设路线W1=(A,C),(C,F),(F,J)W2=(J,M),(M,O),(O,B)假设品&线W1和W2是A到B的最优路径，则根据最优化原理，路线W2必是从J到B的最优路线。用反证法证明：假设有另一路径W2'是J到B的最优路径，则A到B的路线取W1和W2'比W1和W2更优，矛盾。从而证明W2'必是J到B的最优路径W2。

6、最优子结构性质是动态规划的基础，任何问题，如果失去了最优子结构性质的支持，就不可能用动态规划方法计算。根据最优子结构性质导出的动态规划状态转移方程是解决一切动态规划问题的基本方法。可以看出，图2的模型是满足最优子结构性质的。2.子问题重叠性质在我们根据状态转移方程用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新的，而且某些子问题会被重复计算多次，比方，在求SC时需要递归求出SF的值，而在求SD时也需要递归求出SF的值，因此整个求解过程中SF的值会被求解两次，如果我们能把这多余的一次重复计算剔除，将可以最大程度的提高程序执行效率；动态规划正是利用了这种子问题的重叠性质，对每个子问题

7、只计算一次，然后将其结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单的查询一下结果，从而获得较高的解题效率，这个方法就是我们常说的记忆化搜索。因此，如果我们把第一次求解出的SF的值用一种数据结构保存下来，下次再用到SF时，我们直接去查，这样能使程序的时间和空间效率将会大大提高。下面通过对具体实例的分析，帮助大家领会动态规划的这两个性质和动态规划的算法设计思想例：导弹拦截某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度.某大，雷达捕捉到敌国的导弹来袭.由于该

8、系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹.输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数）,计算这套系统最多能拦截多少导弹，并依次输出被拦截的导弹飞来时候的高度.样例：INPUT38920715530029917015865OUTPUT6（最多能拦截的导弹数）38930029917015865分析：因为只有一套导弹拦截系统，并且这套系统除了第一发炮弹能到达任意高度外,以后的每一发炮弹都不能高于前一发炮弹的高度；所以,被拦截的导弹应该按飞来的高度组成一个非递增序列.题目要求我们计算这套系统最多能拦截的导弹数，并依次输出被拦截导弹的高度，实际上就是要求

9、我们在导弹依次飞来的高度序列中寻找一个最长非递增子序列.解决思路：设X=x1,x2,xn为依次飞来的导弹序列，Y=y1,y2,yk为问题的最优解（即X的最长非递增子序列）,s为问题的状态（表示导弹拦截系统当前发送炮弹能够到达的最大高度，初值为s=第一发炮弹能够到达任意的高度）.如果y1=x1,即飞来的第一枚导弹被成功拦截.那么，根据题意"每一发炮弹都不能高于前一发的高度"，问题的状态将由s=8变成s<x1（x1为第一枚导弹的高度）；在当前状态下，序列Y1=y2,yk也应该是序列X1=x2,xn的最长非递增子序列（用反证法很容易证明）.也就是说，在当前状态s<x1

10、下，问题的最优解Y所包含的子问题（序列X1）的解（序列Y1）也是最优的.这就是拦截导弹问题的最优子结构性质.根据最优子结构性质推出状态转移方程：设D(i)为第i枚导弹被拦截之后，这套系统最多还能拦截的导弹数(包含被拦截的第i枚).我们可以设想，当系统拦截了第k枚导弹xk，而xk又是序列X=xk,xn中的最小值，即第k枚导弹之后飞来的导弹高度都比它高，则有D(k)=1;当系统拦截了最后一枚导弹xn，那么，系统最多也只能拦截这一枚导弹了,即D(n)=1;其它情况下，也应该有D(i)>1.根据以上分析，可归纳出问题的动态规划递归方程为："1(i=n或者xi=minxiXn)D(i)=

11、<mMaxD(j)+1(j>i且j<=n且xj<=xi)假设系统最多能拦截的导弹数为dmax(即问题的最优值),则dmax(i为被系统拦截的第一枚导弹的顺序号)所以,要计算问题的最优值dmax,需要分别计算出D(1),D(2),D(n)的值,然后将它们进行比较，找出其中的最大值.即：dmax=maxD(i)(1<=i且i<=n)分析子问题重叠，解决冗余根据上面分析出来的递归方程，我们完全可以设计一个递归函数，采用自顶向下的方法计算D(i)的值.然后，对i从1到n分别调用这个递归函数，就可以计算出D(1),D(2),D(n).程序如下：intD(inti)in

12、tj,max=0;if(i=n)|(min(x,i,n)=xi)/min(x,i,n)返回数组x在下标in之间的最小值return1;else学习文档仅供参考for(j=i+1;j<=n;j+)if(xj<=xi)if(D(j)+1>max)max=D(j)+1;returnmax;从这个程序的递归模型中可以看出，会有大量的子问题被重复计算.比方在调用递归函数计算D(1)的时候,可能需要先计算D(5)的值;之后在分别调用递归函数计算D(2),D(3),D(4)的时候,都有可能需要先计算D(5)的值.如此一来,在整个问题的求解过程中,D(5)可能会被重复计算很多次,从而造成了冗

13、余,降低了程序的效率.其实,通过以上分析,我们已经知道:D(n)=1.如果将n作为阶段对问题进行划分,根据问题的动态规划递归方程,我们可以采用自底向上的方法依次计算出D(n-1),D(n-2),D(1)的值.这样，每个D(i)的值只计算一次，并在计算的同时把计算结果保存下来,程序如下：voidD()inti,j;for(i=1;i<=n;i+)d(i)=1for(i=n-1;i>=1;i-)for(j=i+1;j<=n;j+)if(x(j)<=x(i)&&d(i)=d(j)+1>dmax)dmax=d(i);xh=i;由此我们出了最大拦截数的第一枚

14、导弹的顺序号xh,即d(xh)为问题的解从而防止了有些子问题被重复计算的情况发生,提高了程序的效率.在实际应用中，许多问题的阶段划分并不明显，这时如果刻意地划分阶段反而麻烦。一般来说，只要该问题可以划分成规模更小的子问题，并且原问题的最优解中包含了子问题的最优解即满足最优子化原理，则可以考虑用动态规划解决，也就是分治算法的思想。例2：传球游戏NOIP2008普及组第三题【问题描述】上体育课的时候，小蛮的老师经常带着同学们一起做游戏。这次，老师带着同学们一起做传球游戏。游戏规则是这样的：n个同学站成一个圆圈，其中的一个同学手里拿着一个球，当老师吹哨子时开始传球，每个同学可以把球传给自己左右的两个

15、同学中的一个左右任意，当老师再次吹哨子时，传球停止，此时，拿着球没传出去的那个同学就是败者，要给大家表演一个节目。聪明的小蛮提出一个有趣的问题：有多少种不同的传球方法可以使得从小蛮手里开始传的球，传了m次以后，又回到小蛮手里。两种传球的方法被视作不同的方法，当且仅当这两种方法中，接到球的同学按接球顺序组成的序列是不同的。比方有3个同学1号、2号、3号，并假设小蛮为1号，球传了3次回到小蛮手里的方式有1->2->3->1和1->3->2->1，共2种。【输入】输入文件ball.in共一行，有两个用空格隔开的整数n，m3<=n<=30，1<=m

16、<=30。【输出】输出文件ball.out共一行，有一个整数，表示符合题意的方法数。【输入输出样例】学习文档 仅供参考ball.out2【限制】40%的数据满足：3<=n<=30,1<=m<=20100%的数据满足：3<=n<=30,1<=m<=30解决思路：给n个同学从1n编号，设状态Fp,t表示传了t次球后，球在p手中，在剩下的m-t次传球中共有多少种方案到达1,由于在问题的求解中，球是从1号开始传，并最后回到1号，显然我们所求的目标状态就是是F1,0o由于球只能传递给左右的两个同学，也只能通过左右的两个同学传递给自己，如以下图：学习文

17、档仅供参考由此，我们分析出F1,0的解只与F1,1和Fn,1有关，而F1,1和Fn,1也是最优问题解，因此，该问题符合最优子结构性质。根据最优性原理我们可以得到以下状态转移方程:1(t=m,p=1)F(P，t尸00(t=m,p!=1),0<=t<m)IFRp,t+1+FLp,t+1(1<=p<=nRp:p右边同学的编号Lp:p左边同学的编号通过以上分析，根据状态转移方程，运用记忆化搜索策略，采用自顶向下的过程可递归求出F1,0，程序如下：#include<stdio.h>#include<stdlib.h>#definemaxn31最大人数，编号

18、从1n#definemaxm30/最大传球次数longfmaxnmaxm;/表示传了T次球以后球在P号手里，包括在剩下的M-T次传球中有多少种方法走到1longm,n;voidfind(longp,longt)if(t=m)/传了M次球了if(p=1)/传到了1fpt=1;else/没传到1fpt=0;return;if(fpt!=-1)return;/如果这个状态搜到过了，没必要再搜fpt=0;/标记该状态被搜过了find(p%n+1,t+1);/搜把球传给P右边的同学的状态fpt+=fp%n+1t+1;intp1=p-1;if(p1=0)p1=n;find(p1,t+1);/搜把球传给P左边的同学的状态fpt+=fp1t+1;main()inti,j;/一开始所有状态都没到过for(i=0;i<maxn;i+)for(j=0;j<maxm;j+)fij=-1;scanf("%d%d",&n,&m);find(1,0);printf("%ld",f10);代入数据测算例：input:33数据模型如下：由于采用了记忆化搜索，处于不同位置的相同状态不会被多次搜索，因此可以在O(mxn)的时间复杂度内完成任务，同样防止了子问题被重复计算的情况。由此可知