讨论:1.以上求从A到E的最短路径问题，可以转化为四个性质完全相同，但规模较小的子问题，即分别从D；、Ci、Bi、A到E的最短路径问题。（1）k=4：S4-Dj、Dz，终点只有一个x4-E；表8-1k=4本阶段各终点（决策x4）本阶段始点到E的最短距离本阶段最优终点（状态s4)f4(s4)（最优决策x*)E3ED1344ED2由此可知：从D,和D,到E的最短路径唯一。122024-10-27
2024-10-27 12 讨论： 1. 以上求从A到E的最短路径问题，可以转化为四个性质完 全相同，但规模较小的子问题，即分别从Di 、Ci、Bi、A 到E的最短路径问题。 （1） k=4：s4=D1、D2，终点只有一个x4=E； 表8-1 由此可知：从D1和D2到E的最短路径唯一。 k=4 本阶段始点 （状态s4） 本阶段各终点（决策x4） 到E的最短距离 f4 (s4 ) 本阶段最优终点 （最优决策x* 4 E ) D1 D2 3 4 3 4 E E
（2）k=3：S3=C，C2，C3，Xx3=Di，D2，对始点和终点进行分析和讨论分别求C，C2，C,到D，D,的最短路径问题表8-2k=3本阶段始点本阶段各终点（决策x3）到E的最短距离本阶段最优终点（状态s3)（最优决策x*3)D1D2f3(s3)4D1C11+3=44+4=8C26+3=93+4=77D23+3=63+4=76C3D1由此可知：如果选择状态Cl则本阶段决策为D,;如果选择状态C2.则本阶段决策为D2;如果选择状态C.则本阶段决策为Di。132024-10-27
2024-10-27 13 （2） k=3：s3=C1，C2，C3，x3=D1，D2，对始点和终点进行 分析和讨论分别求C1，C2，C3到D1，D2 的最短路径问题： 表8-2 由此可知：如果选择状态C1，则本阶段决策为D1； 如果选择状态C2，则本阶段决策为D2； 如果选择状态C3，则本阶段决策为D1。 k=3 本阶段始点 （状态s3） 本阶段各终点（决策x3） 到E的最短距离 f3 (s3 ) 本阶段最优终点 （最优决策x* 3 D ) 1 D2 C1 C2 C3 1+3=4 6+3=9 3+3=6 4+4=8 3+4=7 3+4=7 4 7 6 D1 D2 D1