多段图问题的多阶段决策过程:生成从s到t的最小成本路径是 在k-2个阶段(除s和t外)进行某种决策的过程:从s开始,第i次 决策决定Ⅵ1(1≤si≤k2)中的哪个结点在从s到t的最短路径上。 ★最优性原理对多段图问题成立 假设s,v,v3,…,1,t是一条由s到t的最短路径。 ●初始状态:s 即,是V2的3,,kt构成 ●初始决策:(Ss,V2),v2∈V2 从v2至t的最短路径 ●初始决策产生的状态:v2 则,其余的决策 相对于v2将构成一个最优决策序 列—最优性原理成立 反证:若不然,设V2,q3,…,qk1,t是一条由v2到t的更短的路径, 则s,V2,q3,…,qk1,将是比s,v,v3…,k1,埂更短的从s到t的路径。与 假设矛盾。 故,最优性原理成立 2021/2/202021/2/20 6 多段图问题的多阶段决策过程：生成从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的路径。与 假设矛盾。 故，最优性原理成立 即，是v2 v3 ,...,vk-1 t构成 从v2至t的最短路径