第15章动态规划ppt课件.ppt

《第15章动态规划ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第15章动态规划学习内容算法思想应用背包问题图像压缩矩阵乘法链最短路径无交叉子集元件折叠15.1算法思想最短路径问题：第一步，可选择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

2、=[100,14,10],p=[20,18,15],c=116xi=1剩余容量16，剩余物品2、3，一种解[x2,x3]=[1,0]，但[x2,x3]=[1,0]更优[x1,x2,x3]最优解必然包含[x2,x3]的最优解最优解[1,1,0]，价值38xi=0剩余容量116，[x2,x3]=[1,1]最优最优解[0,1,1]，价值33考虑两个决策序列，[1,1,0]最优航行费用问题航线价格亚特兰大纽约/芝加哥，洛杉机亚特兰大：$100芝加哥纽约：$20从亚特兰大转机芝加哥：$20求洛杉机纽约最小费用航线

3、(洛杉机,纽约)洛杉机—亚特兰大—(亚特兰大,芝加哥)：最优$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=1160≤y<10，f(3,y)=0；y≥10，f(3,y)=150≤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

4、}=1824≤y，f(2,y)=max{f(3,y),f(3,y-14)+18}=33f(1,116)=max{f(2,116),f(2,16)+20}=38上述计算过程已经隐含地得到了xix1=1x2=1x3=0小结：动态规划思想最优原则：principleofoptimality问题C可以分解为子问题A和子问题B局部最优特性：无论A的决策如何，C的最优决策必然包含B的最优决策——B不是最优，C也不可能最优！建立递归式计算最优解回溯构造最优解避免递归实现——迭代计算15.2应用15.2.10/1背包问题递归实现intF(

5、inti,inty){//Returnf(i,y).if(i==n)return(yvoidKnapsack(Tp[],intw[],intc,intn,T

6、**f){//Computef[i][y]foralliandy.//initializef[n][]intyMax=min(w[n]-1,c);for(inty=0;y<=yMax;y++)f[n][y]=0;for(y=w[n];y<=c;y++)f[n][y]=p[n];改进（续）//computeremainingf'sfor(inti=n-1;i>1;i--){yMax=min(w[i]-1,c);for(inty=0;y<=yMax;y++)f[i][y]=f[i+1][y];for(y=w[i];y<=c;y++)

7、f[i][y]=max(f[i+1][y],f[i+1][y-w[i]]+p[i]);}f[1][c]=f[2][c];if(c>=w[1])f[1][c]=max(f[1][c],f[2][c-w[1]]+p[1]);}Q(cn)改进（续）templatevoidTraceback(T**f,intw[],intc,intn,intx[]){//Computexforoptimalfilling.for(inti=1;i

8、1;c-=w[i];}x[n]=(f[n][c])?1:0;}其他改进方法数组方式缺点权必须为整数c>2n，W(n2n)三元组方法改进(i,y,f(i,y))保存于hash表计算f(i,y)前先检索hash表，若有，直接使用；若没有，进行计算，计算完毕插入has