动态规划(dp算法).doc

AD 第 3 章 动态规划 ? 动态规划是本书介绍的五种算法设计方法中难度最大的一种，它建立在最优原则的基础上。采用动态规划方法，可以优雅而高效地解决许多用贪婪算法或分而治之算法无法解决的问题。在介绍动态规划的原理之后，本章将分别考察动态规划方法在解决背包问题、图象压缩、矩阵乘法链、最短路径、无交叉子集和元件折叠等方面的应用。 ? 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