10 12 A B2 18 在第一阶段,A为起点,终点有B1,B2,B3三个,因而这时走的路线有三个选择, 分别是走B1,B2,B3 如果选择走B2的决策,则B2就是第一阶段在我们决策之下的结果.它既是第一阶段 路线的终点,又是第二阶段路线的始点。 在第二阶段,再从B2点出发,对应于B2点就有一个可供选择的终点集合{C1,C2 C3}; 如果选择由B2走至C2为第二阶段的决策,则C2就是第二阶段的终点,同时又是第三 阶段的始点 同理递推下去,可看到:各个阶段的决策不同,调运的路线就不同.很明显,当某 阶段的始点给定时,它直接影响着后面各阶段的行进路线和整个路线的长短,而后面各阶
在第一阶段，A为起点，终点有B1，B2，B3三个，因而这时走的路线有三个选择， 分别是走B1，B2，B3。 如果选择走B2的决策，则B2就是第 一阶段在我们决策之下的结果．它既是第一阶段 路线的终点，又是第二阶段路线的始点。 在第二阶段，再从B2点出发，对应于B2点就有一个可供选择的终点集合{C1，C2， C3}； 如果选择由B2走至C2为第二阶段的决策，则C2 就是第二阶段的终点，同时又是第三 阶段的始点． 同理递推下去，可看到：各个阶段的决策不同，调运的路线就不同．很明显，当某一 阶段的始点给定时，它直接影响着后面各阶段的行进路线和整个路线的长短，而后面各阶 段的路线的发展不受这点以前各阶段路线的影响．故此问题的要求是：在各个阶段选取一 A B2 C2 E B1 B3 C1 C3 D1 D2 4 3 5 8 10 12 14 18 10 12 9 4 5 8 9 7 7 3 4 11
10 12 A B2 18 如何解决这个问题呢? 可以采取穷举法.即把由A到E所有可能的每一条路线的距离都算出来,然后互相比 较找出最短者,相应地得出了最短路线.这样,由A到E一共有3X3X2Ⅹ1=18条不同的 路线,比较这18条不同的路线的距离值,才找出最短路线 显然,这样作计算是相当繁的.如果当段数很多,各段的不同选择也很多时,这种解 法的计算将变得极其繁杂,甚至在电子计算机上计算都是不现实的
如何解决这个问题呢? 可以采取穷举法．即把由A到E所有可能的每一条路线的距 离都算出来，然后互相比 较找出最短者，相应地得出了最短路线．这样，由A到E一共有3 X 3 X 2 X 1＝18条不同的 路线，比较这18条不同的路线的距离值，才找出最短路线。 显然，这样作计算是相当繁的．如果当段数很多，各段的不同选择也很多时，这种解 法的计算将变得极其繁杂，甚至在电子计算机上计算都是不现实的． A B2 C2 E B1 B3 C1 C3 D1 D2 4 3 5 8 10 12 14 18 10 12 9 4 5 8 9 7 7 3 4 11
2用动态规划的方法来求解以上最短路间题 (1) 顺序 16N解法 12 A 3(B2) E 18 E地 A地 B地 C地 D地 求解得到的结果内容丰
A B2 C2 E B1 B3 C1 C3 D1 D2 4 3 5 8 10 12 14 18 10 12 9 4 5 8 9 7 7 3 4 11 12 0 4 3 5 14 14 16 17 19 2 用动态规划的方法来求解以上最短路问题 B 地 C 地 D 地 E 地 A 地 （1） 顺序 解法 求解得到的结果内容丰富
(2) 逆序 3解法 12 0 E 18 l0′ D地 A地 E地 B地 C地
（ 2 ） 逆序 解法 A B2 C2 E B1 B3 C1 C3 D1 D2 4 35 8 10 12 14 18 10 12 9 4 5 8 97 7 34 11 0 B 地 C 地 D 地 E 地 A 地 34 7 11 10 15 18 19 19
3动态规划的基本概念 8 1O 12 (1)阶段 把所给问题的过程,恰当地分为若干个相互联系的阶段,以便能按一定的次序去 求解 阶段的划分,一般是根据时间和空间的自然特征来划分。 描述阶段的变量称为阶段变量,常用k表示.如例1可分为4个阶段来求解,k=1、2、 3、4
3 动态规划的基本概念 (1)阶段 把所给问题的过程，恰当地分为若干个相互联系的阶段，以便能按一定的次序去 求解． 阶段的划分，一般是根据时间和空间的 自然特征来划分。 描述阶段的变量称为阶段变量，常用 k 表示．如例1可分为4个阶段来求解，k＝1、2、 3、4。 A B2 C2 E B1 B3 C1 C3 D1 D2 4 3 5 8 10 12 14 18 12 10 9 4 5 8 9 7 7 3 4 11