例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)动态规划方法的关键在于写出基本的递推关系式和恰当的边界条件(简言之为基本方程)