Chapter 15 Dynamic Programming_图文.ppt

第15章动态规划 引论 动态规划法在本课程介绍的算法设计方法中是最难的 应用： （1）0/1背包问题 （2）矩阵乘法链 （4）最短路径 15.1动态规划原理 从算法设计的角度看,动态规划是一种在各个不同大小(size)的子问题的优化值之间建立递归关系并求解的过程. 能用动态规划求解的问题必须满足优化原理:优化解包含的子问题的解也是优化的. 利用优化原理,使用枚举法建立不同长度子问题的优化值之间的递归关系－动态规划方程. 动态规划得到的是精确解. 子问题的数目决定算法的复杂性. 实现时要尽可能消去递归. 例15-1 [多段图] 例15-1 [最短路经]（结论） 多段图问题满足优化原理: 最短路(1-3-5-7)上的子路径(3-5-7) 是3到目的节点7在子图上的最短路. 无论最短路的下一跳是{2,3,4}中的那个节点,其后的路径也应是最短路. 节点1到目的节点的最短路长度c(1)可从2,3,4到目的节点的最短路长度c(i)＋节点1到这些节点的边成本cost(1,i)经枚举得到:c(1)=miniε{2,3,4}{c(i)+cost(1,i)} 多段图的动态规划算法 但2,3,4到目的节点的最短路长度c(2), c(3), c(4) 还不知道! 我们须计算c(2),c(3),c(4);仍使用优化原理. 一般情形: 设c(i)为i到目的节点的最短路长度, A(i)为与i相邻的结点集合,有: c(i)=minjεA(i){c(j)+cost(i, j)} 但c(i)由i 到目的节点的子图来决定,和节点1怎样走到i 没关系(Markov 性质). 我们有c(7)=0 从c(7)开始向前计算 初始c(7)=0 依次计算c(6),…,c(1)： C(6)=1,c(5)=2, c(4)=8+c(6) C(3)=min{1+c(5),5+c(6)} C(2)=min{7+c(5),6+c(6)} C(1)=min{1+c(2),4+c(3),6+c(4)} 递归还可从前向后：c(i)=节点1到节点i的最短路的长度；递归从c(1)=0开始。 例15-2 [0/1背包问题] 0/1背包问题的解指物品1,…,n的一种放法(x1, ···,xn的0/1赋值), 使得效益值最大. 假定背包容量不足以装入所有物品:面临选择. 因为目标函数是非负数之和= 优化原理:无论优化解是否放物品1,相对剩余背包容量,优化解对物品2,…,n的放法, 也是优化解. 背包问题满足的优化原理 例如n=5,c=10,w=[2,2,6,5,4],p=[6,3,5,4,6]. 其优化解为(1,1,0,0,1),即优化的物品装入背包的方法为 1,2,5. 物品1占背包容量2,剩下容量为8. 优化解中包含的子问题:n=4,c’=c-2(物品1的重量),物品为2,3,4,5 (1,0,0,1),即放物品2和5,是上述子问题的优化解. 背包问题满足的优化原理. 优化值间的递归式 虽然我们不知道优化解是否放物品1,但我们可以利用优化原理,从枚举“放”和“不放”两种情形建立优化值之间的递归式: 设f(i, y)为以背包容量y,放物品i,…,n,得到的优化效益值,以下递归关系成立: f(1,c)=max{f(2,c), f(2,c-w1)+p1} 先求子问题的优化值(递归),再从2种可能性中选出最优的. 须求解:任意给定容量y, 任意i,…,n 种物品的子问题. 例15-2 [0/1背包问题]（解） n=3, w=[100,14,10], p=[20,18,15], c=116 放进物品1(x1 = 1),背包容量还剩r=16. [x2,x3]= [1,0] 为子问题的优化解,值为18. 不放物品1(x1= 0)则对于剩下的两种物品而言,容 量限制条件为116，[1,1]为子问题优化解,值为33 前者效益值为38, 后者为33; 所以优化解为[1,1,0], 优化值为38. 例15-4 [0/1背包] 令f(i,y) 表示容量为y,物品i,i+1,···,n 的优化效益值,按优化原理可列递归关系如下： 第2行表示背包容量y不足以放下物品i. 例15-4 0/1背包的DP算法 问题要求计算f(1,c), 所以计算过程中不必计算 f(i, y), yc 计算从f(n, *)开始 然后应用(15-1)式递归计算 f(i, y) i=n-1,n-2，···,2， 最按 f(1,c)=max{f(2,c), f(2,c-w1)+p1}计算f(1,c). 例题15.2：n=3, w=[100,14,10],