●●● 多段图问题的多阶段决策过程:生成从s到t的最小成本路8。 径是在k-2个阶段(除s和t外)进行某种决策的过程:从s开始,·。。 第i次决策决定V(1sisk-2)中的哪个结点在从s到t的最短路径 上。 最优性原理对多段图问题成立 假设s,v2V3,k1,t是一条由s到t的最短路径。 ●初始状态:s ●初始决策:(s,v2),v2∈V2 ●初始决策产生的状态:V2 则,其余的决策: 35·k1 相对于v2将构成一个最优决策 序列——最优性原理成立 反证:若不然,设v2q3,…,q1t是一条由v2到t的更短的路 径,则s,v2q3,qk1t将是比s,V2V3y,vk1t更短的从s到t的 路径。与假设矛盾。 故,最优性原理成立2021/2/8 多段图问题的多阶段决策过程：生成从s到t的最小成本路 径是在k-2个阶段（除s和t外）进行某种决策的过程：从s开始， 第i次决策决定Vi+1(1≤i≤k-2)中的哪个结点在从s到t的最短路径 上。 ➢最优性原理对多段图问题成立 假设s,v2 ,v3 ,…,vk-1 ,t是一条由s到t的最短路径。 ● 初始状态：s ● 初始决策：(s,v2 )，v2∈V2 ● 初始决策产生的状态：v2 则，其余的决策：v3 ,...,vk-1相对于v2将构成一个最优决策 序列——最优性原理成立。 反证：若不然，设v2 ,q3 ,…,qk-1 ,t是一条由v2到t的更短的路 径，则s, v2 ,q3 ,…,qk-1 ,t将是比s,v2 ,v3 ,…,vk-1 ,t更短的从s到t的 路径。与假设矛盾。 故，最优性原理成立