算法设计及分析动态规划基本思想

1、动态规划算法的基本思想动态规划方法是处理分段过程最优化问题的一类及其有效的方法。在实际生活中，有一类问题的活动过程可以分成若干个阶段，而且在任一阶段后的行为依赖于该阶段的状态，与该阶段之前的过程是如何达到这种状态的方式无关。这类 问题的解决是多阶段的决策过程。20世纪50年代，贝尔曼（Richard Bellman） 等人提出了解决这类问题的“最优化原则”，从而创建了最优化问题的一种新的 算法动态规划算法。最优化原则指出，多阶段过程的最优决策序列应当具有性质：无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。这要求原问题的最优解包含了其子问题的

2、一个最优解（称为最优子结构性质）。动态规划算法采用最优原则来建立递归关系式（关于求最优值的），在求解问题时有必要验证该递归关系式是否保持最优原则。若不保持，则不可用动态规划算法。在得到最优值的递归式之后，需要执行回溯以构造最优解。在使用动态 规划算法自顶向下（Top-Down求解时，每次产生的子问题并不总是新问题，有 些子问题反复计算多次，动态规划算法正是利用了这种 子问题重叠性质。对每一 个问题只计算一次，而后将其解保存在一个表格中，当再次要解此子问题时，只 是简单地调用（用常数时间）一下已有的结果。通常，不同的子问题个数随着输 入问题的规模呈多项式增长，因此，动态规划算法通常只需要多项式时

3、间， 从而 获得较高的解题效率。最优子结构性质和子问题重叠性质 是采用动态规划算法的 两个基本要素。例1.多段图问题V1V3V566422sL745856的最小成本路径（也叫最短路径）。8求由S到t711V44993V2725设G=（V,E）是一个赋权有向图，其顶点集V被划分成k2个不相交的子集V: 10兰k，其中，V1和Vk分别只有一个顶点s（称为源）和一个顶点t（称为汇），下图 中所有的边（u,v）的始点和终点都在相邻的两个子集 V和V +1 中: u迂V，vV +1。多阶段图问题：对于每一条由S到t的路径，可以把它看成在k-2个阶段作出的某个决策序列的相应结果：第i步决策就是确定V+1中

4、哪个顶点在这条路径上。今假设s, V2, V3,，V k-1, t是一条由s到t的最短路径，再假定从源点s(初始状态)开始， 已经作出了到顶点V2的决策(初始决策)，则V2就是初始决策产生的状态。若将 V2看成是原问题的子问题的初始状态，这个子问题就是找一条由V2到t的最短路 径。事实上，路径V2, V 3,，V k-1, t 定是V2到t的一条最短路径。不然， 设 V2, q 3, ，q k-1, t 是一条由 V2至y t的比 V2, V 3, ，v k-1, t 更短的路径， 贝y S, V 2, q 3, ，q 空,t 是一条由 s至卩t的比 s, V ?, V ?, ，V 巴，t 更

5、短的 路径。与前面的假设矛盾。这说明多段图问题具有最优子结构性质。例2. 0/1背包问题有n件物品，第i件重量和价值分别是W和Pi, i=1,2,n。要将这n件物品的某些件装入容量为c的背包中，要求每件物品或整个装入或不装入，不 许分割出一部分装入。0/1背包问题就是要给出装包方法，使得装入背包的物品 的总价值最大。这个问题归结为数学规划问题：max 2 Pi Xi1s.t. Z：WiXicXi 0,1, i =1,2，n (6.1.1)10/1背包问题具有最优子结构性质。事实上，若yi,y2,，yn是最优解则 y2,yn将是0/1背包问题的子问题:s.t.(6.1.2)max E pixi2

