动态规划入门(论文)模板

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

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

3、的时候对它直接求解， 并把答案保存起来， 让以后再次遇到是直接引用答案， 不必从新求解，其实质是分治思想和解决冗余。例 1：求 AB 的最短路径图 1这是一个利用动态规划思想的经典问题， 通过直接观察图 1 我们可以枚举出 20 多条路径，并可以计算出其中最短的路径长度为 16用动态规划的思想来分析，我们可以把这个问题转换成下面这个模型阶段状态决策图 2阶段：根据问题的特点和需要， 将问题按时间或空间特征分解为若干相互联系的阶段。在本例中，我们根据空间特性将问题分成了 6 个阶段。状态： 各阶段的开始条件，本例中， A,B,C P这些节点都属于状态，表示从该点到 B的最短路径，在这里我们计做

4、S(i)，表示从第 i个节点（状态）到 B的最短路径决策：某阶段状态确定后，从该状态到下阶段某状态的选择。比如 S(A) ，它可以选择通过 C到达 B，也可以选择通过 D到达 B 。状态转移方程：系统由某阶段的一个状态转变到下一阶段的另一状态称状态转移，体现转移规律的方程称状态转移方程。在本例中，我们不难推出 S(A)=MINS(C)+4,S(D)+3,S(C)=MINS(E)+5,S(F)+3 S(B)=0，由此我们可以得出状态转移方程 (i)=MINS(j)+Vij(j 为与 i相邻接的节点， Vij 表示邻接节点 i， j之间的距离 )。一个动态规划模型应该满足以下几个性质：1.最优子结

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 的最优

6、路径，则根据最优化原理， 路线 W2 必是从 J 到 B 的最优路线。用反证法证明：假设有另一路径 W2 是 J 到 B 的最优路径，则 A 到 B 的路线取 W1 和 W2 比 W1 和 W2 更优，矛盾。从而证明 W2 必是 J 到 B 的最优路径 W2 。最优子结构性质是动态规划的基础， 任何问题，如果失去了最优子结构性质的支持，就不可能用动态规划方法计算。 根据最优子结构性质导出的动态规划状态转移方程是解决一切动态规划问题的基本方法。可以看出，图 2 的模型是满足最优子结构性质的。2子问题重叠性质在我们根据状态转移方程用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新的，而

7、且某些子问题会被重复计算多次，比如，在求 S（ C）时需要递归求出 S（F）的值，而在求 S（D）时也需要递归求出 S（F）的值，因此整个求解过程中 S（ F）的值会被求解两次，如果我们能把这多余的一次重复计算剔除，将可以最大程度的提高程序执行效率； 动态规划正是利用了这种子问题的重叠性质， 对每个子问题只计算一次， 然后将其结果保存在一个表格中， 当再次需要计算已经计算过的子问题时， 只是在表格中简单的查询一下结果， 从而获得较高的解题效率， 这个方法就是我们常说的 记忆化搜索 。因此， 如果我们把第一次求解出的 S（F）的值用一种数据结构保存下来，下次再用到 S（F）时，我们直接去查，这样

8、能使程序的时间和空间效率将会大大提高。下面通过对具体实例的分析， 帮助大家领会动态规划的这两个性质和动态规划的算法设计思想例：导弹拦截某国为了防御敌国的导弹袭击 , 发展出一种导弹拦截系统 . 但是这种导弹拦截系统有一个缺陷 : 虽然它的第一发炮弹能够到达任意的高度 , 但是以后每一发炮弹都不能高于前一发的高度 .某天 , 雷达捕捉到敌国的导弹来袭 .由于该系统还在试用阶段 , 所以只有一套系统 , 因此有可能不能拦截所有的导弹 .输入导弹依次飞来的高度 ( 雷达给出的高度数据是不大于 30000 的正整数 ), 计算这套系统最多能拦截多少导弹 ,并依次输出被拦截的导弹飞来时候的高度 .样例

