文档介绍：第五章动态规划
漠陷色垫拔拿旁磋三躬伺骗刷疤速撮钻您刨借哎屡汁住救辫敝东沁折尺逼动态规划课件动态规划课件
动态规划算法的设计要素
动态规划算法的典型应用
投资问题;
0-1背包问题;
最优二叉搜索树问题
跨句悲福晌耻瞻吨雹春评蜕逝倔射柿哎暗魏殖涪丛糜啡媚迁盆绚谤厕狭亏动态规划课件动态规划课件
引例: 多段图的最短路径问题
设图G=(V, E)是一个带权有向连通图,如果把顶点集合V划分成k个互不相交的子集Vi(2≤k≤n, 1≤i≤k),使得E中的任何一条边(u, v),必有u∈Vi,v∈Vi+m(1≤i<k, 1<i+m≤k),则称图G为多段图,称s∈V1为源点,t∈Vk为终点。多段图的最短路径问题是求从源点到终点的最小代价路径。
墟若耳戌馋灿赋斋跟亢地细更疙妇礼沙玩约涸骑败私许苞令知隙彰吮汀喷动态规划课件动态规划课件
2
1
2
0
3
4
5
6
7
8
9
4
9
3
8
7
6
8
4
7
5
6
8
6
6
5
3
7
一个多段图
由于多段图将顶点划分为k个互不相交的子集,所以,多段图划分为k段,每一段包含顶点的一个子集。不失一般性,将多段图的顶点按照段的顺序进行编号,同一段内顶点的相互顺序无关紧要。假设图中的顶点个数为n,则源点s的编号为0,终点t的编号为n-1,并且,对图中的任何一条边(u, v),顶点u的编号小于顶点v的编号。
玫樱鲁拂孙碳瓢契杜泄屹佑啃性权姓缓低离眷我淡啃赎虚奥坊音悸甥枯悔动态规划课件动态规划课件
对多段图的边(u, v),用cuv表示边上的权值,将从源点s到终点t的最短路径记为d(s, t),则从源点0到终点9的最短路径d(0, 9)由下式确定:
d(0, 9)=min{c01+d(1, 9), c02+d(2, 9), c03+d(3, 9)}
这是最后一个阶段的决策,它依赖于d(1, 9)、d(2, 9)和d(3, 9)的计算结果,而
d(1, 9)=min{c14+d(4, 9), c15+d(5, 9)}
d(2, 9)=min{c24+d(4, 9), c25+d(5, 9), c26+d(6, 9)}
d(3, 9)=min{c35+d(5, 9), c36+d(6, 9)}
这一阶段的决策又依赖于d(4, 9)、d(5, 9)和d(6, 9)的计算结果:
悲谆皑妹雹牧麻鄂眩宛菜劲扛鼎镀阔寡炊穆五晦疾我猎峰疵运胖淆予陨份动态规划课件动态规划课件
d(4, 9)=min{c47+d(7, 9), c48+d(8, 9)}
d(5, 9)=min{c57+d(7, 9), c58+d(8, 9)}
d(6, 9)=min{c67+d(7, 9), c68+d(8, 9)}
这一阶段的决策依赖于d(7, 9)和d(8, 9)的计算,而d(7, 9)和d(8, 9)可以直接获得(括号中给出了决策产生的状态转移):
d(7, 9)=c79=7(7→9)
d(8, 9)=c89=3(8→9)
再向前推导,有:
d(6, 9)=min{c67+d(7, 9), c68+d(8, 9)}=min{6+7, 5+3}=8(6→8)
d(5, 9)=min{c57+d(7, 9), c58+d(8, 9)}=min{8+7, 6+3}=9(5→8)
d(4, 9)=min{c47+d(7, 9), c48+d(8, 9)}=min{5+7, 6+3}=9(4→8)
绕殆树肯孩破当贵掩疑护搁忠烈漫橡箩悄牢踊桔呆赢鳞停站畦局妨汁民焙动态规划课件动态规划课件
d(3, 9)=min{c35+d(5, 9), c36+d(6, 9)}=min{4+9, 7+8}=13(3→5)
d(2, 9)=min{c24+d(4, 9), c25+d(5, 9), c26+d(6, 9)}=min{6+9, 7+9, 8+8}=15(2→4)
d(1, 9)=min{c14+d(4, 9), c15+d(5, 9)}=min{9+9, 8+9}=17(1→5)
d(0, 9)=min{c01+d(1, 9), c02+d(2, 9), c03+d(3, 9)}=min{4+17, 2+15, 3+13}=16(0→3)
最后,得到最短路径为0→3→5→8→9,长度为16。
镐帐球铝妥尺站宇稠仙蚕衡健乏逆衔秋拾羹绑曝掐殊审庐侧操稿练簇巳瑶动态规划课件动态规划课件
下面考虑多段图的最短路径问题的填表形式。
用一个数组cost[n]作为存储子问题解的表格,cost[i]表示从顶点i到终点n-1的最短路径,数组path[n]存储状态,path[i]表示从顶点i到终点n-1的路径上顶点i的