《动态规划新版.docx》由会员分享，可在线阅读，更多相关《动态规划新版.docx（55页珍藏版）》请在金锄头文库上搜索。
1、第6章 动态规划动态规划是我们要介绍的几种算法设计方法中难度最大的一种，它建立在最优原则的基础上。采用动态规划方法，可以高效地解决许多用贪婪算法或分而治之算法无法解决的问题。在介绍动态规划的原理之后，将分别考察动态规划方法在解决背包问题、图象压缩、矩阵乘法链、最短途径、无交叉子集等方面的应用。1算法思想和贪婪算法同样，在动态规划中，可将一个问题的解决方案视为一系列决策的结果。不同的是，在贪婪算法中，每采用一次贪婪准则便做出一个不可撤回的决策，而在动态规划中，还要考察每个最优决策序列中是否包含一个最优子序列。例6-1最短路经考察下图中的有向图。假设要寻找一条从源节点s=1到目的节点d=5的最短途
2、径，即选择此途径所通过的各个节点。第一步可选择节点2，3或4。假设选择了节点3，则此时所规定解的问题变成：选择一条从3到5的最短途径。假如3到5的途径不是最短的，则从1开始通过3和5的途径也不会是最短的。所以在最短途径问题中，假如在的第一次决策时到达了某个节点v，那么不管v是如何拟定的，此后选择从v到d的途径时，都必须采用最优策略。例6-20/1背包问题考察前面的0/1背包问题。如前所述，在该问题中需要决定x1 xn的值。假设按i=1，2，n的顺序来拟定xi的值。假如置x1=0，则问题转变为相对于其余物品（即物品2，3，n），背包容量仍为c的背包问题。若置x1=1，问题就变为关于最大背包容量为
3、c- w1的问题。现设rc，c-w1为剩余的背包容量。在第一次决策之后，剩下的问题便是考虑背包容量为r时的决策。不管x1是0或是1，x2，xn必须是第一次决策之后的一个最优方案，假如不是，则会有一个更好的方案y2，yn，因而x1，y2，yn是一个更好的方案。假设n=3,w=100,14,10,p=20,18,15,c=116。若设x1=1，则在本次决策之后，可用的背包容量为r=116-100=16。x2，x3=0,1符合容量限制的条件，所得值为15，但由于x2，x3=1，0同样符合容量条件且所得值为18，因此x2，x3=0，1并非最优策略。即x=1，0，1可改善为x=1，1，0。若设x1=0，
4、则对于剩下的两种物品而言，容量限制条件为116。总之，假如子问题的结果x2，x3不是剩余情况下的一个最优解，则x1，x2，x3也不会是总体的最优解。例6-3航费假设某航线价格表为：从亚特兰大到纽约或芝加哥，或从洛杉矶到亚特兰大的费用为$100；从芝加哥到纽约票价$20；而对于路经亚特兰大的旅客，从亚特兰大到芝加哥的费用仅为$20。从洛杉矶到纽约的航线涉及到对中转机场的选择。洛杉矶芝加哥亚特兰大纽约1001002010020假如问题状态的形式为（起点，终点），那么在选择从洛杉矶到亚特兰大后，问题的状态变为（亚特兰大，纽约）。从亚特兰大到纽约的最便宜航线是从亚特兰大直飞纽约，票价$100。而使用直
5、飞方式时，从洛杉矶到纽约的花费为$200。但是，从洛杉矶到纽约的最便宜航线为洛杉矶-亚特兰大-芝加哥-纽约，其总花费为$140（在解决局部最优途径亚特兰大到纽约过程中选择了最低花费的途径：亚特兰大-芝加哥-纽约）。假如用三维数组（tag，起点，终点）表达问题状态，其中tag为0表达转飞，tag为1表达其他情形，那么在到达亚特兰大后，状态的三维数组将变为（0，亚特兰大，纽约），它相应的最优途径是经由芝加哥的那条途径。当最优决策序列中包含最优决策子序列时，可建立动态规划递归方程通常是根据最优准则，得出动态规划计算的“递归”计算式。通常，这个递归式也是解决问题的关键，写出递归公式，然后用递归程序实现
6、，并消除反复计算在大多数情况下，求出递归方程是实际工作中的难点而消除反复计算则成为问题是否可以实际求解的关键（dynamic-programming recurrence equation），它可以帮助我们高效地解决问题。例6-40/1背包在例6-2的0/1背包问题中，最优决策序列由最优决策子序列组成。假设f(i,y)先把这个表达的地意义弄清楚?表达例6-2中剩余容量为y，剩余物品为i，i+1，n时的最优解的值，即：这个递归方程事实上将所有的情形所有考虑进去了，然后再从中找到一个最优解运用最优序列由最优子序列构成的结论，可得到f的递归式。f(1,c)是初始时背包问题的最优解。可通过递归或迭代来
7、求解f(1,c)。从f(n,*)开始迭式，先求出f(n,*)，然后递归计算f(i,*)(i=n-1，n-2，.，2)，最后得出f(1,c)。对于例6-2（w=100,14,10,p=20,18,15）可得：f(3,y)=0 0y10f(3,y)=15 y10f(2,y)=0 0y10f(2，y)=15 10y14f(2，y)=18 14y24 和f(2，y)=33 y24剩2、3两个物品的情况因此最优解：f(1,116)= maxf（2，116），f（2，116-w1）+p1= maxf（2，116），f（2，16）+20= max33，38 = 38。现在计算xi值，环节如下：若f(1,c)
8、=f(2,c)，则x1=0，否则x1=1。接下来需从剩余容量c-w1中寻求最优解，用f(2,c-w1)表达最优解。依此类推，可得到所有的xi(i=1n)值。在该例中，可得出f(2,116)=33f(1,116)，所以x1=1。接着运用返回值38-p1=18计算x2及x3，此时r=116-w1=16，又由f(2,16)=18，得f(3,16)=14f(2,16)，因此x2=1，此时r=16-w2=2，所以f(3,2)=0，即得x3=0。动态规划方法采用最优原则（principle of optimality）来建立用于计算最优解的递归式。所谓最优原则即不管前面的策略如何，此后的决策必须是基于当前
9、状态（由上一次决策产生）的最优决策。由于对于有些问题的某些递归式来说并不一定能保证最优原则，因此在求解问题时有必要对它进行验证。若不能保持最优原则，则不可应用动态规划方法。在得到最优解的递归式之后，需要执行回溯（traceback）以构造最优解。编写一个简朴的递归程序来求解动态规划递归方程是一件很诱人的事。然而，正如我们将在下文看到的，假如不努力地去避免反复计算，递归程序的复杂性将非常可观。假如在递归程序设计中解决了反复计算问题时，复杂性将急剧下降。动态规划递归方程也可用迭代方式来求解，这时很自然地避免了反复计算。事实上，这也是动态规划求解的两个基本方法：1、 消除反复的递归2、 采用迭代来代
10、替递归尽管迭代程序与避免反复计算的递归程序有相同的复杂性，但迭代程序不需要附加的递归栈空间，因此将比避免反复计算的递归程序更快。2应用2.1 0/1背包问题背包问题的递归方程可以用几种方法具体的软件实现，即前面的递归公式求解，还是一个比较复杂的问题求得。1）递归策略在例6-4中已建立了背包问题的动态规划递归方程，求解递归式（6-2）的一个很自然的方法便是使用程序6-1中的递归算法。该模块假设p、w和n为输入，且p为整型，F(1,c)返回f(1,c)值。程序6-1背包问题的递归函数实际程序中，w和p以及n需要“输入”到递归函数中消除反复计算，假如y是整数，则可以考虑用一个二维数组保存F(i,y)
11、，从而消除反复计算int F(int i,int y)/返回f(i,y).if(i=n) return (ywn)?0:pn;if(ywi) return F(i+1,y);elsereturn max(F(i+1,y),F(i+1,y-wi)+pi);程序6-1的时间复杂性为：t(n)=(2n)。在所有f(i,y)计算完毕后，再用下列程序计算xitemplatevoid Traceback(T *f,int w,int c,int n,int x)/计算xfor(int i=1;in;i+)if(fic=fi+1c) xi=0;else xi=1; c-=wi; xn=(fnc)?1:0;例
12、6-5设n=5，p=6,3,5,4,6，w=2,2,6,5,4且c=10,求f(1,10)。为了拟定f(1,10)，调用函数F(1,10)。递归调用的关系如图6-1的树型结构所示。每个节点用y值来标记。对于第j层的节点有i=j，因此根节点表达F(1,10)，而它有左孩子和右孩子，分别相应F(2,10)和F(2,8)。总共执行了28次递归调用。但我们注意到，其中也许具有反复前面工作的节点，如f(3,8)计算过两次，相同情况的尚有f(4,8)、f(4,6)、f(4,2)、f(5,8)、f(5,6)、f(5,3)、f(5,2)和f(5,1)。假如保存以前的计算结果，则可将节点数减至19，由于可以丢弃
13、图中的阴影节点。图6-1 递归调用树正如在例6-5中所看到的，程序6-1做了一些不必要的工作。为了避免f(i,y)的反复计算，必须定义一个用于保存已被计算出的f(i,y)值的表格L，该表格的元素是三元组(i,y,f(i,y)。在计算每一个f(i,y)之前，应检查表L中是否已包含一个三元组(i,y,*)，其中*表达任意值。假如已包含，则从该表中取出f(i,y)的值，否则，对f(i,y)进行计算并将计算所得的三元组(i,y,f(i,y)加入表L。L既可以用散列的形式存储，也可用二叉搜索树的形式存储。2）权为整数的迭代方法当权即 w为整数时，可设计一个相称简朴的算法（称为Knapsack算法，见程序
14、6-2）来求解f(1,c)。该算法基于例6-4所给出的策略，因此每个f(i,y)只计算一次。为简朴起见，程序6-2用二维数组f来保存各f的值。而回溯函数Traceback用于拟定由程序6-2所产生的xi值。函数Knapsack的复杂性为(nc)，而Traceback的复杂性为(n)。程序6-2 f和x的迭代计算下面程序中，要注意二维数组的真正实现，c语言中二维数组的传递需要特别注意注意下列三种表达方式的差异：T fN T *fT *fNtemplateT max( T x, T y )return( (xy)?x:y );/ 注意规定yMax用宏定义，大于ctemplatevoid Knapsack( T p,int w,int c,int n,T (*f)yMax )/对于所有i和y计算fiyint i, y;/初始化ffor( y=0;yyMax;y+)fny=0;for( y=wn;y1;i-)for( y=0;yyMax;y+)fiy=fi+1y;for( y=wi;y=c;y+)fiy=max(fi+1y,fi+
