●●●●● ●●●● 7最优策略和最优轨线 ●●0 ●●● ●●● 使指标函数vn达到最优值的策略是从k开始的 又是全过程的最优策略,简称最优策略(○pmn 后部子过程的最优策略,记作pκn*{uk*,Unp policy)。从初始状态x1(=x1)出发,过程按照p1n*和 状态转移方程演变所经历的状态序列{x1*,x2*,xn+1 称最优轨线( optimal trajectory) 2021/2/8
2021/2/8 7.最优策略和最优轨线 使指标函数Vk,n达到最优值的策略是从k开始的 后部子过程的最优策略，记作pk,n*={uk *,..un *},p1,n * 又是全过程的最优策略，简称最优策略(optimal policy)。从初始状态x1 (=x1 *)出发，过程按照p1,n *和 状态转移方程演变所经历的状态序列{x1 *,x2 *,..,xn+1*} 称最优轨线(optimal trajectory)
●●●●● 5.递推策略 ●●●● ●●0 ●●● 1)向前处理法 ●●●● 列出根据X1+…,xn的最优决策序列求取X决策 值的关系式。 从最后一个阶段,逐步向前递推求出各阶段的 决策值。决策序列κ1x2…,xn就是问题的最优解。 n-11 ■■ n n-1.n-1 2021/2/8
2021/2/8 5. 递推策略 1）向前处理法 列出根据xi+1,…,xn的最优决策序列求取xi决策 值的关系式。 从最后一个阶段，逐步向前递推求出各阶段的 决策值。决策序列x1 ,x2 ,…,xn就是问题的最优解。 xn-1,1 … xn-1,pn-1 xn
●●●●● 例53利用向前处理法求解01背包问题 ●●●● ●●0 ●●● 设g(x)是KNAP(+1,n,X)的最优解。 ●●●● g0M):KNAP(1,n,M)的最优解。由于x的取值等于1 或0,可得: go(M)=maxg,M), g,M-w1)+p,1 ●对于某个X,x等于1或0,则有 g (X)=maxigi+1 X), g+1(X-Wi+1)+p +11 初始值: 0X≥0 gn×)=〈 0X<0 2021/28
2021/2/8 例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
例54利用向前处理法求解k段图问题 ●●●●● ●●●● ●●0 ●●● 设v,∈V2,1S2sp2V2|=P2 ●●●● I.是由ψ到t的最短路径,则s到t的最短路径是 sI|v2EV212p2中最短的那条路径。 若s,V2,V3y…v1,Vk1t是s到t的一条最短路径,是其中的 个中间点,则s,V2V3,和vp…vk1t分别是由s到v和V到t的最 短路径(最优性原理) 从v中的结点到t的最短路径将是: min(v r i+1 ∈V+1S+p+1) Ji+ 2021/2/8
2021/2/8 例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
●●●●● ●●●● ●●0 ●●● 2)向后处理法 ●●●● 列出根据x1…,X1的最优决策序列求取x决策 值的关系式。 从第一个阶段,逐步向后递推求出各阶段的 决策值。决策序列κ1x2…,xn就是问题的最优解。 2021/2/8
2021/2/8 2） 向后处理法 列出根据x1 ,…,xi-1的最优决策序列求取xi决策 值的关系式。 从第一个阶段，逐步向后递推求出各阶段的 决策值。决策序列x1 ,x2 ,…,xn就是问题的最优解