当前位置:首页 >> 电脑基础知识 >>

动态规划入门(论文)


动态规划思想入门
作者:陈喻(2008 年 10 月 7 日)
关键字:动态规划,最优子结构,记忆化搜索

引言 动态规划 (dynamic programming) 是运筹学的一个分支,是求解决策过程 (decisionprocess) 最 优 化 的 数 学 方 法 。 20 世 纪 50 年 代 初 美 国 数 学 家 R.E.Bellman 等人在研究多阶段决策过程(multistep decision process)的优 化问题时,提出了著名的最优化原理(principle of optimality),把多阶段过程 转化为一系列单阶段问题,逐个求解,创立了解决这类过程优化问题的新方法 ——动态规划。1957 年出版了他的名著 Dynamic Programming,这是该领 域的第一本著作。 动态规划问世以来,在经济管理、生产调度、工程技术和最优控制等方面得 到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载 等问题,用动态规划方法比用其它方法求解更为方便。 虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题, 但是一些与 时间无关的静态规划(如线性规划、非线性规划),只要人为地引进时间因素,把 它视为多阶段决策过程,也可以用动态规划方法方便地求解。 动态规划的基本思想 动态规划是:将待求的问题分解成若干个相互联系的子问题,先求解子问题,然 后从这些子问题的解得到原问题的解;对于重复出现的子问题,只在第一次遇到 的时候对它直接求解,并把答案保存起来,让以后再次遇到是直接引用答案,不 必从新求解,其实质是分治思想和解决冗余。

例 1:求 A—>B 的最短路径

图1 这是一个利用动态规划思想的经典问题, 通过直接观察图 1 我们可以枚举出 20 多条路径,并可以计算出其中最短的路径长度为 16

用动态规划的思想来分析,我们可以把这个问题转换成下面这个模型

阶段

状态

决策

图2 阶段: 根据问题的特点和需要, 将问题按时间或空间特征分解为若干相互联系的 阶段。在本例中,我们根据空间特性将问题分成了 6 个阶段。 状态: 各阶段的开始条件,本例中,A,B,C……P这些节点都属于状态,表示从 该点到B的最短路径,在这里我们计做S(i),表示从第i个节点(状态)到B的最 短路径 决策:某阶段状态确定后,从该状态到下阶段某状态的选择。比如S(A),它可以 选择通过C到达B,也可以选择通过D到达B。 状态转移方程:系统由某阶段的一个状态转变到下一阶段的另一状态称状态转 移,体现转移规律的方程称状态转移方程。在本例中,我们不难推出 S(A)=MIN{S(C)+4,S(D)+3},S(C)=MIN{S(E)+5,S(F)+3}…………S(B)=0,由此我 们可以得出状态转移方程S(i)=MIN{S(j)+Vij}(j为与i相邻接的节点, Vij表示邻接

节点i,j之间的距离)。 一个动态规划模型应该满足以下几个性质: 1.最优子结构性质 最优子结构可这样阐述: 一个最优化策略具有这样的性质,不论过去状态和 决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。 简而言之,一个最优化策略的子策略总是最优的。例如在图 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。 最优子结构性质是动态规划的基础,任何问题,如果失去了最优子结构性质 的支持, 就不可能用动态规划方法计算。根据最优子结构性质导出的动态规划状 态转移方程是解决一切动态规划问题的基本方法。 可以看出,图 2 的模型是满足最优子结构性质的。 2.子问题重叠性质 在我们根据状态转移方程用递归算法自顶向下对问题进行求解时, 每次产生的子 问题并不总是新的,而且某些子问题会被重复计算多次,比如,在求S(C)时 需要递归求出S(F)的值,而在求S(D)时也需要递归求出S(F)的值,因此 整个求解过程中S(F)的值会被求解两次,如果我们能把这多余的一次重复计 算剔除, 将可以最大程度的提高程序执行效率; 动态规划正是利用了这种子问题 的重叠性质,对每个子问题只计算一次,然后将其结果保存在一个表格中,当再 次需要计算已经计算过的子问题时,只是在表格中简单的查询一下结果,从而获 得较高的解题效率,这个方法就是我们常说的记忆化搜索。因此,如果我们把第

