动态规划-超强文档 - heaven

第4章 动态规划

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。若用分治法解这类问题，则分解得到的子问题数目太多，以至于最后解决原问题需要耗费指数时间。然而，不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算．从而得到多项式时间算法。为了达到这个目的，可以用—个表来记录所有已解决的子问题的答案。不管该子问题以后是否被用到．只要它被计算过，就将其结果填入表中，这就是动念规划法的基本思想。具体的动态规划算法是多种多样的，但它们具有相同的填表格式。

动态规划算法适用于解最优化问题，通常可以按以下步骤设计动态规划算法： (1)找出最优解的性质，并刻画其结构特征； (2)递归地定义最优值；

(3)以自底向上的方式计算出最优值；

(4)根据计算最优值时得到的信息，构造最优解。

步骤(1)一(3)是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤(4)可以省去。若需要求问题的最优解，则必须执行步骤(4)。此时，在步骤(3)中计算最优值时，通常需记录更多的信息，以便在步骤(4)中，根据所记录的信息，快速构造出最优解。

下面以具体例子说明如何运用动态规划算法的设计思想，并分析可用动态规划算法求解的问题应该具备的一般特征。

4.1 矩阵连乘问题

4.1.1 问题描述

给定n个数字矩阵A1，A2，?，An，其中Ai与Ai+1是可乘的，i=1,2,?,n-1.求矩阵连乘A1A2???An的加括号方法，使得所用的数乘次数最少。

考察两个矩阵相成的情形：C=AB。如果矩阵A，B分别是p×r和r×q矩阵，则它们的乘积C将是p×q矩阵，其(i, j)元素为

cij??aikbkj

k?1r(4.1.1)

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)记连乘积的完全加括号数，则有如下递归关系

n?1?1?n?1 P(n)?? (4.1.2)

P(k)P(n?k)n?1???k?1由此不难算出P=C(n-1)，其中C表示Catalan数：

C(n)?1?2n?n3/2????(4/n) (4.1.3) ??n?1?n?也就是说，P(n)是随n指数增长的，所以，我们不能希望列举所有可能次序的连乘积，从中找到具有最少数乘次数的连乘积算法。事实上，矩阵连乘积问题具有最优子结构性质，我们可以采用动态规划的方法，在多项式时间内找到最优的连乘积次序。

用A[i:j]表示连乘积AiAi＋1???Aj。分析计算A[1:n]的一个最优次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链分开，1?k

如上三个例子都具有最优子结构性质，这个性质决定了解决此类问题的基本思路是：

首先确定原问题的最优值和其子问题的最优值之间的递推关系（自上向下），然后自底向上递归地构造出最优解（自下向上）。

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

程序 4.1.1 计算矩阵连乘的递归算法

n int RecurMatrixChain(int i, int j) {

if (i==j) return 0;

int u=RecurMatrixChain(i, i) +RecurMatrixChain(i+1,j) +p[i-1]*p[i]*p[j]; s[i][j]=i;

for(int k=i+1; k

如果用T(n)表示该算法的计算A[1:n]的时间，则有如下递归关系式：

?O(1)?n?1 T(n)??1??(T(k)?T(n?k)?1)?k?1?当n?1时

n?1n?1

T(n)?1?(n?1)??T(k)??T(n－k)?n?2?T(k)，

k?1k?1k?1n?1n?1n?1可用数学归纳法直接证明：T(n)?2n?1??(2n)，这显然不是我们所期望的。

注意到，在用递归算法自上向下求解具有最优子结构的问题时，每次产生的子问题并不总是新问题，有些问题被反复计算多次。如果对每一个问题只解一次，而后将其解保存在一个表格中，当再次需要解此问题时，只是简单地用常数时间查看一下结果。则可以节省大量的时间。在矩阵的连乘积问题中，若用m[i][j]表示由第i个矩阵到第j个矩阵的连乘积所用的最少数乘次数，则计算m[1][n]时共有?(n)个子问题。这是因为，对于

21?i?j?n，不同的有序对(i, j)对应于不同的子问题，不同子问题最多只有

?n?2??2???n??(n)个。下面将会看到，用动态规划解此问题时，可在多项式时间内完成。 ??

程序 4.1.2 求矩阵连乘最优次序的动态规划算法

void MatrixChain(int p, int n, int * *m, int * *s) {

for (int i=1; i<=n; i++) m[i][i]=0;

for (int r=2; r<=n; r++) for (int i=1; i<=n-r+1; i++){

int j=i+r-1; \\\\ r是跨度

m[i][j]= m[i+1][j]+p[i-1]*p[i]*p[j]; s[i][j]=i;

for (int k=i+1; k

int t= m[i][k]+ m[k+1][j]+p[i-1]*p[k]*p[j]; if (t< m[i][j]) { m[i][j]=t; s[i][j]=k; } } } }

算法MatrixChain的主要计算量取决于程序中对r, i和k的三重循环，循环体内的计算量为O(1)，三重循环的总次数是O(n)，所以，算法的计算时间上界为O(n)。

例子 求以下6个矩阵连乘积最少数乘计算次数及所采用乘法次序。

3

3

A1:30?35;A2:35?15;A3:15?5;A4:5?10;A5:10?20;A6:20?25

?m[2][2]?m[3][5]?p1p2p5?0?2500?35?15?20?13000?m[2][5]?min?m[2][3]?m[4][5]?p1p3p5?2625?1000?35?5?20?7125?m[2][4]?m[5][5]?ppp?4375?0?35?10?20?11375

145??7125一般的计算m[i][j]以及s[i][j]的过程如下图所示： 1 2 3 4 5 6

j

1 2 3 4 5 6

1 2 3 4 5 6

j

1 2 3 4 5 6 0 1 1 3 3 3 0 2 3 3 3 0 3 3 3 0 4 5 0 5 0 i

0 15750 7875 9375 11875 15125 0 2625 4375 7125 10500 0 750 2500 5375 0 1000 3500 0 5000 0 i

m[i][j] s[i][j]

注意，上述算法只是明确给出了矩阵最优连乘次序所用的数乘次数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