●●●●● ●●●● 52多段图问题 ●●0 ●●● ●●●● 1.问题的描述 在多段图中求从s到t的一条最小成本的路径,可以看作 是在k2个段作出某种决策的结果。 ●第i次决策决定V1中的哪个结点在这条路径上,这里 1≤i≤k-2; ●最优性原理对多段图问题成立 2021/28
2021/2/8 5.2 多段图问题 1. 问题的描述 ● 在多段图中求从s到t的一条最小成本的路径，可以看作 是在k-2个段作出某种决策的结果。 ● 第i次决策决定Vi+1中的哪个结点在这条路径上，这里 1≤i≤k-2； ● 最优性原理对多段图问题成立
2.向前处理策略求解 ●●●●● ●●●● 设P(是一条从中的结点到汇点t的最小成本路径,8 ●●●● coST(j)是这条路径的成本。 1向前递推式 COST(i,j=min C, D)+COsT(i+l,7) ∈v 2)递推过程 (j,)∈E ★第k-1段 c1)<t>∈E COST(k-1,1) ∞<j,t>∈E ★j∈Vk2计算cosT(k-2j)=min{c()+cost(k-1, ★CoST(1,S) ∈vk=1 <jl>∈E(G) 2021/28
2021/2/8 2. 向前处理策略求解 设 P(i,j)是一条从Vi中的结点j到汇点t的最小成本路径， COST(i,j)是这条路径的成本。 1) 向前递推式 2) 递推过程 ★ 第k-1段 c(j,t) <j,t>∈E COST(k-1,j) = ∞ ★ j∈VK-2计算COST(k-2,j)=min{c(j,l)+cost(k-1,l)} ★ COST(1,S) ( , ) min { ( , ) ( 1, )} ( , ) 1 COST i j c j l COST i l j l E l vi = + + + j,t E , ( ) 1 j l E G l vk −
●●●●● ●●●● ●●0 ●●● ●●●● 2 Pi+ 2021/28
2021/2/8 l 1 l 2... l pi+1 … t j V i Vi+1
●●●●● ●●●● ●●0 ●●● ●●●● 5 6 10 8 5段图 2021/28
2021/2/8 1 2345 678 9 10 11 12 9732 4 2 2 7 11 11 8 1 4 563 5 6 425 V 1 V 2 V 3 V 4 V 5 5段图
★各递推结果 第4段cosT(429)=c(9,12)=4 ●●●●● ●●●● ●●0 cosT(4,10)=c(10,12)=2 ●●● ●●●● cOsT(4,11)=c(1112)=5 #3# COST(3, 6 )=min (6+COST(4, 9), 5+COST(4, 10)1-7 cosT(3,7)=min{4+cosT(4,9),3+c0sT(4,10}=5 cOsT(3,8)=min{5+COsT(4,10),6+CosT(4,11)}=7 第2段cosT(2,2)=min{4coST(3,6),2+c0ST(3,7), 1+cosT(38)}=7 cosT(2,3)=9 cosT(2,4)=18 cosT(2,5)=15 第1段cosT(1,1)=min{9+cosT(2,2)7+coST(2,3) 3+cosT(24),2+cosT(25) =16 S到t的最小成本路径的成本=16 2021/28
2021/2/8 ★各递推结果 第4段 COST(4,9) = c(9,12) = 4 COST(4,10) = c(10,12) = 2 COST(4,11) = c(11,12) = 5 第3段 COST(3,6) = min{6+COST(4,9),5+COST(4,10)} = 7 COST(3,7) = min{4+COST(4,9),3+COST(4,10)} = 5 COST(3,8) = min{5+COST(4,10),6+COST(4,11)} = 7 第2段 COST(2,2) = min{4+COST(3,6) , 2+COST(3,7), 1+COST(3,8)} = 7 COST(2,3) = 9 COST(2,4) = 18 COST(2,5) = 15 第1段 COST(1,1) = min{9+COST(2,2),7+COST(2,3), 3+COST(2,4),2+COST(2,5)} = 16 S到t的最小成本路径的成本 ＝ 16