动态规划课件.ppt

第五章动态规划

动态规划算法的设计要素
动态规划算法的典型应用
投资问题;
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的下一个顶点。则:
cost[i]=min{cij+cost[j]} (i≤j≤n且顶点j是顶点i的邻接点)
(式1)
path[i]=使cij+cost[j]最小的j (式2)
算法1——多段图的最短路径
:数组cost[n]初始化为最大值,数组path[n]初始化为-1;
(i=n-2; i>=0; i--)
对顶点i的每一个邻接点j,[i];
[i];
[0];
4. 输出最短路径经过的顶点:
i=0
循环直到path[i]=n-1
输出path[i];