动态规划是本书介绍的五种算法设计方法中难度最大的一种，它建立在最优原则的基础上。采用动态规划方法，可以优雅而高效地解决许多用贪婪算法或分而治之算法无法解决的问题。在介绍动态规划的原理之后，本章将分别考察动态规划方法在解决背包问题、图象压缩、矩阵乘法链、最短路径、无交叉子集和元件折叠等方面的应用。
3.1 算法思想
和贪婪算法一样，在动态规划中，可将一个问题的解决方案视为一系列决策的结果。不同的是，在贪婪算法中，每采用一次贪婪准则便做出一个不可撤回的决策，而在动态规划中，还要考察每个最优决策序列中是否包含一个最优子序列。
例3-1 [最短路经] 考察图1 2 - 2中的有向图。假设要寻找一条从源节点s= 1到目的节点d= 5的最短路径，即选择此路径所经过的各个节点。第一步可选择节点2，3或4。假设选择了节点3，则此时所要求解的问题变成：选择一条从3到5的最短路径。如果3到5的路径不是最短的，则从1开始经过3和5的路径也不会是最短的。例如，若选择的子路径（非最短路径）是3，2，5 (耗费为9 )，则1到5的路径为1，3，2，5 (耗费为11 )，这比选择最短子路径3，4，5而得到的1到5的路径1，3，4，5 (耗费为9) 耗费更大。
所以在最短路径问题中，假如在的第一次决策时到达了某个节点v，那么不管v 是怎样确定的，此后选择从v 到d 的路径时，都必须采用最优策略。
例3-2 [0/1背包问题] 考察1 3 . 4节的0 / 1背包问题。如前所述，在该问题中需要决定x1 .. xn的值。假设按i = 1，2，.，n 的次序来确定xi 的值。如果置x1 = 0，则问题转变为相对于其余物品（即物品2，3，.，n），背包容量仍为c 的背包问题。若置x1 = 1，问题就变为关于最大背包容量为c-w1 的问题。现设r?{c，c-w1 } 为剩余的背包容量。
在第一次决策之后，剩下的问题便是考虑背包容量为r 时的决策。不管x1 是0或是1，[x2 ，.，xn ] 必须是第一次决策之后的一个最优方案，如果不是，则会有一个更好的方案[y2，.，yn ]，因而[x1，y2，.，yn ]是一个更好的方案。
假设n=3, w=[100,14,10], p=[20,18,15], c= 11 6。若设x1 = 1，则在本次决策之后，可用的背包容量为r= 116-100=16 。[x2，x3 ]=[0,1] 符合容量限制的条件，所得值为1 5，但因为[x2，x3 ]= [1，0] 同样符合容量条件且所得值为1 8，因此[x2，x3 ] = [ 0，1] 并非最优策略。即x= [ 1，0，1] 可改进为x= [ 1，1，0 ]。若设x1 = 0，则对于剩下的两种物品而言，容量限制条件为11 6。总之，如果子问题的结果[x2，x3 ]不是剩余情况下的一个最优解，则[x1，x2，x3 ]也不会是总体的最优解。
例3-3 [航费] 某航线价格表为：从亚特兰大到纽约或芝加哥，或从洛杉矶到亚特兰大的费用为$ 1 0 0；从芝加哥到纽约票价$ 2 0；而对于路经亚特兰大的旅客，从亚特兰大到芝加哥的费用仅为$ 2 0。从洛杉矶到纽约的航线涉及到对中转机场的选择。如果问题状态的形式为（起点，终点），那么在选择从洛杉矶到亚特兰大后，问题的状态变为（亚特兰大，纽约）。从亚特兰大到纽约的最便宜航线是从亚特兰大直飞纽约，票价$ 1 0 0。而使用直飞方式时，从洛杉矶到纽约的花费为$ 2 0 0。不过，从洛杉矶到纽约的最便宜航线为洛杉矶-亚特兰大-芝加哥-纽约，其总花费为$ 1 4 0（在处理局部最优路径亚特兰大到纽约过程中选择了最低花费的路径：亚特兰大-芝加哥-纽约）。
如果用三维数组（t a g，起点，终点）表示问题状态，其中t a g为0表示转飞， t a g为1表示其他情形，那么在到达亚特兰大后，状态的三维数组将变为（ 0，亚特兰大，纽约），它对应的最优路径是经由芝加哥的那条路径。
当最优决策序列中包含最优决策子序列时，可建立动态规划递归方程（ d y n a m i c -programming recurrence equation），它可以帮助我们高效地解决问题。
例3-4 [0/1背包] 在例3 - 2的0 / 1背包问题中，最优决策序列由最优决策子序列组成。假设f (i,y) 表示例1 5 - 2中剩余容量为y，剩余物品为i，i + 1，.，n 时的最优解的值，即：和利用最优序列由最优子序列构成的结论，可得到f 的递归式。f ( 1 ,c) 是初始时背包问题的最优解。可使用（ 1 5 - 2）式通过递归或迭代来求解f ( 1 ,c)。从f (n, * )开始迭式， f (n, * )由（1 5 - 1）式得出，然后由（ 1 5 - 2）式递归计算f (i,*) ( i=n- 1，n- 2，.， 2 )，最后由（ 1 5 - 2）式得出f ( 1 ,c)。
对于例1 5 - 2，若0≤y＜1 0，则f ( 3 ,y) = 0；若y≥1 0，f ( 3 ,y) = 1 5。利用递归式（1 5 - 2），可得f (2, y) = 0 ( 0≤y＜10 )；f（2，y）= 1 5（1 0≤y＜1 4）；f（2，y）= 1 8（1 4≤y＜2 4）和f（2，y）= 3 3（y≥2 4）。因此最优解f ( 1 , 11 6 ) = m a x {f（2，11 6），f（2，11 6 - w1）+ p1} = m a x {f（2，11 6），f（2，1 6）+ 2 0 } = m a x { 3 3，3 8 } = 3 8。
现在计算xi 值，步骤如下：若f ( 1 ,c) =f ( 2 ,c)，则x1 = 0，否则x1 = 1。接下来需从剩余容量c-w1中寻求最优解，用f (2, c-w1) 表示最优解。依此类推，可得到所有的xi (i= 1.n) 值。
在该例中，可得出f ( 2 , 11 6 ) = 3 3≠f ( 1 , 11 6 )，所以x1 = 1。接着利用返回值3 8 -p1=18 计算x2 及x3，此时r = 11 6 -w1 = 1 6，又由f ( 2 , 1 6 ) = 1 8，得f ( 3 , 1 6 ) = 1 4≠f ( 2 , 1 6 )，因此x2 = 1，此时r= 1 6 -w2 = 2，所以f (3,2) =0，即得x3 = 0。
动态规划方法采用最优原则（ principle of optimality）来建立用于计算最优解的递归式。所谓最优原则即不管前面的策略如何，此后的决策必须是基于当前状态（由上一次决策产生）的最优决策。由于对于有些问题的某些递归式来说并不一定能保证最优原则，因此在求解问题时有必要对它进行验证。若不能保持最优原则，则不可应用动态规划方法。在得到最优解的递归式之后，需要执行回溯（t r a c e b a c k）以构造最优解。
编写一个简单的递归程序来求解动态规划递归方程是一件很诱人的事。然而，正如我们将在下文看到的，如果不努力地去避免重复计算，递归程序的复杂性将非常可观。如果在递归程序设计中解决了重复计算问题时，复杂性将急剧下降。动态规划递归方程也可用迭代方式来求解，这时很自然地避免了重复计算。尽管迭代程序与避免重复计算的递归程序有相同的复杂性，但迭代程序不需要附加的递归栈空间，因此将比避免重复计算的递归程序更快。
3.2 应用
3.2.1 0/1背包问题
1. 递归策略
在例3 - 4中已建立了背包问题的动态规划递归方程，求解递归式（ 1 5 - 2）的一个很自然的方法便是使用程序1 5 - 1中的递归算法。该模块假设p、w 和n 为输入，且p 为整型，F(1,c) 返回f ( 1 ,c) 值。
程序15-1 背包问题的递归函数
int F(int i, int y)
{// 返回f ( i , y ) .
if (i == n) return (y < n=" 5，p="" w="[2,2,6,5,4]" c=" 1" i="j，因此根节点表示F" t="">
void Knapsack(T p[], int w[], int c, int n, T** f)
{// 对于所有i和y计算f [ i ] [ y ]
// 初始化f [ n ] [ ]
for (int y = 0; y <= yMax; y++) f[n][y] = 0; for (int y = w[n]; y <= c; y++) f[n][y] = p[n]; // 计算剩下的f for (int i = n - 1; i > 1; i--) {
for (int y = 0; y <= yMax; y++) f[i][y] = f[i+1][y]; for (int y = w[i]; y <= c; y++) f[i][y] = max(f[i+1][y], f[i+1][y-w[i]] + p[i]); } f[1][c] = f[2][c]; if (c >= w[1])
f[1][c] = max(f[1][c], f[2][c-w[1]] + p[1]);
}
template
void Traceback(T **f, int w[], int c, int n, int x[])
{// 计算x
for (int i = 1; i < i=" 5时，f" x1 =" 1；由f" p2 ="f" x2 =" 1；由f" x3="x4" x5=" 1。" xi =" 1时的数对集，而P(i+" xi =" 0的数对集。接下来，合并Q和P(i+" q=" [" q="[(6,5)," q=" [" i="2|P(i" 6 =" 1" i =" 1li" s0 =" 0。考虑第i" j ="a" si =" si-r" s1 ="s0" 11 =" 1" y1 =" 1s2" s2 =" m" 11 =" m" 11 =" 2" y2 =" 2" s5 =" [" y5 =" [" s5 =" 8" y5 =" 4，所以s5" k="4" i ="="" k =" 1时," lsum =" l[i],bmax" s =" S(i-1)" k =" 2;" bmax =" b[i-k+1];" t =" S(i-k);"> t + lsum * bmax) {
s = t + lsum * bmax;
kay[i] = k;}
}
return s + header;
}
void Traceback(int kay[], int n)
{// 合并段
if (n == 0) return;
Tr a c e b a c k ( k a y, n-kay[n]);
cout << "New segment begins at " << (n - kay[n] + 1) << i ="=""> 0) return s[i]; //已计算完
/ /计算s [ i ]
/ /首先根据公式（1 5 - 3）计算k = 1时最小值
int lsum = l[i], bmax = b[i];
s[i] =S(i-1) + lsum * bmax;
kay[i] = 1;
/ /对其余的k计算最小值并更新
for (int k = 2; k <= i && lsum+l[i-k+1] <= L; k++) { lsum += l[i-k+1]; if (bmax < bmax =" b[i-k+1];" t =" S(i-k);"> t + lsum * bmax) {
s[i] = t + lsum * bmax;
kay[i] = k;}
}
s[i] += header;
return s[i];
}
为了确定程序1 5 - 4的时间复杂性，我们将使用分期计算模式（ amortization scheme）。在该模式中，总时间被分解为若干个不同项，通过计算各项的时间然后求和来获得总时间。当计算si 时，若sj 还未算出，则把调用S(j) 的消耗计入sj ；若sj 已算出，则把S(j) 的消耗计入si (这里sj依次把计算新sq 的消耗转移至每个sq )。程序1 5 - 4的其他消耗也被计入si。因为L是2 5 6之内的常数且每个li 至少为1，所以程序1 5 - 4的其他消耗为( 1 )，即计入每个si 的量是一个常数，且si 数目为n，因而总工作量为(n)。
3. 迭代方法
倘若用式（1 5 - 3）依序计算s1 , ., sn，便可得到一个复杂性为(n)的迭代方法。在该方法中，在si 计算之前， sj 必须已计算好。该方法的代码见程序1 5 - 5，其中仍利用函数Tr a c e b a c k（见程序1 5 - 3）来获得最优合并。
程序15-5 迭代计算s和k a y
void Vbits (int l[], int b[], int n, int s[], int kay[])
{ / /计算s [ i ]和k a y [ i ]
int L = 256, header = 11 ;
s[0] = 0;
/ /根据式（1 5 - 3）计算s [ i ]
for (int i = 1; i <= n; i++) { // k = 1时,计算最小值 int lsum = l{i}, bmax = b[i]; s[i] = s[i-1] + lsum * bmax; kay[i] = 1; / /对其余的k计算最小值并更新 for (int k=2; k<= i && lsum+l[i-k+1]<= L; k++) { lsum += l[i-k+1]; if (bmax < bmax =" b[i-k+1];"> s[i-k] + lsum * bmax){
s[i] = s[i-k] + lsum * bmax;
kay[i] = k; }
}
s[i] += header;
}
}
没有评论:
发表评论