第15章动态规划引论动态规划法.ppt

第15章动态规划
第15章动态规划引论动态规划法
引论
动态规划法在本课程介绍的算法设计方法中是最难的
应用：
（1）0/1背包问题
（2）矩阵乘法链
（4）最短路径
第15章动态规划引论动态规划法

动态规划常用来解优化问题.
能用动态规划求解的问题必须满足优化原理:优化解包含的子问题的解也是优化的.
建立不同长度的子问题的优化值之间的递归关系。
动态规划得到的是精确解。
第15章动态规划引论动态规划法
例15-1 [多段图]
第15章动态规划引论动态规划法
例15-1 [最短路经]（结论）
多段图问题满足优化原理:
最短路(1->3->5->7), (3->5->7)
无论最短路的下一跳是{2,3,4}中的那个节点,其后的路径也应是最短路.
节点1到目的节点的最短路长度c(1)可从2,3,4到目的节点的最短路长度c(i)＋节点1到这些节点的边成本cost(1,j)经枚举得到:c(1)=miniε{2,3,4}{c(i)+cost(1,i)}
第15章动态规划引论动态规划法
多段图的动态规划算法
但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)}
第15章动态规划引论动态规划法
例
初始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章动态规划引论动态规划法
例15-2 [0/1背包问题]
0/1背包问题的解指物品1,…,n的一种放法(x1, ···,xn的0/1赋值), 使得效益值最大.
假定背包容量不足以装入所有物品:面临选择.
优化原理:无论优化解是否放物品1,优化解对物品2,…,n的放法,相对剩余背包容量,也是优化解.
第15章动态规划引论动态规划法
背包问题满足的优化原理
例如n=5,c=10,p=[6,3,5,4,6],w=[2,2,6,5,4]
其优化解为(1,1,0,0,1),即放物品1,2,5.
物品1占背包容量2,剩下容量为8.
考虑子问题:n=4,c’=8,物品为2,3,4,5
(1,0,0,1),即放物品1和5,是子问题的优化解.
以上是背包问题满足的优化原理.
第15章动态规划引论动态规划法
优化值间的递归式
虽然不知道优化解是否放物品1,但从优化原理我们能建立优化值间的递归式:
设f(i, y)为以背包容量y,放物品i,…,n,得到的优化效益值,以下递归关系成立:
f(1,c)=max{f(2,c), f(2,c-w1)+p1}
先求子问题的优化值(递归),再从2种可能性中求出最优的.
须对任意给定容量y, 任意i,…,n 种物品求解子问题.
第15章动态规划引论动态规划法