动态规划算法 算法设计

动态规划算法张珊1（安徽中医学院安徽省合肥市230031）摘 要：在信息学中，我们经常遇到求最优解的问题，这些问题的特点是，只需要求出最优解，而不要求 写出最优解的具体情况。为了解决此类问题，我们经常会遇到一种有效的算法一一动态规划。使得我们可 以在有限的时间内，求出问题的解，本文介绍一些动态规划的理论知识。关键词：动态规划最优化原理算法中图分类号：TP301.6 文献标识码：ADynamic programming algorithmZHANG Shan1(Anhui College of Traditional Chinese Medicine,Anhui Province ,Hefei 230031,China)Abstract： In information science, we often encounter the problem of the optimal solution, the nature of these problems is to simply request the optimal solution, without requiring to write the optimal solution specific circumstances. In order to solve such problems, we often encounter an effective algorithm - dynamic programming. Makes the solution that we can within a limited time, find the problem, this article describes the theory of dynamic programming knowledge.Key words： Dynamic Programming Principle of optimality Algorithm作者简介：张珊，女，安徽安庆人，安徽中医学院本科生，学号09713051,09级医软（1）班0引言动态规划是一种在数学和计算机科学 中使用的，用于求解包含重叠字问题的最优 化问题的方法。其基本思想是，将原问题分 解为相似的子问题，在求解的过程中通过子 问题的解求出原问题的解。动态规划的思想 是多种算法的基础，被广泛应用于计算机科 学和工程领域。比较著名的应用实例有：求 解最短路径问题，背包问题，项目管理，网 络流优化等。1正文动态规划算法与分治法类似，其基本思 想也是将待求解问题分解成若干个子问题。 但是经分解得到的子问题往往不是互相独 立的。不同子问题的数目常常只有多项式量 级。在用分治法求解时，有些子问题被重复 计算了许多次。动态规划在查找有很多重叠 字问题的情况的最优解时有效。它将问题重 新组合成子问题。为了避免多次解决这些子 问题，它们的结果都逐渐被计算并被保存， 从简单的问题直到整个问题都被解决。因 此，动态规划保存递归时的结果，因而不会 在解决同样的问题时花费时间。如果能够保 存已解决的子问题的答案，而在需要时再找 出已求得的答案，就可以避免大量重复计 算，从而得到多项式时间算法。找出最优解 的性质，并刻划其结构特征。以自底向上的 方式计算出最优值。根据计算最优值时得到 的信息，构造最优解。1.1最优子结构动态规划只能应用于有最优子结构的 问题。最优子结构的意思是局部最优解能决 定全局最优解（对有些问题这个要求并不能 完全满足，故有时需要引入一定的近似）。 简单地说，问题能够分解成子问题来解决。最优子结构性质。如果问题的最优解所 包含的子问题的解也是最优的，我们就称该 问题具有最优子结构性质（即满足最优化原 理）。最优子结构性质为动态规划算法解决 问题提供了重要线索。子问题重叠性质。子问题重叠性质是指 在用递归算法自顶向下对问题进行求解时， 每次产生的子问题并不总是新问题，有些子 问题会被重复计算多次。动态规划算法正是 利用了这种子问题的重叠性质，对每一个子 问题只计算一次，然后将其计算结果保存在 一个表格中，当再次需要计算已经计算过的 子问题时，只是在表格中简单地查看一下结 果，从而获得较高的效率。矩阵连乘计算次序问题的最优解包含 着其子问题的最优解。这种性质称为最优子 结构性质。在分析问题的最优子结构性质时， 所用的方法具有普遍性：首先假设由问题的 最优解导出的子问题的解不是最优的，然后 再设法说明在这个假设下可构造出比原问 题最优解更好的解，从而导致矛盾。利用问题的最优子结构性质，以自 底向上的方式递归地从子问题的最优解逐 步构造出整个问题的最优解。最优子结构是 问题能用动态规划算法求解的前提。同一个问题可以有多种方式刻划 它的最优子结构，有些表示方法的求解速度 更快（空间占用小，问题的维度低）重叠子 问题递归算法求解问题时，每次产生的子问 题并不总是新问题，有些子问题被反复计算 多次。这种性质称为子问题的重叠性质。动态规划算法，对每一个子问题只 解一次，而后将其解保存在一个表格中，当 再次需要解此子问题时，只是简单地用常数 时间查看一下结果。通常不同的子问题个数随问题的大小 呈多项式增长。因此用动态规划算法只需要 多项式时间，从而获得较高的解题效率。1.2备忘录备忘录方法备忘录方法的控制结 构与直接递归方法的控制结构相同，区别在 于备忘录方法为每个解过的子问题建立了 备忘录以备需要时查看，避免了相同子问题 的重复求解。由最长公共子序列问题的最优子 结构性质建立子问题最优值的递归关系。用 cij记录序列和的最长公共子序列的长 度。其中，Xi=x1,x2,，xi； Yj=y1,y2,yj。当 i=0或 j=0时，空序 列是Xi和Yj的最长公共子序列。故此时 Cij=0。其它情况下，由最优子结构性 质可建立递归关系如下：0i= 0,j= 0cij =di1U1+1i,jQ x = yi jmaxCij1,ci 1j i,j Q f.丰七 在算法Icslength和les中，可进一步将数 组b省去。事实上，数组元素cij的值 仅由 ci-1j-1 ci-1j和 cij-1 这3个数组元素的值所确定。对于给定的数 组元素cij，可以不借助于数组b而仅 借助于c本身在时间内确定cij的值是 由 ci-1j-1 ci-1j和 cij-1冲 哪一个值所确定的。如果只需要计算最长公共子序列 的长度，则算法的空间需求可大大减少。事 实上，在计算cij时，只用到数组c的 第i行和第i-1行。因此，用2行的数组空间 就可以计算出最长公共子序列的长度。进一 步的分析还可将空间需求减至 O（min（m,n）。在所给多边形中，从顶点i（1 WiWn）开始，长度为j（链中有j个顶点） 的顺时针链p（i，j）可表示为vi， opi+1，vi+jT。如果这条链的最后一次合并运算在opi+s 处发生（1 WsWj-1），则可在opi+s处将链 分割为2个子链p（i，s）和p（i+s，j-s）。设m1是对子链p（i，s）的任意一种合并方式 得到的值，而a和b分别是在所有可能的合 并中得到的最小值和最大值。m2是 p（i+s， j-s）的任意一种合并方式得到的值，而c和 d分别是在所有可能的合并中得到的最小值 和最大值。依此定义有aWm1Wb，cWm2Wd当 opi+s=+ 时，显然有 a+cWmWb+d(2) 当 opi+s=*时，有minac, ad, bc, bd WmWmaxac，ad, bc, bd(3) 换句话说，主链的最大值和最小值可由 子链的最大值和最小值得到。斐波那契数列(Fibonacci polynomial)计算斐波那契数列(Fibonacci polynomial)的一个最基础的算法是，直接按照定义计function fib(n)I if n = 0 or n = 1Ireturn 1I return fib(n 1) + fib(n 2)当n=5时，fib(5)的计算过程如下：1 fib(5)2 fib(4) + fib(3)3 (fib(3) + fib(2) + (fib(2) + fib(1)4 (fib(2) + fib(1) + (fib(1) + fib(0) + (fib(1) + fib(0) + fib(1)5 (fib(1) +fib(0) +fib(1) + (fib(1)+ fib(0) + (fib(1) +fib(0) +fib(1)由上面可以看出，这种算法对于相 似的子问题进行了重复的计算，因此不是一 种高效的算法。实际上，该算法的运算时间 是指数级增长的。改进的方法是，我们可 以通过保存已经算出的子问题的解来避免 重复计算：array map 0.n = 0 = 0, 1 = 1 fib( n )Iiif ( map m does not contain key n)mn := fib(r 1) + fib(nI 、I2)IIreturn mn卜-I将前n个已经算出的前n个数保存在数组 map中，这样在后面的计算中可以直接易用运算时间变为0 (n)1.3背包问题背包问题作为NP完全问题，暂时不存 在多项式时间算法。动态规划属于背包问题 求解最优解的可行方法之一。此外，求解背 包问题最优解还有搜索法等，近似解还有贪 心法等，分数背包问题有最优贪心解等。背 包问题具有最优子结构和重叠子问题。动态 规划一般用于求解背包问题中的整数背包 问题(即每种物品所选的个数必须是整数)。 解整数背包问题：设有n件物品，每件价 值记为Pi，每件体积记为Vi，用一个最大 容积为Vmax的背包，求装入物品的最大价 值。用一个数组fi,j表示取i件商品填 充一个容积为j的背包的最大价值，显然问 题的解就是fn,Vmaxfi-1,j j=Vi0 i=0 OR j=0对于特例01背包问题(即每件物品最多放1件，否则不放入)的问题，状态转移方程：fi,j =T- fi-1,j j=Vi0 i=0 OR j=0for i:=1 to n dofor j:=tot down to vi doFj:=max(fjfj-vi+pi);writeln(ftot)2结论理解动态规划算法的概念，掌握动态规 划算法的基本要素:最优子结构性质和重叠 子问题性质。前面的结果，从而避免了重复计算。算法的参考文献1算法设计与分析基础（第二版）（美）Anany Levitin著2算法设计技巧与分析沙特M.H.Alsuwaiyel吴伟昶方世昌译电子工业出版社3算法设计与分析第2版 王晓东著 清华大学出版社4微软新英汉双解计算机词典（美）Microsoft Corporation著 北京超品计算机有限责任公司译人民邮电出版社5计算机算法基础邹海明著 华中理工大学出版社6计算机算法设计与分析苏德富著 电子工业出版社7算法导论Thomas H.Cormen Charles E.Leiserson Ronald L.RivestClifford Stein著潘金贵顾铁成李成法等译机械工业出版8计算机算法设计与分析导论朱清新杨凡 钟黔川等著 人民邮电出版社