一次求解出的S(F)的值用一种数据结构保存下来,下次再用到S(F)时,我 们直接去查,这样能使程序的时间和空间效率将会大大提高。。 下面通过对具体实例的分析, 帮助大家领会动态规划的这两个性质和动态规划的 算法设计思想 例:导弹拦截 某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系 统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹 都不能高于前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试 用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹. 输入导弹依次飞来的高度(雷达给出的高度数据是不大于 30000 的正整数),计 算这套系统最多能拦截多少导弹,并依次输出被拦截的导弹飞来时候的高度. 样例: INPUT 389 207 155 300 299 170 158 65 OUTPUT 6 (最多能拦截的导弹数) 389 300 299 170 158 65 分析: 因为只有一套导弹拦截系统,并且这套系统除了第一发炮弹能到达任意高 度外,以后的每一发炮弹都不能高于前一发炮弹的高度;所以,被拦截的导弹应该 按飞来的高度组成一个非递增序列.题目要求我们计算这套系统最多能拦截的导 弹数,并依次输出被拦截导弹的高度,实际上就是要求我们在导弹依次飞来的高 度序列中寻找一个最长非递增子序列.

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

根据最优子结构性质推出状态转移方程:设 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 或者 xi=min{xi……Xn}) D(i)= Max{D(j)+1} (j>i 且 j<=n 且 xj<=xi)

假设系统最多能拦截的导弹数为 dmax (即问题的最优值),则 dmax ( i 为被系统拦截的第一枚导弹的顺序号) 所以,要计算问题的最优值 dmax ,需要分别计算出 D(1) , D(2) ,…… D(n) 的 值,然后将它们进行比较,找出其中的最大值.即:dmax=max{D(i)}(1<=i 且 i<=n) 分析子问题重叠,解决冗余 根据上面分析出来的递归方程,我们完全可以设计一个递归函数,采用自顶向下 的方法计算 D(i) 的值.然后,对 i 从 1 到 n 分别调用这个递归函数,就可以计 算出 D(1) , D(2) ,…… D(n) .程序如下:
int D(int i) { int j,max=0; if((i==n)||(min(x,i,n)==x[i])) //min(x,i,n) 返回数组 x 在下标 i—n 之间的最小值 return 1; else {

for(j=i+1;j<=n;j++) if(x[j]<=x[i]) if(D(j)+1>max) max=D(j)+1; return max; } }

从这个程序的递归模型中可以看出,会有大量的子问题被重复计算.比如在调用 递归函数计算 D(1) 的时候,可能需要先计算 D(5) 的值;之后在分别调用递归 函数计算 D(2) , D(3) , D(4) 的时候,都有可能需要先计算 D(5) 的值.如此 一来,在整个问题的求解过程中, 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<=n;i++) d(i)=1 for(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; }

}

由此我们出了最大拦截数的第一枚导弹的顺序号 xh, 即 d(xh)为问题的解从而避 免了有些子问题被重复计算的情况发生,提高了程序的效率. 在实际应用中, 许多问题的阶段划分并不明显,这时如果刻意地划分阶段反而麻 烦。一般来说,只要该问题可以划分成规模更小的子问题,并且原问题的最优解 中包含了子问题的最优解 (即满足最优子化原理) , 则可以考虑用动态规划解决, 也就是分治算法的思想。 例 2:传球游戏(NOIP2008 普及组第三题) 【问题描述】 上体育课的时候,小蛮的老师经常带着同学们一起做游戏。这次,老师带着 同学们一起做传球游戏。 游戏规则是这样的:n 个同学站成一个圆圈,其中的一个同学手里拿着一个 球, 当老师吹哨子时开始传球, 每个同学可以把球传给自己左右的两个同学中的 一个(左右任意),当老师再次吹哨子时,传球停止,此时,拿着球没传出去的 那个同学就是败者,要给大家表演一个节目。 聪明的小蛮提出一个有趣的问题: 有多少种不同的传球方法可以使得从小蛮 手里开始传的球,传了 m 次以后,又回到小蛮手里。两种传球的方法被视作不 同的方法, 当且仅当这两种方法中,接到球的同学按接球顺序组成的序列是不同 的。比如有 3 个同学 1 号、2 号、3 号,并假设小蛮为 1 号,球传了 3 次回到小 蛮手里的方式有 1->2->3->1 和 1->3->2->1,共 2 种。 【输入】 输入文件 ball.in 共一行,有两个用空格隔开的整数 n,m(3<=n<=30, 1<=m<=30)。 【输出】 输出文件 ball.out 共一行,有一个整数,表示符合题意的方法数。 【输入输出样例】

