f(C2)=min{3(C2,D1)+f(D)d3(C2,D2)+/(D2)=min6+82+9=11 其最短距离是1,其路线是C2→D2→>E 决策为x3(C2)=D 对点C3有 f(C3)=min{3(C3,D)+f4(D1)d2(C3,D2)+f(D2)=mn4+8,3+9}=12 点C3到E的最短距离是12,其路线可有两条:C3→>D1→>E,C3→>D2→E,决 策为x3(C3)=D1或x3(C3)=D2均可 k=2时,考虑两点B1,B2到终点的最短距离/2(s2),对点B1有 f2(B1)=min{a2(B,C1)+f(C1)d2(B1,C2)+f3(C2)d3(B1,C3)+f(C3) =min6+115+117+12}=16 则最短路线为B1→C2→D1→E,且x2(B1)=C2 从点B2出发,有 f2(B2)=min{a2(B2,C1)+f(C1)d2(B2,C2)+f3(C2)d(B2,C)+f(c3) =min5+11112}=12 则最短路线为B2→C2→D1→E,x2(B2)=C2 k=1时,考虑始点E的最短距离f(s1),有 f(A)=min(4(A,B)+f2(B)d1(A,B2)+f2(B2)}=min3+162+12}=14 所以,始点A决策为x1(4)=B2,最短距离为14,其路线为A→B2→C2→D2→>E。 整个迭代过程至此结束。 最后,可按计算顺序反推,得最优的决策序列x1(4)=B2,x2(B2)=C2,x3(C2)=D1, x:(C1)=E构成了本问题的最优策略 用数学模型(6-5)直接求解,由于数学公式中符号抽象,所以容易出错。下面再 介绍两种较为形象、直观和简捷的计算方法,成为标号法和表格求解法。这两种方法都 是根据动态规划的求优原则由递推公式 (6-5)演化而来 6.3.2动态规划的网络标号法 网络标号法就是直接在网络图上进行 计算的方法,现在仍通过求解例1种网络 最短路线来阐述 例6.4设有一个网络线路(图6-2), 试用标号法求出由A到E的最短路线。 图6-5f3 (C2 ) = min{ } d3 ( ) C2 , D1 + f 4 (D1 ),d3 (C2 , D2 ) + f 4 (D2 ) = min{6 + 8,2 + 9} = 11 其最短距离是 11，其路线是C2 → D2 → E ， 决策为 3 2 1 x (C ) = D 对点C3有 f3 (C3 ) = min{ } d3 ( ) C3 , D1 + f 4 (D1 ),d3 (C3 , D2 )+ f 4 (D2 ) = min{4 + 8,3 + 9}= 12 点C3到 E 的最短距离是 12，其路线可有两条：C ，C ，决 策为 或 均可。 3 → D1 → E 3 → D2 → E 3 1 x ) 3 (C = D 3 3 2 x (C ) = D k = 2 时，考虑两点 B1， B2到终点的最短距离 f 2 (s2 ) ，对点 B1有 { ( ) ( ) ( ) ( ) ( ) ( )} min{ } 6 11,5 11,7 12 16 ( ) min , , , , , 2 1 2 1 1 3 1 2 1 2 3 2 3 1 3 3 3 = + + + = f B = d B C + f C d B C + f C d B C + f C 则最短路线为 B1 → C2 → D1 → E ，且 2 1 2 x (B ) = C 从点 B2出发，有 { ( ) ( ) ( ) ( ) ( ) ( )} min{ } 5 11,1 11,1 12 12 ( ) min , , , , , 2 2 2 2 1 3 1 2 2 2 3 2 3 2 3 3 3 = + + + = f B = d B C + f C d B C + f C d B C + f C 则最短路线为 B2 → C2 → D1 → E ， 2 2 2 x (B ) = C k = 1时，考虑始点 E 的最短距离 f1 (s1 )，有 ( ) min{ } ( ) , ( ), ( , ) ( ) min{3 16,2 12} 14 f1 A = d1 A B1 + f 2 B1 d1 A B2 + f 2 B2 = + + = 所以，始点 决策为 ，最短距离为 14，其路线为 。 整个迭代过程至此结束。 A 1 2 x (A) = B A → B2 → C2 → D2 → E 最后，可按计算顺序反推，得最优的决策序列 1 2 x (A) = B ，x ，x 2 2 2 (B ) = C 3 2 1 (C ) = D ， x4 (C1 ) = E 构成了本问题的最优策略。 用数学模型（6-5）直接求解，由于数学公式中符号抽象，所以容易出错。下面再 介绍两种较为形象、直观和简捷的计算方法，成为标号法和表格求解法。这两种方法都 是根据动态规划的求优原则由递推公式 （6-5）演化而来。 图 6-5 C3 D2 C2 B2 E D1 3 B1 1 5 2 1 3 9 8 5 7 6 6 2 4 A C1 3 6 6.3.2 动态规划的网络标号法 网络标号法就是直接在网络图上进行 计算的方法，现在仍通过求解例 1 种网络 最短路线来阐述。 例 6.4 设有一个网络线路（图 6-2）， 试用标号法求出由 A到 E 的最短路线