1.把问题划分为几个阶段。本例可把网络按各点位置划分为四个阶段。第一阶段由 A到B1及B2的路线构成,……,第四阶段由D,D2到E的路线构成,如图6-2所示 2.按阶段顺序首先考虑最后阶段即第四阶段的最优决策,也就是走哪条路线最短 先考虑D1,D1到终点E只有一条路线,故D1的最短后都路线就是D→E,最短距离 为8;同样,从D2到E的最短后部路线就是D2→E,最短距离为9。 3.按阶段顺序依次考虑第三、第二,第一阶段的最优决策,为此只需确定每一阶段 上各初始点的最优决策即可。在第三阶段中分别考虑三个点C1,C2和C3的最优决策。 点C后部路线的第一段路线有两种选择.即C1→D和C1→>D2。为了确定C1的最优决 策即确定出对第四阶段的D1,D2的某个选择,应比较由C1分别经过D、D2到E所用 的时间,即比较C,→D的长度与D的最短后部路线长度之和,以及C1→>D,的长度与 D,的最短后部路线的长度之和。前者为3+8=11,后者为6+9=15,取其中较小者为C的 最短后部路线的长度。所以C1的最优决策是下一阶段到达点D,C1的最短后部路线是 C1→D1→E,最短距离为11。用同样的方法求C2的最优决策。由于C2后部路线的第 阶段有两种选择,即C2→>D1,C2→>D2。所以比较C2→>D1的长度与D1的最短后部 路线D1→E的长度之和,以及C2→D2的长度与D2的最短后部路线D2→>E的长度之 和,前者为6+8=14,后者为2+9=11,取其中较小者为11,对应的C2的最优决策是到达 D2,C2的最短后部路线为C2→D2→E,其距离为11。对于C3比较4+8=12及3+9=12 因为二者相等,所以C3的最优决策是到达D及D2均可,C3的最短后部路线可以取其中 任一条,C3→D1→E或C3→D2→E距离都是12 在第二阶段中讨论点B1及B2的最优决策。点B1的后部路线在第一段上有三条,即 B1→C1,B1→C2,B1→C3。而C1,C2,C3各点到终点E的最优决策在第三阶段的 讨论中已确定了。所以比较6+11=17,5+11=16及7+12=19,知三条路线中长度最短者为 16,则B1的最优决策就是由点B1到点C2,点B1的最短后部路线为B1→C2→D2→E, 最短距离为16。点B2的后部路线第一阶段上有三条。比较B2→C1→D1→E B2→C2→D2→E及B2→C3→D1→E(或B2→C3→D2→E)这三条后部路线 的长短,由5+11=16,1+11=12,1+12=13得点B2的最优决策是到点C2,点B2的最短后 部路线为B2→C2→>D2→E,其距离为12。 最后考虑第一阶段,也就是求始点A的最优决策。点可能的决策方案有两个,即到 达B1或B2,而B1及B2两点到终点E的最优决策已在第二阶段确定了,并找到了该两点 之间的最短后部路线,因此我们只需在A→B1→C2→D2→E和 A→B2→C2→D2→E这两条路线中选择点B2,点A的最短后部路线为 A→B2→丶C2→E。至此解题过程结束,整个网络最短路线的决策问题得到解决。从A 到E的最短路线为A→B2→C2→D2→E,最短距离为14。 通过此例的求解过程,可以看到用动态规划方法逐段求解时,每个阶段上的求优方1.把问题划分为几个阶段。本例可把网络按各点位置划分为四个阶段。第一阶段由 A到 B1及 B2的路线构成，……，第四阶段由 D1， D2 到 E 的路线构成，如图 6-2 所示。 2.按阶段顺序首先考虑最后阶段即第四阶段的最优决策，也就是走哪条路线最短。 先考虑 D1， D1到终点 E 只有一条路线，故 的最短后都路线就是 ，最短距离 为 8；同样，从 到 D1 D1 → E D2 E 的最短后部路线就是 D2 → E ，最短距离为 9。 3.按阶段顺序依次考虑第三、第二，第一阶段的最优决策，为此只需确定每一阶段 上各初始点的最优决策即可。在第三阶段中分别考虑三个点C ，C 和C 的最优决策。 点 后部路线的第一段路线有两种选择．即C 和C 。为了确定C 的最优决 策即确定出对第四阶段的 ， 的某个选择，应比较由C 分别经过 、 到 1 D2 2 3 D1 C1 1 → D1 1 → 1 1 D1 D2 D2 E 所用 的时间，即比较 的长度与 的最短后部路线长度之和，以及C 的长度与 的最短后部路线的长度之和。前者为 3+8=11，后者为 6+9=15，取其中较小者为C 的 最短后部路线的长度。所以 的最优决策是下一阶段到达点 ， 的最短后部路线是 ，最短距离为 11。用同样的方法求C 的最优决策。由于C 后部路线的第 一阶段有两种选择，即C ，C 。所以比较C 的长度与 的最短后部 路线 的长度之和，以及C 的长度与 的最短后部路线 的长度之 和，前者为 6+8=14，后者为 2+9=11，取其中较小者为 11，对应的C 的最优决策是到达 ，C 的最短后部路线为C ，其距离为 11。对于C 比较 4+8=12 及 3+9=12， 因为二者相等，所以 的最优决策是到达 及 均可，C 的最短后部路线可以取其中 任一条， 或 距离都是 12。 C1 → D1 C3 D1 → E D1 2 → 2 → → D2 1 E 1 → 2 D2 2 1 → 2 D C D 1 1 D → C → 2 C3 D1 D1 3 C1 2 D1 → E D1 → E 2 C3 → 2 D2 1 D2 1 2 → D D2 2 → D2 D2 E D E 2 → 3 D → 在第二阶段中讨论点 及 的最优决策。点 的后部路线在第一段上有三条，即 ， ， 。而 ， ，C 各点到终点 B1 → C B2 B1 B1 → C1 B1 → C2 B1 3 C1 C2 3 E 的最优决策在第三阶段的 讨论中已确定了。所以比较 6+11=17，5+11=16 及 7+12=19，知三条路线中长度最短者为 16，则 的最优决策就是由点 到点C ，点 的最短后部路线为 ， 最短距离为 16。点 的后部路线第一阶段上有三条。比较 ， 及 （或 ）这三条后部路线 的长短，由 5+11=16，1+11=12，1+12=13 得点 的最优决策是到点 ，点 的最短后 部路线为 ，其距离为 12。 B1 B2 → C2 B1 3 → 2 E B1 B2 B1 → C2 → D2 → E B2 → C1 → D1 → E E C2 B2 B2 B C D2 → D2 → E 2 → C2 → 2 → D1 → → E B2 → C3 → D2 → B 最后考虑第一阶段，也就是求始点 的最优决策。点可能的决策方案有两个，即到 达 或 ，而 及 两点到终点 A B1 B2 B1 B2 E 的最优决策已在第二阶段确定了，并找到了该两点 之间的最短后部路线，因此我们只需在 和 这两条路线中选择点 ， 点 的最短后部路线为 。至此解题过程结束，整个网络最短路线的决策问题得到解决。从 到 A → B1 → C2 → D2 → E A B C2 D2 E A A B C2 → → → E 2 → 2 → → → B2 A E 的最短路线为 A → B2 → C2 → D2 → E ，最短距离为 14。 通过此例的求解过程，可以看到用动态规划方法逐段求解时，每个阶段上的求优方