动态规划教材.docx

动态规划一、动态规划简介动态规划是运筹学的一个分支它是解决多阶段决策过程最优化问题的一种 方法1951年，美国数学家贝尔曼（R.Bellman）提出了解决这类问题的“最优 化原则”， 1957 年发表了他的名著《动态规划》，该书是动态规划方面的第一本 著作动态规划问世以来，在工农业生产、经济、军事、工程技术等许多方面都 得到了广泛的应用，取得了显著的效果动态规划运用于信息学竞赛是在 90 年代初期，它以独特的优点获得了出题 者的青睐此后，它就成为了信息学竞赛中必不可少的一个重要方法，几乎在所 有的国内和国际信息学竞赛中，都至少有一道动态规划的题目所以，掌握好动 态规划，是非常重要的动态规划是一种方法，是考虑问题的一种途径，而不是一种算法因此，它 不像深度优先和广度优先那样可以提供一套模式它必须对具体问题进行具体分 析需要丰富的想象力和创造力去建立模型求解二、 动态规划的几个基本概念想要掌握好动态规划，首先要明白几个概念：阶段、状态、决策、策略、指 标函数1．阶段：把所给问题的过程，恰当地分为若干个相互联系的阶段，以便能按一 定的次序去求解描述阶段的变量称为阶段变量2．状态：状态表示每个阶段开始所处的自然状况和客观条件，它描述了研究问 题过程中的状况，又称不可控因素。

3．决策：决策表示当过程处于某一阶段的某个状态时，可以作出不同的决定（或 选择），从而确定下一阶段的状态，这种决定称为决策，在最优控制中也称为 控制描述决策的变量，称为决策变量4．策略：由所有阶段的决策组成的决策函数序列称为全过程策略，简称策略 5．状态转移方程：状态转移方程是确定过程由一个状态到另一个状态的演变过 程6．指标函数：用来衡量所实现过程优劣的一种数量指标，称为指标函数指标 函数的最优值，称为最优值函数三、 确定动态规划的思路 1、采用动态规划来解决问题，必须符合两个重要的条件 1 ）“过去的历史只能通过当前状态去影响它未来的发展，当前的状态是对以往 历史的一个总结”，这种特性称为无后效性，是多阶段决策最优化问题的特征2）作为整个过程的最优策略具有这样的性质：即无论过去的状态和决策如何， 对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略简言之，一 个最优策略的子策略总是最优的这就是最优化原理2、如果碰到一个问题，能够满足以上两个条件的话，那么就可以去进一步考虑 如何去设计使用动态规划：（1）划分阶段把一个问题划分成为许多阶段来思考（2）设计合适的状态变量（用以递推的角度）（3）建立状态转移方程（递推公式）（4）寻找边界条件（已知的起始条件） 如果以上几个步骤都成功完成的话，我们就可以进行编程了。

四、动态规划解题的一些技巧由于动态规划并没有一个定式，这就需要去开拓我们创造力去构造并且使用 它以下，通过一些具体的竞赛实例谈谈使用动态规划过程中的一些技巧数塔问题：有形如图1.3-8 所示的数塔，从顶部出发，在每一结点可以选择向左走或是向右 走，一起走到底层，要求找出一条路径，使路径上的值最大图 1.3-8这道题如果用枚举法，在数塔层数稍大的情况下（如40），则需要列举出的路径 条数将是一个非常庞大的数目如果用贪心法又往往得不到最优解 在用动态规划考虑数塔问题时可以自顶向下的分析，自底向上的计算从顶点出 发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到 最大值，只要左右两道路径上的最大值求出来了才能作出决策同样的道理下一 层的走向又要取决于再下一层上的最大值是否已经求出才能决策这样一层一层 推下去，直到倒数第二层时就非常明了如数字2，只要选择它下面较大值的结 点 19 前进就可以了所以实际求解时，可从底层开始，层层递进，最后得到最 大值 实际求解时应掌握其编程的一般规律，通常需要哪几个关键数组来存储变化过程 这一点非常重要数塔问题的样例程序如下：var a:array[1..50,1..50,1..3] of longint;{第一维记原状态，第二维参与计算，第三维记录决策，0向左，1 向右。

浪费啊， 不如开三个一维，或三元组（指针处理麻烦，类似三角矩阵存储）} i,j,n:integer;beginwrite（ 'please input the number of rows:'）;readln（n）;for i:=1 to n dofor j:=1 to i do { 行元素数等于行数 }begin read（a[i,j,1]）; a[i,j,2]:=a[i,j,1];a[i,j,3]:=0end;{计算=================================}for i:=n-1 downto 1 do { 行选择（始于倒数第二行），阶段 }for j:=1 to i do { 列选择，状态 }if a[i+1,j,2]>a[i+1,j+1,2] then { 左强 }begin a[i,j,2]:=a[i,j,2]+a[i+1,j,2];{ 累 计 结 果 （ 父 +左）}a[i,j,3]:=0 {记录决策（选左）}endelse { 右强 }begin a[i,j,2]:=a[i,j,2]+a[i+1,j+1,2]; { 累计结果（ 父+右）}a[i,j,3]:=l{记录决策（选右）} end;{===输出==========} writeln（'max=',a[1,1,2]）; {最大值}j:=1;for i:=1 to n-1 dobeginwrite（a[i,j,1],'->'）;j:=j+a[i,j,3]end;writeln(a[n,j,1]) end.总结：此题是最为基础的动态规划题目，阶段、状态 的划分一目了然。