6、 M2 WjXi 2 Pi Yi2并且使得p1Y1 + 壬 Pi yi21Ik由此不难算出P=C(n-1)，其中C表示Catalan数:C(n)计 2nn +1 (n 丿= Q(4n / n3/2)(6.1.7)也就是说，P(n)是随n指数增长的，所以，我们不能希望列举所有可能次序的连 乘积，从中找到具有最少数乘次数的连乘积算法。 事实上，矩阵连乘积问题具有 最优子结构性质，我们可以采用动态规划的方法，在多项式时间内找到最优的连 乘积次序。用Ai:j表示连乘积AA + 1“A。分析计算A1:n的一个最优次序。设这个 仁kv n,则完全加括号方式为，依此次序，我们先分别计算 A1:k和Ak+1:

7、n,然后将 A1:n。可见，A1:n的一个最优序所包含的矩阵计算子 的次序也一定是最优的。也就是说，矩阵连乘问题具有最计算次序在矩阵 A和A+1之间将矩阵链分开，(A1A A)( A+1 A)计算的结果相乘得到链 A1:k和 Ak+1: n优子结构性质。如上三个例子都具有最优子结构性质，这个性质决定了解决此类问题的基本 思路是：首先确定原问题的最优值和其子问题的最优值之间的递推关系(自上向 下)，然后自底向上递归地构造出最优解(自下向上)。最优子结构性质是最优化原理得以采用的先决条件。一般说来，分阶段选 择策略确定最优解的问题往往会形成一个决策序列。Bellman认为，利用最优化原理以及所获得

8、的递推关系式去求解最优决策序列，可以使枚举数量急剧下降。这里有一个问题值得注意：最优子结构性质提示我们使用最优化原则产生的算法 是递归算法，简单地使用递归算法可能会增加时间与空间开销。例如，用递归式直接计算矩阵连乘积A1:n的算法RecurMatrixChain的时间复杂度将是O(2n):程序6-1-1计算矩阵连乘的递归算法int RecurMatrixChain(int i, int j)if (i=j) retu rn 0;int u=RecurMatrixCha in (i, i)+RecurMatrixChai n(i+1,j)+pi-1* p i* pj;sij=i;for(i nt

9、 k=i+1; kj; k+)int t=RecurMatrixChai n(i,k)+RecurMatrixChai n(k+1,j)+p i-1* Pk* pj；if (t1 +(n 1) + Z T(k) T(n k) = n + T(k)，krn心可用数学归纳法直接证明：T(n)2n=Q(2n)，这显然不是我们所期望的。注意到，在用递归算法自上向下求解具有最优子结构的问题时，每次产生 的子问题并不总是新问题，有些问题被反复计算多次。如果对每一个问题只解一 次，而后将其解保存在一个表格中，当再次需要解此问题时，只是简单地用常数 时间查看一下结果。则可以节省大量的时间。在矩阵的连乘积问题中

10、，若用mij表示由第i个矩阵到第j个矩阵的连乘积所用的最少数乘次数，则计算+ n= G(n2)个。下面将会看到,m1 n时共有(n2)个子问题。这是因为，对于1n，不同的有序对(i,j)对应于不同的子问题，不同子问题最多只有i I2丿用动态规划解此问题时，可在多项式时间内完成。程序6-1-2求矩阵连乘最优次序的动态规划算法void MatrixChai n(int p, int n, i nt * *m, i nt * *s) for (i nt i=1; i=n; i+) mii=0;for (int r=2; rv=n;叶+)for (i nt i=1; iv=n-r+1; i+)int

11、j=i+r-1; r是跨度mij= mi+1j+p i-1* p i* pj; sij=i;for (i nt k=i+1; kj; k+)int t= mik+ mk+1j+pi-1* pk* pj; if (t mij) mij=t;sij=k; 算法Matrixchain的主要计算量取决于程序中对 r, i和k的三重循环，循 环体内的计算量为0(1)，三重循环的总次数是om3)，所以，算法的计算时间上 界为0(n3)。例子求以下6个矩阵连乘积最少数乘计算次数及所采用乘法次序。A :30汽35; A :35心5; A3 :15汽5; A :5勺0; A :10氷 20;傀：20汽 25口2

12、2 + m35 + P1P2P5 =0 + 2500 +35兀 15兀 20 = 13000m25 =min 佃23 +m45 + pjPsP5 = 2625 +1000 +35 5 20 = 71251口24 + m 55 + ppp 5 =4375 +0+ 31211375= 7125一般的计算mij以及sij的过程如下图所示:12345612345612i 3456、0 15750、7875 . 9375. 11875 15125 . 0. “2625 .4375 . .7125、10500 U、 750； 25005375.0、. 1000 35000、5000140123456333

13、033340333550si jmi j注意，上述算法只是明确给出了矩阵最优连乘次序所用的数乘次数 m1n，并未明确给出最优连乘次序，即完全加括号方法。但是以sij 为元素的2维数组却给出了足够的信息。事实上，sij=k 说明，计算连乘积Ai:j 的最佳方式应该在矩阵 A和 A+1之间断开，即最优加括号方式为 (Ai:k)(Ak+1:j)。下面的算法Traceback按算法MatrixChain 计算出的断点信息s指示的加括号方式输出计算 Ai:j的最优次序。程序6-1-3根据最优值算法构造最优解Void Traceback(i nt i, i nt j, i nt * * s)if (i=j

14、) return;Traceback(i, sij, s);Traceback(sij+1, j, s); sij;“,” j endl;cout “ Mult ip ly A ” i “, ”cout “and A” (sij +1) 总结上面解矩阵连乘积问题，我们可以归纳出使用动态规划算法的基本步骤：1 .分析最优解的结构在这一步中，应该确定要解决的问题应该是具有最小子结构性质，这是选择动态规划算法的基础。2. 建立递归关系第一步的结构分析已经为建立递归关系奠定了基础。这一步的主要任务是递归地例如在矩阵连乘定义最优值，并建立该问题与其子问题最优值之间的递归关系。 积问题中，递归关系为0i = j叫|门=(minmi k + mk +1 j +pi - 1* pk* pj icjI i在0/1背包问题中的递归关系是(gj(X)表示0/1背包问题Knap(j+1,n,X)的最 优值)gj(X) = maxigj*(X),gjMX WjG + Pj V(6.1.8)在多段图问题中的递归关系是COST(i,j)= min c( j,l)+COS