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

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

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

3、规划算法通常只需要多项式时间，从而 获得较高的解题效率。最优子结构性质和子问题重叠性质 是采用动态规划算法的 两个基本要素。 例1 多段图问题 设G=（V,E）是一个赋权有向图，其顶点集V被划分成k2个不相交的子集V: 1_k，其中，M和Vk分别只有一个顶点s（称为源）和一个顶点t（称为汇），下图 中所有的边（u,v）的始点和终点都在相邻的两个子集 V和V +1 中: u V，v V +1。 s 4 2 4 6 7 9 6 9 9 4 4 2 5 3 6 2 5 3 7 1 10 7 18 1 12 11 4 7 5 8 2 1 5 5 1 6 5 8 多阶段图问题：求由S到t的最小成本路径（

4、也叫最短路径）。 对于每一条由s到t的路径，可以把它看成在k-2个阶段作出的某个决策序列的相应结果：第i步决策就是确定V+1中哪个顶点在这条路径上。今假设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-i, t 是一条由 V2至卩t的比 V2, v 3, ，v k-i, t

5、更短的路径， 贝U s, V 2, q 3, ，q 巴 _是一条由 s至U t的比 s, V 2, v 3, ，v , t 更短的 路径。与前面的假设矛盾。这说明多段图问题具有最优子结构性质。 例2. 0/1背包问题 有n件物品，第i件重量和价值分别是w和pi, i=1,2,n。要将这n 件物品的某些件装入容量为c的背包中，要求每件物品或整个装入或不装入，不 许分割出一部分装入。0/1背包问题就是要给出装包方法，使得装入背包的物品 的总价值最大。这个问题归结为数学规划问题： max 二 Pi Xi i丄印 s.t. vWjXi EC, Xi 0,1, i =1,2, ,n (6.1.1) i岂

6、岂 0/1背包问题具有最优子结构性质。事实上，若2,yn是最优解， 则%, ,yn将是0/1背包问题的子问题： max pixi 2 勺切 s.t.WjXi 乞 c yw , Xi 0,1, i = 2，n 2岂勺 (6.1.2) 最优解。因为，若y；,，yn是子问题(6.1.2)的最优解，且使得 Piyi Pi yi 2 ln2 岂 m (6.1.3) 则,丫2,，yn将是原问题(6.1.1)的可行解，并且使得 P1、Piyi、Piyi(6.1.4) 2査至1 这与肆2,yn是最优解相悖。 例3.矩阵连乘问题 给定n个数字矩阵A，A,，An，其中A与A+1是可乘的，i=1,2，,n-1. 求

7、矩阵连乘AAA的加括号方法，使得所用的数乘次数最少。 考察两个矩阵相成的情形：C=AB如果矩阵A, B分别是px r和r x q矩阵, 则它们的乘积C将是px q矩阵，其(i, j) 元素为 r Cij 八 aik bkj(6.1.5) i=1,p, j=1,q,因而AB所用的数乘次数是prq。如果有至少3个以上的 矩阵连乘，贝U涉及到乘积次序问题，即加括号方法。例如3个矩阵连乘的加括号 方法有两种：(AiA)A3)和(Ai(AA)。设 A, A, A 分别是 poX pi, pi x p2, p2X P3矩阵，则以上两种乘法次序所用的数乘次数分别为：卩0卩22+5邮3和PoPlP3+PlP2

8、P3。 如果po=io, p 1=100, p 2=5, p 3=50,则两种乘法所用的数乘次数分别为：7500和 750000。可见，由于加括号的方法不同，使得连乘所用的数乘次数有很大差别。 对于n个矩阵的连乘积，令P(n)记连乘积的完全加括号数，则有如下递归关系 彳n =1 P(n )1、 彳(6.1.6) Z P(k)P(n -k) n1/ k A 由此不难算出P=C(n-1)，其中C表示Catalan数： C(门)=丄 2nLo(4n/n3/2)(6.1.7) n +Un 丿 也就是说，P(n)是随n指数增长的，所以，我们不能希望列举所有可能次序的连 乘积，从中找到具有最少数乘次数的连

9、乘积算法。 事实上，矩阵连乘积问题具有 最优子结构性质，我们可以采用动态规划的方法，在多项式时间内找到最优的连 乘积次序。 用Ai:j表示连乘积AA +1A。分析计算A1:n的一个最优次序。设这个 计算次序在矩阵 A和A+1之间将矩阵链分开，1_kn,则完全加括号方式为 (A1A2 A)( A+1 A)，依此次序，我们先分别计算 A1:k和Ak+1:n,然后将 计算的结果相乘得到 A1:n。可见，A1:n的一个最优序所包含的矩阵计算子 链A1:k和Ak+1:n的次序也一定是最优的。也就是说，矩阵连乘问题具有最 优子结构性质。 如上三个例子都具有最优子结构性质，这个性质决定了解决此类问题的基本

10、思路是： 首先确定原问题的最优值和其子问题的最优值之间的递推关系(自上向 下)，然后自底向上递归地构造出最优解(自下向上)。 最优子结构性质是最优化原理得以采用的先决条件。一般说来，分阶段选 择策略确定最优解的问题往往会形成一个决策序列。Bellman认为，利用最优化 原理以及所获得的递推关系式去求解最优决策序列，可以使枚举数量急剧下降。 这里有一个问题值得注意：最优子结构性质提示我们使用最优化原则产生的算法 是递归算法，简单地使用递归算法可能会增加时间与空间开销。例如，用递归式 直接计算矩阵连乘积A1:n的算法RecurMatrixChain 的时间复杂度将是 “(2n): 程序6-1-1计

11、算矩阵连乘的递归算法 int RecurMatrixChai n(int i, i nt j) if (i=j) retur n 0; int u=RecurMatrixCha in (i, i) +RecurMatrixChai n(i+1,j) +pi-1*pi*pj； sij=i; for(int k=i+1; kj; k+) int t=RecurMatrixChai n(i,k) +RecurMatrixChai n(k+1,j) +pi-1*pk*pj; if (tu) u=t; sij=k; return u; 如果用T(n)表示该算法的计算A1:n的时间，则有如下递归关系式：

12、O(1) T(n)纠 I n -4 1 k 1 仃(k) T(n - k) 1) nVnnV T(n) _1 (n -1)二 T(k)二 T(n k)二 n 2 T(k), kmk=ikm 可用数学归纳法直接证明： T(n) -2n4 =-J(2n)，这显然不是我们所期望的。 注意到，在用递归算法自上向下求解具有最优子结构的问题时，每次产生 的子问题并不总是新问题，有些问题被反复计算多次。如果对每一个问题只解一 次，而后将其解保存在一个表格中，当再次需要解此问题时，只是简单地用常数 时间查看一下结果。则可以节省大量的时间。在矩阵的连乘积问题中，若用mij表示由第i个矩阵到第j个矩阵的连乘积所用

