内蒙古大学《算法与数据结构》讲义15动态规划

下载第1 5章动 态 规 划动态规划是本书介绍的五种算法设计方法中难度最大的一种， 它建立在最优原则的基础上。采用动态规划方法，可以优雅而高效地解决许多用贪婪算法或分而治之算法无法解决的问题。在介绍动态规划的原理之后，本章将分别考察动态规划方法在解决背包问题、图象压缩、矩阵乘法链、最短路径、无交叉子集和元件折叠等方面的应用。15.1 算法思想和贪婪算法一样，在动态规划中，可将一个问题的解决方案视为一系列决策的结果。不同的是，在贪婪算法中，每采用一次贪婪准则便做出一个不可撤回的决策，而在动态规划中，还要考察每个最优决策序列中是否包含一个最优子序列。例15-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 的路径时，都必须采用最优策略。例15-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的问题。现设rc，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 也不会是总体的最优解。例15-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） ，它可以帮助我们高效地解决问题。例15-4 0/1背包 在例1 5 - 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，若0y1 0，则f ( 3 ,y) = 0；若y1 0，f ( 3 ,y) = 1 5。利用递归式（1 5 - 2） ，可得f (2, y) = 0 ( 0y10 )；f（2，y）= 1 5（1 0y1 4）；f（2，y）= 1 8（1 4y2 4）和f（2，y）= 3 3（y2 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= 1n) 值。在该例中，可得出f ( 2 , 11 6 ) = 3 3f ( 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 4f ( 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）以构造最优解。编写一个简单的递归程序来求解动态规划递归方程是一件很诱人的事。然而，正如我们将在下文看到的，如果不努力地去避免重复计算，递归程序的复杂性将非常可观。如果在递归程序设计中解决了重复计算问题时，复杂性将急剧下降。动态规划递归方程也可用迭代方式来求解，这时很自然地避免了重复计算。尽管迭代程序与避免重复计算的递归程序有相同的复杂性，但迭代程序不需要附加的递归栈空间，因此将比避免重复计算的递归程序更快。4 6 8第三部分算法设计方法下载（1 5 - 1）（1 5 - 2）15.2 应用15.2.1 0/1背包问题1. 递归策略在例1 5 - 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 wn) ? 0 : pn;if (y wi) return F(i+1,y); return max(F(i+1,y), F(i+1,y-wi) + pi);程序1 5 - 1的时间复杂性t(n)满足：t( 1 ) =a；t（n）2t（n- 1）+b（n1） ，其中a、b 为常数。通过求解可得t(n) =O( 2n） 。例15-5 设n= 5，p= 6 , 3 , 5 , 4 , 6 ，w=2,2,6,5,4 且c= 1 0 ,求f ( 1 , 1 0 )。为了确定f ( 1 , 1 0 )，调用函数F ( 1 , 1 0 )。递归调用的关系如图1 5 - 1的树型结构所示。每个节点用 y值来标记。对于第j层的节点有i=j，因此根节点表示F ( 1 , 1 0 )，而它有左孩子和右孩子，分别对应 F ( 2 , 1 0 )和F ( 2 , 8 )。总共执行了2 8次递归调用。但我们注意到，其中可能含有重复前面工作的节点，如 f ( 3 , 8 )计算过两次，相同情况的还有f ( 4 , 8 )、f ( 4 , 6 )、f ( 4 , 2 )、f ( 5 , 8 )、f ( 5 , 6 )、f ( 5 , 3 )、f (5,2) 和f ( 5 , 1 )。如果保留以前的计算结果，则可将节点数减至1 9，因为可以丢弃图中的阴影节点。图15-1 递归调用树正如在例1 5 - 5中所看到的，程序1 5 - 1做了一些不必要的工作。为了避免 f (i,y)的重复计算，必须定义一个用于保留已被计算出的f (i,y)值的表格L，该表格的元素是三元组(i,y,f (i,y) )。在计算每一个f (i,y)之前，应检查表L中是否已包含一个三元组(i,y, * )，其中*表示任意值。如果已包含，则从该表中取出f (i,y)的值，否则，对f (i,y)进行计算并将计算所得的三元组(i,y,f (i,y) )加入第1 5章动 态 规 划4 6 9下载表L。L既可以用散列（见7 . 4节）的形式存储，也可用二叉搜索树(见11章)的形式存储。2. 权为整数的迭代方法当权为整数时，可设计一个相当简单的算法（见程序 1 5 - 2）来求解f ( 1 ,c)。该算法基于例1 5 - 4所给出的策略，因此每个f (i,y) 只计算一次。程序1 5 - 2用二维数组f 来保存各f 的值。而回溯函数Tr a c e b a c k用于确定由程序1 5 - 2所产生的xi值。函数K n a p s a c k的复杂性为( n c） ，而Tr a c e b a c k的复杂性为( n )。程序15-2 f 和x 的迭代计算templatevoid 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+)fny = 0;for (int y = wn; y 1; i-) for (int y = 0; y = yMax; y+)fiy = fi+1y;for (int y = wi; y = w1)f1c = max(f1c, f2c-w1 + p1);templatevoid Traceback(T *f, int w, int c, int n, int x)/ 计算x for (int i = 1; i n; i+)if (fic = fi+1c) xi = 0;else xi = 1;c -= wi;xn = (fnc) ? 1 : 0;3. 元组方法（选读）程序1 5 - 2有两个缺点：1) 要求权为整数；2) 当背包容量c 很大时，程序1 5 - 2的速度慢于程序1 5 - 1。一般情况下，若c2n，程序1 5 - 2的复杂性为 (n2n)。可利用元组的方法来克服上述两个缺点。在元组方法中，对于每个i，f (i, y) 都以数对(y, f (i, y) 的形式按y的递增次序存储于表4 7 0第三部分算法设计方法下载P(i)中。同时，由于f (i, y) 是y 的非递减函数，因此P(i) 中各数对(y, f (i, y) 也是按f (i,