例4.1.1中，若A到B1到C2到D1到E2到F2到G是A到G的最短路线，则D1到E2到F2到G应 是由D,到G的所有可能选择的不同路线中的最短路线。（反证） 根据最短路线的特性，寻找最短路线的方法，就是从最后一段开始，用由后向前逐步递推的方法， 求出各点到G点的最短路线，最后求得由A到G的最短路线。 所以，动态规划的方法是从终点逐段向始点方向寻找最短路线的一种方法。 下面按照动态规划的方法，将例4.1.1从最后一段开始计算，由后向前逐步推移至A点。 k-6时，由F1到G只有一条路线，故f6F)=4,f6(F2=3,6(F1):→G,6(F2:→G。 =5时，出发点E1,E2,E3三个。若从点E1出发，则有→F1,→F2,则 f5(E1=min{d(E1,F)+f6(Fi),d(Ei,F2tf6(F2)}=min{3+4,5+3}=7 其相应的决策为us(E)上→F1,这说明E1到终点G的最短距离为7，最短路线E,到F到G。 同理，从E2,E3出发有： Fs(E2=min{d(E2,Fi+f6(Fi),d(E2,F2+f6(F2)}=min{3+4,2+3=5 其相应的决策为u(E2):一F2, Fs(E3)=min{d(E3,Fitf6(F),dE3,F2)+f6F2)}=min{6+4,6+3}=9 且us(E):→F2。 类似地： k=4时，f4(DF7,4(D)→E2,f4D2F6,4(D2):→E2,fD3=8,4(D3→E2。 k=3时，(C1=13,(C1)→D1,f(C2)=10,s(C2:→D1,f(C3=9,s(C3:→D2,(C4)=12,u3(C4:→D3。 k=2时，(B1尸13,2(B1):→C2,(B2)尸16,2(B2)→C3。 k=1时，f(4)=min{d(A,Btf(B1),d(A,B2tf5(B2)}=min{5+13,3+16}=18,(A):→B1。 于是从起点A到终点G的最短距离为18。 为寻找最短路线，再按计算的顺序反推之，求得最优决策函数序列{；，即 u1(A):→B1,u2(B1):→C2,u(C2:→D1,4(D1→E2,us(E2:→F2,6(F2):→G 组成一个最优策略，最短路线为：A到B1到C2到D到E2到F2到G。 从上面的计算过程可以看出，在求解的各个阶段，利用k阶段与+1阶段之间的递推关系： fs)=4R(4)+f(T,4},k=5,43,2,1 f6(S6)=v(s6,→G)=d(s6,G) 一般情况下，k阶段与+1阶段的递推关系式可写为： [f(s)=opt{y(sk,44)+f+(T(s,4)},k=n-1,…,1 (s) (4.2.1) f(s)=opt v(su) u.EU(sn） 即 f(s)=opI{v(,4s)+f(T(s,4a},k=n,…,1 4Ek(级) (4.2.2) (S)=0 递推关系(4.2.1)和(4.2.2)称为动态规划的基本方程。 递推关系(4.2.1)和(4.2.2)中，相应的最优解即为最优决策4，(S)。 2.动态规划方法的基本思想 (1)动态规划方法的关键在于写出基本的递推关系式和恰当的边界条件（简言之为基本方程）。4 例 4.1.1 中，若 A 到 B1到 C2 到 D1到 E2 到 F2到 G 是 A 到 G 的最短路线，则 D1 到 E2 到 F2 到 G 应 是由 D1 到 G 的所有可能选择的不同路线中的最短路线。（反证） 根据最短路线的特性,寻找最短路线的方法，就是从最后一段开始，用由后向前逐步递推的方法， 求出各点到 G 点的最短路线，最后求得由 A 到 G 的最短路线。 所以，动态规划的方法是从终点逐段向始点方向寻找最短路线的一种方法。 下面按照动态规划的方法，将例 4.1.1 从最后一段开始计算，由后向前逐步推移至 A 点。 k=6 时，由 F1 到 G 只有一条路线，故 f6(F1)=4，f6(F2)=3，u6(F1)：→G，u6(F2)：→G。 k=5 时，出发点 E1，E2，E3 三个。若从点 E1 出发，则有→F1，→F2，则 f5(E1)=min{d(E1, F1)+ f6(F1), d(E1, F2)+ f6(F2)}=min{3+4, 5+3}=7 其相应的决策为 u5(E1)= →F1，这说明 E1 到终点 G 的最短距离为 7，最短路线 E1 到 F1到 G。 同理，从 E2, E3 出发有： F5(E2)=min{d(E2, F1)+ f6(F1), d(E2, F2)+ f6(F2)}=min{3+4, 2+3}=5 其相应的决策为 u5(E2):→ F2， F5(E3)=min{d(E3, F1)+ f6(F1),d(E3, F2)+ f6(F2)}=min{6+4, 6+3}=9 且 u5(E3):→ F2。 类似地： k=4 时, f4(D1)=7，u4(D1):→ E2，f4(D2)=6，u4(D2):→ E2，f4(D3)=8，u4(D3):→ E2。 k=3 时, f3(C1)=13，u3(C1):→D1，f3(C2)=10，u3(C2):→ D1，f3(C3)=9，u3(C3):→D2，f3(C4)=12，u3(C4):→D3。 k=2 时, f2(B1)=13，u2(B1):→C2，f2(B2)=16，u2(B2):→C3。 k=1 时, f1(A)=min{d(A, B1)+f2(B1), d(A, B2)+f2(B2)}=min{5+13, 3+16}=18，u1(A):→ B1。 于是从起点 A 到终点 G 的最短距离为 18。 为寻找最短路线，再按计算的顺序反推之，求得最优决策函数序列{uk}，即 u1(A):→ B1，u2(B1):→C2，u3(C2):→D1，u4(D1):→E2，u5(E2):→ F2，u6(F2):→G 组成一个最优策略，最短路线为：A 到 B1 到 C2到 D1 到 E2到 F2 到 G。 从上面的计算过程可以看出，在求解的各个阶段，利用 k 阶段与 k+1 阶段之间的递推关系： 1 ( ) 66 66 6 ( ) min { ( , ) ( ( , ))}, 5,4,3,2,1 () (, ) (,) k kk kk kk k k kk k uUs fs vsu f Tsu k f s v s G ds G + ∈ ⎧ =+ = ⎪ ⎨ ⎪⎩ = →= 一般情况下，k 阶段与 k+1 阶段的递推关系式可写为： 1 ( ) ( ) ( ) { ( , ) ( ( , ))}, 1, ,1 ( ) { ( , )} k kk n nn kk kk k k k k uUs nn nn n uUs f s opt v s u f T s u k n f s opt v s u + ∈ ∈ ⎧ = + =− ⎪ ⎨ = ⎪ ⎩ " (4.2.1) 即 1 ( ) 1 1 ( ) { ( , ) ( ( , ))}, , ,1 ( )0 k kk kk kk k k k k uUs n n f s opt v s u f T s u k n f s + ∈ + + ⎧ =+ = ⎪ ⎨ ⎪⎩ = " (4.2.2) 递推关系(4.2.1)和(4.2.2)称为动态规划的基本方程。 递推关系(4.2.1)和(4.2.2)中，相应的最优解即为最优决策 ( ) k k u s 。 2. 动态规划方法的基本思想 （1）动态规划方法的关键在于写出基本的递推关系式和恰当的边界条件（简言之为基本方程）