多段图问题的多阶段决策过程:生成从s到t的最小成本路径是 在k-2个阶段(除s和t外)进行某种决策的过程:从s开始,第i次 决策决定Ⅵ1(1≤si≤k2)中的哪个结点在从s到t的最短路径上。 ★最优性原理对多段图问题成立 假设s,v,v3,…,1,t是一条由s到t的最短路径。 ●初始状态:s 即,是V2的3,,kt构成 ●初始决策:(Ss,V2),v2∈V2 从v2至t的最短路径 ●初始决策产生的状态:v2 则,其余的决策 相对于v2将构成一个最优决策序 列—最优性原理成立 反证:若不然,设V2,q3,…,qk1,t是一条由v2到t的更短的路径, 则s,V2,q3,…,qk1,将是比s,v,v3…,k1,埂更短的从s到t的路径。与 假设矛盾。 故,最优性原理成立 2021/2/20
2021/2/20 6 多段图问题的多阶段决策过程：生成从s到t的最小成本路径是 在k-2个阶段（除s和t外）进行某种决策的过程：从s开始，第i次 决策决定Vi+1(1≤i≤k-2)中的哪个结点在从s到t的最短路径上。 ★ 最优性原理对多段图问题成立 假设s,v2 ,v3 ,…,vk-1 ,t是一条由s到t的最短路径。 ● 初始状态：s ● 初始决策：(s,v2 )， v2∈V2 ● 初始决策产生的状态：v2 则，其余的决策：v3 ,...,vk-1相对于v2将构成一个最优决策序 列——最优性原理成立。 反证：若不然，设v2 ,q3 ,…,qk-1 ,t是一条由v2到t的更短的路径， 则s, v2 ,q3 ,…,qk-1 ,t将是比s,v2 ,v3 ,…,vk-1 ,t更短的从s到t的路径。与 假设矛盾。 故，最优性原理成立 即，是v2 v3 ,...,vk-1 t构成 从v2至t的最短路径
例4.2[0/1背包问题]KNAP(1,X) 日标函数:∑Px 1≤i 约束条件 ∑mx≤X k<i< x1=0或1,p>0,11>0,1≤i≤j 0/1背包间题:KNAP(1,n,M) 2021/2/20
2021/2/20 7 ◼例4.2[0/1背包问题] KNAP(1,j,X) 目标函数： 约束条件： 0/1背包问题：KNAP(1,n,M) i j i i p x 1 x p w i j w x X i i i i j i i = 0 1, 0, 0,1 1 或
★最优性原理对01背包问题成立: 设y1,y2yn是x,x2,x的0/1值最优序列。 ●初始状态:KNAP(1n,M) ●初始决策:决定y等于1还是等于0 ★若y1=0,KNAP(2,n-1,M是初始决策产生的状态。则y2yn相 对于KNAP(2n-1,M)将构成一个最优序列。否则,y1y2…yn将不是 KNAP(1,n,M)的最优解 ★若y1=1,KNAP(2n-1,MW1)是初始决策产生的状态。则y2yn相 对于KNAP(2n-1,M-W)将构成一个最优序列 如若不然,设存在另一0序列z2,z3,…,z乙n,使得 且∑p,≥∑PB∑mE≤M-m 2≤i≤n 2<i<n 则序列y1,z2,,zn将是一个对于KNAP(1n,M)具有更大效益值得序列。 与假设矛盾 故,最优性原理成立 2021/2/20
2021/2/20 8 ★ 最优性原理对0/1背包问题成立： 设y1 ,y2 ,…,yn是x1 ,x2 ,…,xn的0/1值最优序列。 ●初始状态： KNAP(1,n,M) ●初始决策：决定y1等于1还是等于0 ★ 若y1＝0, KNAP(2,n-1,M)是初始决策产生的状态。则y2 ,…,yn相 对于KNAP(2,n-1,M)将构成一个最优序列。否则，y1 ,y2 ,…,yn将不是 KNAP(1,n,M)的最优解 ★若y1＝1, KNAP(2,n-1,M-w1 )是初始决策产生的状态。则y2 ,…,yn相 对于KNAP(2,n-1,M－w1 )将构成一个最优序列。 如若不然，设存在另一0/1序列z2 ,z3 ,…,zn ,使得 且 则序列y1 ,z2 ,…,zn将是一个对于KNAP(1,n,M)具有更大效益值得序列。 与假设矛盾。 故，最优性原理成立 − i n wi zi M w 2 1 i n i n i i i i p z p y 2 2
4.最优决策序列的表示 设 就一个特定的 ●S0:问题的初始状态 r1,n1而言 ●n次决策:问题需要做nη次决策 ●x:昕阶段的决策值,1≤i≤n 设X1=r1,r1,2,……,r,n}是x可选决策值的集合,S1,n是在选择 决策值r1,n之后所产生的状态——“初始决策”所产生的状态 设1,j1是相应于状态S1,j的最优决策序列。 则,相应于S0的最优决策序列就是{r1iT1,n1≤j1≤p1中最优的 序列,记为 OP7,11,}=I 1≤/1≤P1 2021/2/20
2021/2/20 9 4. 最优决策序列的表示 设 ● S0：问题的初始状态 ● n次决策：问题需要做n次决策 ● xi：i阶段的决策值，1≤i≤n。 设X1={r1,1,r1,2,…,r1,p1}是x1可选决策值的集合，S1,j1是在选择 决策值r1,j1之后所产生的状态——“初始决策”所产生的状态。 设Γ1,j1是相应于状态S1,j1的最优决策序列。 则，相应于S0的最优决策序列就是{r1,j1Γ1,j1|1≤j1≤p1}中最优的 序列，记为 1, 1, 1 1 1 { } 1 1 1 1 = OPT r r j j j p 就一个特定的 r1,j1而言
r 1,2 「 n 1J1 1p1 2021/2/20 10
2021/2/20 10 s0 r1,1 r1,2... r1,p1 sn Γ1,j1 Γ1,1 Γ1,2 Γ1p1