ball.in 33 ball.out 2 【限制】 40%的数据满足:3<=n<=30,1<=m<=20 100%的数据满足:3<=n<=30,1<=m<=30 解决思路:给 n 个同学从 1—n 编号,设状态 F[p,t]表示传了 t 次球后,球在 p 手中,在剩下的 m-t 次传球中共有多少种方案到达 1,由于在问题的求解中,球 是从 1 号开始传,并最后回到 1 号,显然我们所求的目标状态就是是 F[1,0]。由 于球只能传递给左右的两个同学,也只能通过左右的两个同学传递给自己,如下 图:

F[1,0] 向左传 F[2,1] 向右传 F[n,1]

由此, 我们分析出 F[1,0]的解只与 F[1,1]和 F[n,1]有关, 而 F[1,1]和 F[n,1]也是最 优问题解,因此,该问题符合最优子结构性质。 根据最优性原理我们可以得到以下状态转移方程:
1 (t=m,p=1) F(p,t)= 0 (t=m,p!=1) F[R[p],t+1]+F[L[p],t+1] (1<=p<=n,0<=t<m) R[p]:p 右边同学的编号 L[p]:p 左边同学的编号

通过以上分析,根据状态转移方程,运用记忆化搜索策略,采用自顶向下的过程 可递归求出 F[1,0],程序如下:
#include<stdio.h> #include<stdlib.h> #define maxn 31//最大人数,编号从 1……n #define maxm 30//最大传球次数 long f[maxn][maxm];//表示传了 T 次球以后球在 P 号手里,包括在剩下的 M-T 次传球中有 多少种方法走到 1 long m,n; void find(long p,long t) { if(t==m)//传了 M 次球了 { if(p==1)//传到了 1 f[p][t]=1; else//没传到 1 f[p][t]=0; return; } if(f[p][t]!=-1) return;//如果这个状态搜到过了,没必要再搜 f[p][t]=0;//标记该状态被搜过了 find(p%n+1,t+1);//搜把球传给 P 右边的同学的状态 f[p][t]+=f[p%n+1][t+1]; int p1=p-1; if(p1==0)p1=n; find(p1,t+1);//搜把球传给 P 左边的同学的状态 f[p][t]+=f[p1][t+1]; } main() { int i,j; //一开始所有状态都没到过 for(i=0;i<maxn;i++) for(j=0;j<maxm;j++) f[i][j]=-1; scanf("%d%d",&n,&m); find(1,0);

printf("%ld",f[1][0]); }

代入数据测算 例:input:3 3 数据模型如下:

F[1,0]=2

F[2,1]=1

F[3,1]=1

F[1,2]=0

F[3,2]=1

F[1,2]=0

F[2,2]=1

F[3,3]=0

F[2,3]=0

F[1,3]=1

F[2,3]=0

F[1,3]=1

F[3,3]=0

:可以从记忆数组中直接获取; :需搜索记忆的状态; 由于采用了记忆化搜索, 处于不同位置的相同状态不会被多次搜索,因此可以在 O(m×n)的时间复杂度内完成任务,同样避免了子问题被重复计算的情况。 由此可知,动态规划法与分治法和贪心法类似,它们都是将问题实例归纳为 更小的、相似的子问题,并通过求解子问题产生一个全局最优解。 贪心法:当前选择可能要依赖已经作出的所有选择,但不依赖于有待于做出的选 择和子问题。因此贪心法自顶向下,一步一步地作出贪心选择; 分治法:各个子问题是独立的 (即不包含公共的子子问题),因此一旦递归地求 出各子问题的解后, 便可自下而上地将子问题的解合并成问题的解。 但不足的是, 如果各子问题是不独立的, 则分治法要做许多不必要的工作,重复地解公共的子 问题。