13、的最少数乘次数，则计算 m1n时共有a(n2)个子问题。这是因为，对于1却乞j乞n，不同的有序对(i, j)对应于不同的子问题，不同子问题最多只有n +n= G(n2)个。下面将会看到, 丿 用动态规划解此问题时，可在多项式时间内完成。 程序6-1-2求矩阵连乘最优次序的动态规划算法 void MatrixCha in (i nt p, int n, int * *m, int * *s) for (i nt i=1; i=n; i+) mii=0; for (int r=2; r=n; r+) for (i nt i=1; i=n-r+1; i+) int j=i+r-1; r是跨度 mij

14、= mi+1j+pi-1*pi*pj; sij=i; for (int 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)，三重循环的总次数是0(n)，所以，算法的计算时间上 界为O(n3)。 例子求以下6个矩阵连乘积最少数乘计算次数及所采用乘法次序。 A :30 35;A2:35 15;A3:15 5;几：5 10;乓：10 20; Ae : 20 25 m(22 m35 p1p2p0 2500 3

15、5 15 20 =13000 m25 =min m23 +m4 5 + p1 p3p5 = 2625 +1000 +35 汉 5汉 20 = 7125 m(24 m5 5 p1 p4 p 4375 0 35 10 20 = 11375 = 7125 般的计算mij以及sij的过程如下图所示: 1 2 34 5 6 0 15750 7875 9375 11375 15125 02625 4375 7125 10500 07502500 5375 01000 3500 05000 0 1 2 i 3 4 5 6 1 0 1 1 3 3 3 2 0 2 3 3 3 3 0 3 3 3 4 5 0 4

16、 5 6 0 5 0 123456 si j mi 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 *

17、 * s) if (i=j) retur n; Traceback(i, sij, s); Traceback(sij+1, j, s); cout “Multiply A ” i “, ” sij; cout “and A” (sij +1) “, ” j endl; 总结上面解矩阵连乘积问题，我们可以归纳出使用动态规划算法的基本步 骤： 1. 分析最优解的结构 在这一步中，应该确定要解决的问题应该是具有最小子结构性质，这是选择动态 规划算法的基础。 2. 建立递归关系 第一步的结构分析已经为建立递归关系奠定了基础。这一步的主要任务是递归地 定义最优值，并建立该问题与其子问题最优值之间的递归关系。 例如在矩阵连乘 积问题中，递归关系为 mi j 0 min f mi k mk 1 i迷勺 j pi - 1* pk* 在0/1背包问题中的递归关系是(gj(X)表示0/1背包问题Knap(j+1,n,X)的最 优值) gj(X maXgj 1(X),gj (X -Wj .1)Pj J(6.1.8)