动态规划设计补充部分.pptVIP

　　粗线表示的A→B2→C3→D1→E就是从起点状态A开始的一个策略，而C2→D1→E是从第3阶段C2状态开始的一个子策略。 5. 状态转移方程 　　某一状态以及该状态下的决策，与下一状态之间的函数关系称为状态转移方程，记为sk+1=T(sk,xk)。 k+1阶段的状态等于k阶段某个状态下的决策。 6. 指标函数和最优指标函数 　　指标函数是衡量对决策过程进行控制的效果的数明指标，可以是收益、成本或距离等。 　　从k阶段状态sk出发，选择决策xk所产生的第k阶段指标称为k阶段指标函数，记为vk(sk,xk)。 　　v1(A,AB2)描述了第一阶段在位置状态A的情况下选择AB2路线时，此项决策的优劣，具体来讲v1(A,AB2)=4表示AB2路线的距离为4。 　　从k阶段状态sk出发，选择决策xk、xk+1、…、xn所产生的过程指标，称为k子过程指标函数，记为Vk(sk,xk,xk+1,…,xn)或Vk，这里n为阶段数。 　　从k阶段状态sk出发，对所有的子策略，最优过程对应的指标函数称为最优指标函数（或最优函数），记为fk(sk)，通常取Vk的最大值或最小值。 　　Vk的含义是在状态sk下选择某一条路径到E（决策序列）的距离，如，V2(B2,C1,D2,E)= 　　　　v2(B2,B2C1)+v3(C1,C1D2)+v4(D2,D2E)=3+4+4=11。 最优指标函数是某顶点到终点E的最短距离。 　　动态规划解决问题的关键是将问题归结为一个递推过程，建立一个递推指标函数求最优解，如果不能建立递推函数则动态规划方法无效。 　　动态规划要求子过程指标满足递推关系： Vk(sk,xk,xk+1,…,xn)=Vk[vk(sk,xk),Vk+1(sk+1,xk+1, …,xn)] 　　常用的指标函数有连和形式和连乘形式，其中连和形式为： Vk = Vk(sk,xk,xk+1, …,xn) =vk(sk,xk)+ Vk+1(sk+1,xk+1,…,xn) =　　　　　　 （通常Vn=0） 对应的最优指标函数fk(sk)为： fk(sk)=　　　　　　　　　　　，k=1,2,…,n 　　其中Opt表示最优的意思，通常取“MAX”或“MIN”。上述各式是动态规划的基本方程。为了使递推方程有递推起点，需要确定最后一个状态sn的最优指标fn(sn)的值，称fn(sn)为边界条件。 　　一般地，连和形式时有fn(sn)=0，连乘形式时有fn(sn)=1。 递推指标函数为： Vk=Vk(sk,xk,xk+1, …,xn)=vk(sk,xk)+Vk+1 最优指标函数为： fk(sk)=　　　　　　　　　　　，k=1,2,…,n f5(E)=0 7. 动态规划问题的解法 （1）动态规划问题的逆序解法 　　从E→A的求解过程如下（path存放路径，path1存放最优路径，红色字体表示本次选取的决策）： f4(D1)=MIN{v4(D1，D1E)}=MIN{3+ f5(E)}=3 path41={D1E } f4(D2)=MIN{v4(D2，D2E)}=MIN{4+ f5(E)}=4 path42={D2E } f3(C1)=MIN{v3(C1，C1D1)+ f4(D1)，v3(C1，C1D2)+ f4(D2)} 　　=MIN{3+ f4(D1)，4+ f4(D2)}=MIN{3+3，4+4}=6 path31= path41∪{C1D1}={C1D1，D1E } f3(C2)=MIN{v3(C2，C2D1)+ f4(D1)，v3(C2，C2D2)+ f4(D2)} 　　=MIN{6+ f4(D1)，3+ f4(D2)}=MIN{6+3，3+4}=7 path32= path42∪{C2D2}={C2D2， D2E} f3(C3)=MIN{v3(C3，C3D1)+ f4(D1)，v3(C2，C3D2)+ f4(D2)} 　　=MIN{3+ f4(D1)，3+ f4(D2)} =MIN{3+3，3+4}=6 path33= path41∪{C3D1}={C3D1， D1E} f2(B1)=MIN{v2(B1，B1C1)+ f2(C1)，v2(B1，B1C2)+ f2(C2)} 　　=MIN{7+ f2(C1)，4+ f2(C2)}= =MIN{7+6，4+7}=11 path21= path32∪{B1C1}={B1C2，C2D2， D2E} f2(B2)=MIN{v2(B2，B2C1)+ f2(C1)，v2(B2，B2C2)+ f2(C2)，v2(B2，B2C3)+ f2(C3)} 　　=MIN{3+ f2(C1)，2+ f2(C2)，4+ f2(C3)}=MIN{3+6，2+7，4+6}=9（或B2C2） path22= path31∪{B2C