最短路问题解法详解：顺序解法

(1)建模。

阶段k:第k个阶段选路的过程,k＝0,1,2,3,4,5。

状态Sk:第k阶段初所处的位置。

决策变量xk:第k阶段选择的路径。

阶段指标Vk:第k阶段所选择的路径相应的路权。

指标函数:Vk(Sk,xk)。

最优函数:fk(Sk)。

动态规划基本方程:

视频-8．2．2最短路动态规划求解-2-顺序解法

(2)求解。

第一步,如图8-8所示,该最短路径问题可划分为六个阶段,边界条件为f0(A)＝0(第0阶段),说明从A点(始点)到A点的最短距离为0。

图8-8

第二步,当k＝1时,状态可能集为S1＝{B1,B2,B3}。如图8-9所示。

图8-9

决策允许集为X1(B)＝{AB1,AB2,AB3}。

最优函数f1(S2)分别为:

对于状态B1,最优函数为f1(B1)＝min{AB1＋f0(A)}＝min{3＋0}＝3,即第二阶段B1状态下的最优策略为A→B1。

对于状态B2,最优函数为f1(B2)＝min{AB2＋f0(A)}＝min{5＋0}＝5,即第二阶段B2状态下的最优策略为A→B2。

对于状态B3,最优函数为f1(B3)＝min{AB3＋f0(A)}＝min{2＋0}＝2,即第二阶段B3状态下的最优策略为A→B3。(www.xing528.com)

第三步,当k＝2时,状态可能集为S2＝{C1,C2}。决策允许集为X2(C1)＝{B1 C1,B2 C1},X2(C2)＝{B2 C2,B3 C2}。如图8-10所示。

图8-10

对于状态C1,最优函数为f2(C1)＝min{B1 C1＋f1(B1),B2 C1＋f1(B2)}＝min{1＋3,4＋5}＝4,即第二阶段C1状态下的最优策略为A→B1→C1。

对于状态C2,最优函数为f2(C2)＝min{B2 C2＋f1(B2),B3 C2＋f1(B3)}＝min{3＋5,3＋2}＝5,即第二阶段C2状态下的最优策略为A→B3→C2。

第四步,当k＝3时,状态可能集为S3＝{D1,D2,D3}。决策允许集为X3(D1)＝{C1 D1},X3(D2)＝{C1 D2,C2 D2},X3(D3)＝{C2 D3}。如图8-11所示。

图8-11

对于状态D1,最优函数为f3(D1)＝min{C1 D1＋f2(C1)}＝min{3＋4}＝7,即第三阶段D1状态下的最优策略为A→B1→C1→D1。

对于状态D2,最优函数为f3(D2)＝min{C1 D2＋f2(C1),C2 D2＋f2(C2)}＝min{2＋4,4＋5}＝6,即第三阶段D2状态下的最优策略为A→B1→C1→D2。

对于状态D3,最优函数为f3(D3)＝min{C2 D3＋f2(C2)}＝min{7＋5}＝12,即第三阶段D3状态下的最优策略为A→B3→C2→D3。

第五步,当k＝4时,状态可能集为S4＝{E1,E2}。决策允许集为X4(E1)＝{D1 E1,D2 E1},X4(E2)＝{D2 E2,D3 E2}。如图8-12所示。

图8-12

对于状态E1,最优函数为f4(E1)＝min{D1 E1＋f3(D1),D2 E1＋f3(D2)}＝min{10＋7,9＋6}＝15,即第四阶段E1状态下的最优策略为A→B1→C1→D2→E1。

对于状态E2,最优函数为f4(E2)＝min{D2 E2＋f3(D2),D3 E2＋f3(D3)}＝min{7＋6,9＋12}＝13,即第四阶段E2状态下的最优策略为A→B1→C1→D2→E2。

第六步,当k＝5时,状态可能集为S5＝{F}。决策允许集为X5(F)＝{E1 F,E2 F}。如图8-13所示。

图8-13

对于状态E1,最优函数为f5(F)＝min{E1 F＋f4(E1),E2 F＋f4(E2)}＝min{12＋15,13＋13}＝26,即第五阶段F状态下的最优策略为A→B1→C1→D2→E2→F。

综上,最优策略为A→B1→C1→D2→E2→F,即最短路径,最短路权为26。

可见,对于最短路问题,逆序解法可以求出各点到目的地的最短路径和路权,顺序解法可以求出始点到各点的最短路径和路权。一般而言,当给定初始状态时,用逆序解法;当给定结束状态时,用顺序解法。