数据结构-动态规划.ppt

文档介绍：第15章动态规划
学****内容
算法思想
应用
背包问题
图像压缩
矩阵乘法链
最短路径
无交叉子集
元件折叠
算法思想
最短路径问题:第一步,可选择2、3、4
选择3,问题变为求35的最短路径:因为,如果35不是最短路径,135也不可能是最短路径
最优化问题一系列最优决策考虑多种可能决策序列
0/1背包问题
按i=1, 2, ..., n的次序确定xi的值
对i = 1,有两种选择
xi=0物品2~n,背包容量不变的背包问题
xi=1物品2~n,背包容量c-w1的背包问题
两个结果选优即可
2~n的背包问题怎么解决?递归
动态规划解0/1背包问题例
n=3, w=[100, 14, 10], p=[20, 18, 15], c=116
xi=1剩余容量16,剩余物品2、3,一种解[x2, x3]=[1, 0],但[x2, x3]=[1, 0]更优[x1, x2, x3]最优解必然包含[x2, x3]的最优解最优解[1, 1, 0],价值38
xi=0剩余容量116,[x2, x3]=[1, 1]最优最优解[0, 1, 1],价值33
考虑两个决策序列,[1, 1, 0]最优
航行费用问题
航线价格
亚特兰大纽约/芝加哥,洛杉机亚特兰大:$100
芝加哥纽约:$20
从亚特兰大转机芝加哥:$20
求洛杉机纽约最小费用航线
(洛杉机, 纽约)洛杉机—亚特兰大—(亚特兰大, 芝加哥):最优$140
建立动态规划递归方程
背包问题:f(i, y)——背包剩余容量y,剩余物品i, i+1, ..., n的最优解
递归计算或迭代计算f(n, *)f(i, *)f(1, c)
例
n=3, w=[100, 14, 10], p=[20, 18, 15], c=116
0≤y<10,f(3, y)=0;y≥10,f(3, y)=15
0≤y<10,f(2, y)=f(3, y)=010≤y<14,f(2, y)=f(3, y)=1514≤y<24,f(2, y)=max{f(3, y), f(3, y-14)+18}=1824≤y,f(2, y)=max{f(3, y), f(3, y-14)+18}=33
f(1, 116)=max{f(2, 116), f(2, 16)+20}=38
上述计算过程已经隐含地得到了xi
x1=1
x2=1
x3=0
小结:动态规划思想
最优原则:principle of optimality
问题C可以分解为子问题A和子问题B
局部最优特性:无论A的决策如何,C的最优决策必然包含B的最优决策——B不是最优,C也不可能最优!
建立递归式计算最优解回溯构造最优解
避免递归实现——迭代计算
应用
0/1背包问题
递归实现
int F(int i, int y)
{// Return f(i,y).
if (i == n) return (y < w[n]) ? 0 : p[n];
if (y < w[i]) return F(i+1,y);
return max(F(i+1,y), F(i+1,y-w[i]) + p[i]);
}
t(1)=a, t(n)≤2t(n-1)+bt(n)=O(2n)