而决策的记录，充分体现了动态规划即“记忆化搜索”的本质最短路径问题下图给出了一个地图，地图中每个顶点代表一个城市，两个城市间的连线代表道 路，连线上的数值代表道路长度｛求城市 who 与城市 E｛找到目标城市｝｛初始化最短路径为最大｝现在，我们想从城市a到达城市E怎样走才能使得路径最短，最短路径的长度 是多少？设DiS [x]为城市x到城市E的最短路径长度（x表示任意一个城市）；map[i, j]表示i, j两个城市间的距离，若map[i, j]=0,则两个城市不通； 我们可以使用回溯法来计算 DiS[x]： varS：未访问的城市集合；functionsearch(who{x})：integer；的最短距离}beginif Who = E Then Search~OElse begin min^maxi nt；for i 取遍所有城市 Doif (map[Who, i]>0{有路}) and (i S{未访问}) then begin｛置访问标志｝｛累加城市 E 至城市 Who 的路径长度｝｛回溯后,恢复城市 i 未访问状态｝｛ 如果最短则记下 ｝｛返回最短路径长度｝｛计算最短路径长度｝S-S—[i]；j~map[Who, i]+ search(i)；S-S＋[i]；if jVmin Then min-j； end； {then}search-min；End； {else}End； {search}beginS—除E外的所有城市；Dis[a]-search(a)； 输出 Dis[a]； end．{main} 这个程序的效率如何呢？我们可以看到,每次除了已经访问过的城市外,其他城 市都要访问，所以时间复杂度为O (n!),这是一个“指数级”的算法。

那么， 还有没有效率更高的解题方法呢？首先，我们来观察上述算法在求bl到E的最短路径的时候，先求出从C2到E 的最短路径；而在求从b2刭E的最短路径的时候，又求了一遍从C2刭E的最短 路径也就是说，从C2到E的最短路径求了两遍同样可以发现，在求从Cl、 C2刭E的最短路径的过程中，从Dl到E的最短路径也被求了两遍而在整个程 序中，从Dl到E的最短路径被求了四遍，这是多么大的一个浪费啊！如果在求 解的过程中，同时将求得的最短路径的距离“记录在案”，以便将来随时调用， 则可以避免这种重复计算至此，一个新的思路产生了，即 由后往前依次推出每个Dis值，直到推出Dis「a」为止问题是，究竟什么是“由后往前”呢？所谓前后关系是指对于任意一对城市 i 和j来说，如果满足“或者城市i和城市j不连通或者dis[i]+map[i, j] $dis[j] ” 的条件，则定义为城市 i 在前、城市 j 在后因为如果城市 i 和城市 j 连通且 Dis[i]+map[i，j]VDis「j」，则说明城市j至城市E的最短路径长度应该比 Dis[j]更优可城市j位于城市i后不可能推出此情况，以至于影响最后的解 那么，我们应该如何划分先后次序呢？3、74-/Z 玲程0阶投1阶段2阶段3阶段4如上图所示，从城市 a 出发，按照与城市 a 的路径长度划分阶段。

阶段0包含的出发城市有｛a｝阶段1所含的城市有｛bl, b2｝阶段2包含的出发城市有｛Cl, C2, C3, C4｝阶段3包含的出发城市有｛Dl, D2, D3｝阶段4包含城市｛E｝这种划分可以明确每个城市的次序,因为阶段的划分具有如下性质⑴阶段i的取值只与阶段i+1有关，阶段i+1的取值只对阶段i的取值产生影响:⑵每个阶段的顺序是确定的，不可以调换任两个阶段的顺序；我们从阶段4的城市E出发，按照阶段的顺序倒推至阶段0的城市a在求解的 各个阶段，利用了 mSh段与k+｛Ld阶段之间a如下关系X, y) g G｝dis[k][x]=歹伙+1阶段的城市集 卩dis[4][E]=0k=4, 3„, 0,其中dis[k][x]指k阶段的城市X由此得出程序dis[E] -*-0；for k—3 down to 0 do ｛倒序枚举阶段｝for x 取遍 k 阶段的所有城市 dobegindis[x]—8； ｛初始化最短路径为最大｝for y 取遍 k+1 阶段的所有城市 do if dis[y]+map[x,y]

总结：此题是动态规划的基础题讲解也比较详细 在求解最短路经问题时，必须对图进行拓扑排 序，即划分明确的阶段、状态拦截导弹某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统但是这种拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹 都不能高于前一发的高度某天，雷达捕捉到敌国的导弹来袭，由于该系统还在 试用阶段所以只有一套系统，因此有可能不能拦截所有的导弹输入导弹依次飞来的高度(雷达给出的高度不大于 30000 的正整数)计算这 套系统最多能拦截多少导弹输入：导弹数n和n颗依次飞来的高度(1 WnW 1000)输出：一套系统最多拦截的导弹数best,并依次列出被拦截导弹的序号题解有的试题不仅要求输出最优解,而且还要求输出最优解的形成过程为此,我们 设置了一张记忆表,在按自下而上方式求解的过程中,将每一个子问题的最佳决 策保存起来,避免在输出方案时重复计算。