动态规划: 利用分治思想把问题划分成规模更小的子问题,并且原问题的最优解 中包含了子问题的最优解;动态规划允许这些子问题不独立,(亦即各子问题可 包含公共的子子问题)也允许其通过自身子问题的解作出选择,该方法对每一个 子问题只解一次,并将结果保存起来,避免每次碰到时都要重复计算,从而解决 解决冗余 因此, 动态规划法所针对的问题有一个显著的特征,即它所对应的子问题树中的 子问题呈现大量的重复。动态规划法的关键就在于,对于重复出现的子问题,只 在第一次遇到时加以求解,并把答案保存起来,让以后再遇到时直接引用,不 必重新求解。 总结: 任何思想方法都有一定的局限性, 超出了特定条件, 它就失去了作用。 同样, 动态规划也并不是万能的。适用动态规划的问题必须满足最优化子结构性质。 特点: 1. 以长远利益为目标的一些列决策,一般用来求解最优的问题解 2. 符合最优化原理,可归结为一个递推式 3. 也成为多阶段规划,特点体现在多阶段性


赞助商链接
相关文章:
动态规划01背包论文
动态规划01背包论文_军事/政治_人文社科_专业资料。基于动态规划法解决 0/1 背包问题摘要动态规划是通过将它们分解成更简单的子问题解决复杂问题的方法。它适用 于...
关于动态规划的相关论文
有关动态规划的一篇小论... 7页 免费 动态规划论文 22页 2下载券 运筹学之...中医护理学基础重点 执业医师实践技能考试模拟试题 66份文档 职场生存攻略 思维...
动态规划论文
不及格 讨论与结论部分 论文鉴定意见 成绩 评阅人 职称 专业 浅谈不同方法在...1 。动态 规划递归方程是动态规划的最优性原理的基础,即:最优策略的子策 略...
动态规划---2000方奇论文
动态规划---2000方奇论文_财务管理_经管营销_专业资料。计算机算法广东...最优化原理是动态规划基础,任何问题,如果失去了最优化原理的支持, 就不可能用...
动态规划超级论文
动态规划超级论文_城乡/园林规划_工程科技_专业资料。ACM初学者需要知道的 ...规划是本书介绍的五种算法设计方法中难度最大的一种,它建立在最优原则的基础...
ACM课程论文——详解动态规划
ACM课程论文——详解动态规划 - 本次课程论文,针对ACM比赛中的经典算法,动态规划,进行了详细的讲述,并以ZOJ和POJ上的经典题目为例,讲述了动态规划算法的应用。
基于连通性状态压缩的动态规划问题
2008年冬令营论文 基于连通性状态压缩的动态规划问题长沙市雅礼中学 陈丹琦 【摘要...在状态压缩的基础上,有一类问题的状态中必须要 记录若干个元素的连通情况,我们...
算法论文:旅行商问题的求解方法(动态规划法和贪心法)
算法论文:旅行商问题的求解方法(动态规划法和贪心法) - 旅行商问题的求解方法 摘要 旅行商问题(TSP 问题)时是指旅行家要旅行 n 个城市然后回到出发城市, 要求...
运筹学课程设计论文
运筹学课程设计论文 - 本课设选取问题为动态规划。... 运筹学课程设计论文_管理学_高等教育_教育专区。本课...程序设计基础中所学知识, 编写了动态规划逆序法的计算...
国家集训队1999论文集 来煜坤
国家集训队1999论文集 来煜坤 - 把握本质,灵活运用 把握本质,灵活运用——动态规划的深入探讨 动态规划的深入探讨 浙江省萧山中学 来煜坤 【关键字】 动态规划 ...
更多相关标签: