算法设计与分析 第六章 动态规划算法

1第六章动态规划算法§1.动态规划算法的基本思想动态规划方法是处理分段过程最优化问题的一类及其有效的方法。在实际生活中，有一类问题的活动过程可以分成若干个阶段，而且在任一阶段后的行为依赖于该阶段的状态，与该阶段之前的过程是如何达到这种状态的方式无关。这类问题的解决是多阶段的决策过程。在50年代，贝尔曼（RichardBellman）等人提出了解决这类问题的“最优化原则”，从而创建了最优化问题的一种新的算法动态规划算法。最优化原则指出，多阶段过程的最优决策序列应当具有性质：无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。这要求原问题的最优解包含了其子问题的一个最优解（称为最优子结构性质）。动态规划算法采用最优原则来建立递归关系式（关于求最优值的），在求解问题时有必要验证该递归关系式是否保持最优原则。若不保持，则不可用动态规划算法。在得到最优值的递归式之后，需要执行回溯以构造最优解。在使用动态规划算法自顶向下（Top-Down）求解时，每次产生的子问题并不总是新问题，有些子问题反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个问题只计算一次，而后将其解保存在一个表格中，当再次要解此子问题时，只是简单地调用（用常数时间）一下已有的结果。通常，不同的子问题个数随着输入问题的规模呈多项式增长，因此，动态规划算法通常只需要多项式时间，从而获得较高的解题效率。最优子结构性质和子问题重叠性质是采用动态规划算法的两个基本要素。例1．多段图问题设G=(V,E)是一个赋权有向图，其顶点集V被划分成k2个不相交的子集Vi:1ik，其中，V1和Vk分别只有一个顶点s(称为源)和一个顶点t(称为汇)，下图中所有的边(u,v)的始点和终点都在相邻的两个子集Vi和Vi＋1中：uVi，vVi＋1。图6-1-1一个5段图V1V2V3V4V51ts37292246117811345265541854277597161574532678910111212多阶段图问题：求由s到t的最小成本路径（也叫最短路径）。对于每一条由s到t的路径，可以把它看成在k-2个阶段作出的某个决策序列的相应结果：第i步决策就是确定Vi+1中哪个顶点在这条路径上。今假设s,v2,v3,…,vk-1,t是一条由s到t的最短路径，再假定从源点s(初始状态)开始，已经作出了到顶点v2的决策(初始决策)，则v2就是初始决策产生的状态。若将v2看成是原问题的子问题的初始状态，这个子问题就是找一条由v2到t的最短路径。事实上，路径v2,v3,…,vk-1,t一定是v2到t的一条最短路径。不然，设v2,q3,…,qk-1,t是一条由v2到t的比v2,v3,…,vk-1,t更短的路径，则s,v2,q3,…,qk-1,t是一条由s到t的比s,v2,v3,…,vk-1,t更短的路径。与前面的假设矛盾。这说明多段图问题具有最优子结构性质。例2．0/1背包问题有n件物品，第i件重量和价值分别是wi和pi,i=1,2,…,n。要将这n件物品的一部分装入容量为c的背包中，要求每件物品或整个装入或不装入，不许分割出一部分装入。0/1背包问题就是要给出装包方法，使得装入背包的物品的总价值最大。这个问题归结为数学规划问题：niiixp1maxs.t.nixcxwiniii,,2,1},1,0{,1(6.1.1)0/1背包问题具有最优子结构性质。事实上，若nyyy,,,21是最优解，则nyy,,2将是0/1背包问题的子问题：niiixp2maxs.t.nixwycxwiniii,,2},1,0{,112(6.1.2)最优解。因为，若nyy',,'2是子问题(6.1.2)的最优解，且使得niiiyp2'niiiyp2(6.1.3)则nyyy',,',21将是原问题(6.1.1)的可行解，并且使得niiiypyp211'niiiyp1(6.1.4)这与nyyy,,,21是最优解相悖。例3.矩阵连乘问题给定n个数字矩阵A1，A2，…，An，其中Ai与Ai+1是可乘的，i=1,2,…,n-1.求矩阵连乘A1A2An的加括号方法，使得所用的数乘次数最少。3考察两个矩阵相成的情形：C=AB。如果矩阵A，B分别是p×r和r×q矩阵，则它们的乘积C将是p×q矩阵，其(i,j)元素为rkkjikijbac1(6.1.5)i=1,…,p,j=1,…,q,因而AB所用的数乘次数是prq。如果有至少3个以上的矩阵连乘，则涉及到乘积次序问题，即加括号方法。例如3个矩阵连乘的加括号方法有两种：((A1A2)A3)和(A1(A2A3))。设A1，A2，A3分别是p0×p1，p1×p2，p2×p3矩阵，则以上两种乘法次序所用的数乘次数分别为：p0p1p2+p0p2p3和p0p1p3+p1p2p3。如果p0=10,p1=100,p2=5,p3=50,则两种乘法所用的数乘次数分别为：7500和750000。可见，由于加括号的方法不同，使得连乘所用的数乘次数有很大差别。对于n个矩阵的连乘积，令P(n)记连乘积的完全加括号数，则有如下递归关系111)()(11)(nknknPkPnnP(6.1.6)由此不难算出P=C(n-1)，其中C表示Catalan数：)/4(211)(2/3nnnnnCn(6.1.7)也就是说，P(n)是随n指数增长的，所以，我们不能希望列举所有可能次序的连乘积，从中找到具有最少数乘次数的连乘积算法。事实上，矩阵连乘积问题具有最优子结构性质，我们可以采用动态规划的方法，在多项式时间内找到最优的连乘积次序。用A[i:j]表示连乘积AiAi＋1Aj。分析计算A[1:n]的一个最优次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链分开，1kn，则完全加括号方式为((A1A2Ak)(Ak＋1An))，依此次序，我们先分别计算A[1:k]和A[k+1:n]，然后将计算的结果相乘得到A[1:n]。可见，A[1:n]的一个最优序所包含的矩阵计算子链A[1:k]和A[k+1:n]的次序也一定是最优的。也就是说，矩阵连乘问题具有最优子结构性质。如上三个例子都具有最优子结构性质，这个性质决定了解决此类问题的基本思路是：首先确定原问题的最优值和其子问题的最优值之间的递推关系（自上向下），然后自底向上递归地构造出最优解（自下向上）。最优子结构性质是最优化原理得以采用的先决条件。一般说来，分阶段选择策略确定最优解的问题往往会形成一个决策序列。Bellman认为，利用最优化原理以及所获得的递推关系式去求解最优决策序列，可以使枚举数量急剧下降。4这里有一个问题值得注意：最优子结构性质提示我们使用最优化原则产生的算法是递归算法，简单地使用递归算法可能会增加时间与空间开销。例如，用递归式直接计算矩阵连乘积A[1:n]的算法RecurMatrixChain的时间复杂度将是)2(n：程序6-1-1计算矩阵连乘的递归算法intRecurMatrixChain(inti,intj){if(i==j)return0;intu=RecurMatrixChain(i,i)+RecurMatrixChain(i+1,j)+p[i-1]*p[i]*p[j];s[i][j]=i;for(intk=i+1;kj;k++){intt=RecurMatrixChain(i,k)+RecurMatrixChain(k+1,j)+p[i-1]*p[k]*p[j];if(tu){u=t;s[i][j]=k;}}returnu;}如果用T(n)表示该算法的计算A[1:n]的时间，则有如下递归关系式：111)1)()((11)1()(nknknTkTnOnT当1n时111111)(2)()()1(1)(nknknkkTnknTkTnnT－，可用数学归纳法直接证明：)2(2)(1nnnT，这显然不是我们所期望的。注意到，在用递归算法自上向下求解具有最优子结构的问题时，每次产生的子问题并不总是新问题，有些问题被反复计算多次。如果对每一个问题只解一次，而后将其解保存在一个表格中，当再次需要解此问题时，只是简单地用常数时间查看一下结果，则可以节省大量的时间。在矩阵的连乘积问题中，若用5m[i][j]表示由第i个矩阵到第j个矩阵的连乘积所用的最少数乘次数，则计算m[1][n]时共有)(2n个子问题。这是因为，对于nji1，不同的有序对(i,j)对应于不同的子问题，不同子问题最多只有)(22nnn个。下面将会看到，用动态规划解此问题时，可在多项式时间内完成。程序6-1-2求矩阵连乘最优次序的动态规划算法voidMatrixChain(intp,intn,int**m,int**s){for(inti=1;i=n;i++)m[i][i]=0;for(intr=2;r=n;r++)for(inti=1;i=n-r+1;i++){intj=i+r-1;\\r是跨度m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];s[i][j]=i;for(intk=i+1;kj;k++){intt=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];if(tm[i][j]){m[i][j]=t;s[i][j]=k;}}}}算法MatrixChain的主要计算量取决于程序中对r,i和k的三重循环，循环体内的计算量为O(1)，三重循环的总次数是O(n3)，所以，算法的计算时间上界为O(n3)。例子求以下6个矩阵连乘积最少数乘计算次数及所采用乘法次序。2520:;2010:;105:;515:;1535:;3530:654321AAAAAA71251137520103504375]5][5[]4][2[71252053510002625]5][4[]3][2[1300020153525000]5][3[]2][2[min]5][2[541531521pppmmpppmmpppmmm6一般的计算]][[jim以及]][[jis的过程如下图所示：]][[jim]][[jis注意，上述算法只是明确给出了矩阵最优连乘次序所用的数乘次数m[1][n]，并未明确给出最优连乘次序，即完全加括号方法。但是以s[i][j]为元素的2维数组却给出了足够的信息。事实上，s[i][j]=k说明，计算连乘积A[i:j]的最佳方式应该在矩阵Ak和Ak+1之间断开，即最优加括号方式为(A[i:k])(A[k+1:j])。下面的算法Traceback按算法MatrixChain计算出的断点信息s指示的加括号方式输出计算A[i:j]的最优次序。程序6-1-3根据最优值算法构造最优解VoidTraceback(inti,intj,int**s){if(i==j)return;Traceback(i,s[i][j],s);Traceback(s[i][j]+1,j,s);cout“MultiplyA”i“,”s[i][j];cout“andA”(s[i][j]+1)“,”jendl;}总结上面解矩阵连乘积问题，我们可以归纳出使用动态规划算法的基本步骤：1．分析最优解的结构在这一步中，应该确定要解决的问题应该是具有最小子结构性质，这是选择动态规划算法的基础。2.建立递归关系第一步的结构分析已经为建立递归关系奠定了基础。这一步的主要任务是递归地123456015750787593751187515125026254375712510500075025005375010003500050000123456ij123456011333023330333045050123456ij