文档介绍：运筹学第五章动态规划曝臀愿逆节窒猩孰***§2动态规划的最优性原理多阶段决策过程的特点是每个阶段都要进行决策,具有n个阶段的决策过程的策略是由n个相继进行的阶段决策构成的决策序列。由于前阶段的终止状态又是后一阶段的初始状态,因此确定阶段最优决策不能只从本阶段的效应出发,必须通盘考虑,整体规划。就是说,阶段k的最优决策不应只是本阶段的最优,而必须是本阶段及其所有后续阶段的总体最优,即关于整个后部子过程的最优决策。对此,贝尔曼在深入研究的基础上,针对具有无后效性的多阶段决策过程的特点,提出了著名的多阶段决策的最优性原理:“整个过程的最优策略具有这样的性质:即无论过程过去的状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。”简而言之,最优性原理的含意就是:最优策略的任何一部分子策略也必须是最优的。,A—B2—C1—D2—E是由A到E的最短路线,我们在该路线上任取一点C1,按照最优性原理C1—D2—E应该是C1到E的最短路。很容易用反证法证明这一结论的正确性,从而说明最优性原理的正确性。按最优性原理,可以将例1分成A—B—C—D—E4个阶段,由后向前逐步求出各点到E的最短线路,直至求出A至E的最短线路。K=4时,出发点有D1,D2,D3,记f4(Di)(i=1,2,3)为Di到E的最短距离;u4(Di)表示从状态Di出发采取的决策。显然:f4(D1)=7,u4(D1)=Ef4(D2)=8,u4(D2)=Ef4(D3)=6,u4(D3)=EK=3时,出发点有C1,C2,C3f3(C1)=min{d(C1D1)+f4(D1),d(C1D2)+f4(D2)}=min{4+7,2+8}=10,u3(C1)=D2f3(C2)=min{d(C2D2)+f4(D2),d(C2D3)+f4(D3)}=min{5+8,7+6}=13,u3(C2)=D2或D3f3(C3)=min{d(C3D2)+f4(D2),d(C3D3)+f4(D3)}=min{10+8,9+6}=15,u3(C3)==2时,出发点有B1,B2,B3f2(B1)=min{d(B1C1)+f3(C1),d(B1C2)+f3(C2)}=min{6+10,4+13}=16,u2(B1)=C1f2(B2)=min{d(B2C1)+f3(C1),d(B2C3)+f3(C3)}=min{3+10,1+15}=13,u2(B2)=C1f2(B3)=min{d(B3C2)+f3(C2),d(B3C3)+f3(C3)}=min{8+13,4+15}=19,u2(B3)=C3K=1时,出发点只有Ad(AB1)+f2(B1)4+16f1(A)=mind(AB2)+f2(B2)=5+13=18,d(AB3)+f2(B3)3+19u1(A)=B2由f1(A)=18,可知从起点A到终点E的最短距离为18。