9、:INPUT389 207 155 300 299 170 158 65OUTPUT6 ( 最多能拦截的导弹数 )389 300 299 170 158 65分析 : 因为只有一套导弹拦截系统 ,并且这套系统除了第一发炮弹能到达任意高度外 ,以后的每一发炮弹都不能高于前一发炮弹的高度 ; 所以 , 被拦截的导弹应该按飞来的高度组成一个非递增序列 .题目要求我们计算这套系统最多能拦截的导弹数 ,并依次输出被拦截导弹的高度 , 实际上就是要求我们在导弹依次飞来的高度序列中寻找一个最长非递增子序列 .解决思路：设X=x 1 ,x 2 ,2 ,y k 为问题的最优解,x n 为依次飞来的导弹序列( 即

10、 X 的最长非递增子序列 ), s, Y=y 1 ,y为问题的状态( 表示导弹拦截系统当前发送炮弹能够到达的最大高度, 初值为s=第一发炮弹能够到达任意的高度). 如果y 1 =x 1 ,即飞来的第一枚导弹被成功拦截. 那么 ,根据题意 每一发炮弹都不能高于前一发的高度, 问题的状态将由s=变成 sx 1 ( x 1为第一枚导弹的高度);在当前状态下,序列Y 1 =y 2 ,y k 也应该是序列X 1 =x 2 ,x n 的最长非递增子序列( 用反证法很容易证明 ). 也就是说 , 在当前状态 sx 1 下, 问题的最优解 Y 所包含的子问题 ( 序列 X 1 ) 的解 ( 序列 Y 1 )

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

12、 xi=minxiXn)D(i)=MaxD(j)+1 (ji且 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(

13、1) , D(2) , D(n) . 程序如下：int D(int i)int j,max=0;if(i=n)|(min(x,i,n)=xi)/min(x,i,n)返回数组 x 在下标 i n 之间的最小值return 1;elsefor(j=i+1;j=n;j+)if(xjmax)max=D(j)+1;return max;从这个程序的递归模型中可以看出，会有大量的子问题被重复计算 . 比如在调用递归函数计算 D(1) 的时候 , 可能需要先计算 D(5) 的值 ; 之后在分别调用递归函数计算 D(2) , D(3) , D(4) 的时候 ,都有可能需要先计算 D(5) 的值 .如此一来 ,

14、在整个问题的求解过程中 , D(5) 可能会被重复计算很多次 ,从而造成了冗余 ,降低了程序的效率 .其实 ,通过以上分析 , 我们已经知道 : D(n)=1 . 如果将 n 作为阶段对问题进行划分 ,根据问题的动态规划递归方程 , 我们可以采用自底向上的方法依次计算出D(n-1) , D(n- 2) , D(1) 的值 . 这样 ,每个 D(i) 的值只计算一次 ,并在计算的同时把计算结果保存下来 ,程序如下：void D()int i,j;for( i=1;i=1;i-)for(j=i+1;j=n;j+)if (x(j)dmax)dmax=d(i);xh=i;由此我们出了最大拦截数的第一枚

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

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

17、=n=30 ，1=m=30 ）。【输出】输出文件 ball.out 共一行，有一个整数，表示符合题意的方法数。【输入输出样例】ball.in3 3ball.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,0 。由于球只能传递给左右的两个同学， 也只能通过左右的两个同学传递给自己， 如

18、下图：F1,0向左传向右传F2,1Fn,1由此，我们分析出 F1,0 的解只与 F1,1 和 Fn,1 有关，而 F1,1 和 Fn,1 也是最优问题解，因此，该问题符合最优子结构性质。根据最优性原理我们可以得到以下状态转移方程：1(t=m， p=1)F(p,t)=0(t=m， p!=1)FRp,t+1+FLp,t+1 (1=p=n，0=tm)Rp ： p 右边同学的编号Lp ： p 左边同学的编号通过以上分析， 根据状态转移方程， 运用记忆化搜索策略， 采用自顶向下的过程可递归求出 F1,0 ，程序如下：#include#include#define maxn 31/最大人数，编号从1n#d

19、efine maxm 30/最大传球次数long fmaxnmaxm;/表示传了T 次球以后球在P 号手里，包括在剩下的M-T次传球中有多少种方法走到1long m,n;void find(long p,long t)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;int p1=p-1;if(p1=0)p1=n;find(p

20、1,t+1);/ 搜把球传给P 左边的同学的状态fpt+=fp1t+1;main()int i,j;/ 一开始所有状态都没到过for(i=0;imaxn;i+)for(j=0;jmaxm;j+)fij=-1;scanf(%d%d,&n,&m);find(1,0);printf(%ld,f10);代入数据测算例： input ：33数据模型如下：F1,0=2F2,1=1F3,1=1F1,2=0F3,2=1F1,2=0F2,2=1F3,3=0F2,3=0F1,3=1F2,3=0F1,3=1F3,3=0：可以从记忆数组中直接获取；：需搜索记忆的状态；由于采用了记忆化搜索， 处于不同位置的相同状态不会被多次搜索， 因此可以在 O(m n)的时间复杂度内完成任