7最优策略和最优轨线 使指标函数Vk,n达到最优值的策略是从k开始的 后部子过程的最优策略，记作pk,n*={uk*,un*,P1,n 又是全过程的最优策略，简称最优策略(optimal policy)。从初始状态x1(=x1*)出发，过程按照p1,n*和 状态转移方程演变所经历的状态序列{X*,X2*,,×+*) 称最优轨线(optimal trajectory)。 2023/4/28
2023/4/28 7.最优策略和最优轨线 使指标函数Vk,n达到最优值的策略是从k开始的 后部子过程的最优策略，记作pk,n*={uk *,..un *},p1,n * 又是全过程的最优策略，简称最优策略(optimal policy)。从初始状态x1 (=x1 *)出发，过程按照p1,n *和 状态转移方程演变所经历的状态序列{x1 *,x2 *,..,xn+1*} 称最优轨线(optimal trajectory)
5.递推策略 1)向前处理法 列出根据X+1,,X的最优决策序列求取x决策 值的关系式。 从最后一个阶段，逐步向前递推求出各阶段的 决策值。决策序列x1,X2,,X就是问题的最优解。 Xn-1,1 Xn Xn-1.Pn-1 2023/4/28
2023/4/28 5. 递推策略 1）向前处理法 列出根据xi+1,…,xn的最优决策序列求取xi决策 值的关系式。 从最后一个阶段，逐步向前递推求出各阶段的 决策值。决策序列x1 ,x2 ,…,xn就是问题的最优解。 xn-1,1 … xn-1,pn-1 xn
例5.3利用向前处理法求解0/1背包问题 设g(x)是KNAP(i+1,n,X)的最优解。 ● gMW):KNAP(1,n,M)的最优解。由于x的取值等于1 或0，可得： go(M)=max{g (M),g(M-w1)+p} ●对于某个x,x等于1或0，则有： gi(X)=maxtgi+1(X),gi+1(X-Wi+)+pi+1) 初始值： 1X≥0 gn(X)= -∞X<0 2023/4/28
2023/4/28 例5.3 利用向前处理法求解0/1背包问题 设gi (x)是KNAP(i+1,n,X)的最优解。 ● g0 (M)：KNAP(1,n,M)的最优解。由于x1的取值等于1 或0,可得： g0 (M)=max{g1 (M),g1 (M-w1)+p1 } ● 对于某个xi，xi等于1或0，则有： gi (X)=max{gi+1(X),gi+1(X-wi+1)+pi+1} 初始值： 0 X≥0 gn (X) = -∞ X＜0
例5.4利用向前处理法求解k段图问题 设V2.后V,1S1zpV以=p2i 工，2是由V2.到t的最短路径，则s到t的最短路径是 2,j2 s「，后V,1,sp中最短的那条路径。 2,j2 若S,V2,V3,,V,Vk-1,t是s到t的一条最短路径，V是其中的一 个中间点，则s,V2,V3,,V和V,Vk-1t分别是由s到V和v到t的最 短路径（最优性原理） 从V中的结点到t的最短路径将是： min,Ty Vs后vn1l.p》 2023/4/28
2023/4/28 例5.4 利用向前处理法求解k段图问题 设 ∈V2，1≤j2≤p2 ,|V2 |=p2 ; 是由 到t的最短路径，则s到t的最短路径是 {s | ∈V2 ,1≤j2≤p2 }中最短的那条路径。 若s,v2 ,v3 ,…,vi ,…,vk-1 ,t是s到t的一条最短路径，vi是其中的一 个中间点，则s,v2 ,v3 ,…,vi和 vi ,…,vk-1 ,t分别是由s到vi和vi到t的最 短路径（最优性原理） 从Vi中的结点j i到t的最短路径将是： min( { | ∈Vi+1,1≤ji+1≤pi+1}) 2, j 2 v 2 2, j v 2 2, j v 2, j 2 v 2 2, j v 1 +1, + i i j v 1 1, + i+ i j v i i j v
2)向后处理法 列出根据x1,,X1的最优决策序列求取X决策 值的关系式。 从第一个阶段，逐步向后递推求出各阶段的 决策值。决策序列X1,x2,,X就是问题的最优解。 2023/4/28
2023/4/28 2） 向后处理法 列出根据x1 ,…,xi-1的最优决策序列求取xi决策 值的关系式。 从第一个阶段，逐步向后递推求出各阶段的 决策值。决策序列x1 ,x2 ,…,xn就是问题的最优解