文档介绍：第6章动态规划
动态规划是我们要介绍的几种算法设计方法中难度最大的一种,它建立在最优原则的基础上。采用动态规划方法,可以高效地解决许多用贪婪算法或分而治之算法无法解决的问题。
在介绍动态规划的原理之后,将分别考察动态规划方法在解决背包问题、图象压缩、矩阵乘法链、最短路径、无交叉子集等方面的应用。
1算法思想
和贪婪算法一样,在动态规划中,可将一个问题的解决方案视为一系列决策的结果。不同的是,在贪婪算法中,每采用一次贪婪准则便做出一个不可撤回的决策,而在动态规划中,还要考察每个最优决策序列中是否包含一个最优子序列。
例6-1[最短路经]考察下图中的有向图。假设要寻找一条从源节点s=1到目的节点d=5的最短路径,即选择此路径所经过的各个节点。第一步可选择节点2,3或4。假设选择了节点3,则此时所要求解的问题变成:选择一条从3到5的最短路径。如果3到5的路径不是最短的,则从1开始经过3和5的路径也不会是最短的。
所以在最短路径问题中,假如在的第一次决策时到达了某个节点v,那么不管v是怎样确定的,此后选择从v到d的路径时,都必须采用最优策略。
例6-2[0/1背包问题]考察前面的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=116。若设x1=1,则在本次决策之后,可用的背包容量为r=116-100=16。[x2,x3]=[0,1]符合
容量限制的条件,所得值为15,但因为[x2,x3]=[1,0]同样符合容量条件且所得值为18,因此[x2,x3]=[0,1]并非最优策略。即x=[1,0,1]可改进为x=[1,1,0]。若设x1=0,则对于剩下的两种物品而言,容量限制条件为116。总之,如果子问题的结果[x2,x3]不是剩余情况下的一个最优解,则[x1,x2,x3]也不会是总体的最优解。
例6-3[航费]假设某航线价格表为:从亚特兰大到纽约或芝加哥,或从洛杉矶到亚特兰大的费用为$100;从芝加哥到纽约票价$20;而对于路经亚特兰大的旅客,从亚特兰大到芝加哥的费用仅为$20。从洛杉矶到纽约的航线涉及到对中转机场的选择。
洛杉矶
芝加哥
亚特兰大
纽约
100
100
20
100
20
如果问题状态的形式为(起点,终点),那么在选择从洛杉矶到亚特兰大后,问题的状态变为(亚特兰大,纽约)。从亚特兰大到纽约的最便宜航线是从亚特兰大直飞纽约,票价$100。而使用直飞方式时,从洛杉矶到纽约的花费为$200。不过,从洛杉矶到纽约的最便宜航线为洛
杉矶-亚特兰大-芝加哥-纽约,其总花费为$140(在处理局部最优路径亚特兰大到纽约过程中选择了最低花费的路径:亚特兰大-芝加哥-纽约)。
如果用三维数组(tag,起点,终点)表示问题状态,其中tag为0表示转飞,tag为1表示其他情形,那么在到达亚特兰大后,状态的三维数组将变为(0,亚特兰大,纽约),它对应的最优路径是经由芝加哥的那条路径。
当最优决策序列中包含最优决策子序列时,可建立动态规划递归方程通常是根据最优准则,得出动态规划计算的“递归”计算式。
通常,这个递归式也是解决问题的关键,写出递归公式,然后用递归程序实现,并消除重复计算
在大多数情况下,求出递归方程是实际工作中的难点
而消除重复计算则成为问题是否可以实际求解的关键
(dynamic-programming recurrence equation),它可以帮助我们高效地解决问题。
例6-4[0/1背包]在例6-2的0/1背包问题中,最优决策序列由最优决策子序列组成。假设f(i,y)先把这个表示的地意义弄清楚?
表示例6-2中剩余容量为y,剩余物品为i,i+1,…,n时的最优解的值,即:
这个递归方程实际上将所有的情形全部考虑进去了,然后再从中找到一个最优解
利用最优序列由最优子序列构成的结论,可得到f的递归式。f(1,c)是初始时背包问题的最优解。可通过递归或迭代来求解f(1,c)。从f(n,*)开始迭式,先求出f(n,*),然后递归计算f(i,*)(i=n-1,n-2
,.,2),最后得出f(1,c)。
对于例6-2(w