算法設(shè)計與分析 課件 第六章 回溯法6.3.1 飼料投喂問題 -算法改進

計算機算法設(shè)計與分析第6章回溯法6.3.1飼料投喂問題---算法改進給定任意狀態(tài)[x1，x2，...，xk]，怎么來判斷其子結(jié)點是否可能得出最優(yōu)解？ABCx1，x2，...，xk，1x1，x2，...，xk，0x1x1，x2，...，xk進入左分支結(jié)點B，xk+1=1,設(shè)cw=,若cw+wk+1>C用約束函數(shù)對A的左分支進行剪枝處理算法改進給定任意狀態(tài)[x1，x2，...，xk]，怎么來判斷其子結(jié)點是否可能得出最優(yōu)解？ABCx1，x2，...，xk，1x1，x2，...，xk，0x1x1，x2，...，xk進入結(jié)點A的右分支結(jié)點C，xk+1=0，cw≤C,總是可行右分支上的投喂可能的最大產(chǎn)奶量為cv+若cv+<=bestv,不可能是最優(yōu)解，可剪枝飼料余量為C-cw，后續(xù)奶牛的產(chǎn)奶量為算法改進現(xiàn)在的問題是

如何計算？這部分是還沒有考慮投喂的奶牛最大產(chǎn)奶量，屬于未知的，所以僅對其上限進行粗略的評估。算法改進常用的評估方法為=在不考慮現(xiàn)有飼料余量的情況下，后面的奶牛全部產(chǎn)奶的總和，若cv+>bestv，則進入結(jié)點A的右分支，否則剪枝處理。c語言實現(xiàn)剪枝函數(shù)，評估后面奶牛產(chǎn)奶量的最大極值intbound(inti,intcw,intcv){intbv=cv;for(intj=i;j<n;j++)bv+=v[j];returnbv;}//飼料投喂問題（0-1背包問題）的遞歸回溯函數(shù)voidbacktrack(inti,intcw,intcv){if(i==n){if(cv>bestv&&cw<=c){ bestv=cv; for(intk=0;k<n;k++)bestx[k]=x[k];}return;}if(cw+w[i]<=c){cv+=v[i];cw+=w[i];x[i]=1;backtrack(i+1,cw,cv);

cv-=v[i];cw-=w[i];//若剪枝需要回溯}if(bound(i+1,cw,cv)>bestv){ x[i]=0;backtrack(i+1,cw,cv);}}進入左分支的剪枝約束條件進入右分支的剪枝限界條件與前一節(jié)一樣進一步優(yōu)化為了對進入右分支的限界函數(shù)進一步優(yōu)化，考慮現(xiàn)有飼料余量下精準(zhǔn)評估

的值?？梢栽趩栴}處理前，我們按單位重量投喂飼料后牛奶產(chǎn)出量的降序，重新將奶牛進行編號。按照這種順序，只要飼料還夠，就進行投喂，并計算其產(chǎn)奶量；當(dāng)考慮到某頭奶牛時，剩下的飼料不足投喂它，則用剩下的飼料對它進行部分投喂，并計算部分投喂可能的產(chǎn)奶量，并將產(chǎn)奶量累計計算結(jié)果作為

的評估值，相較前面不考慮剩余飼料量的評估會更為精準(zhǔn)。進一步優(yōu)化后的評估限界函數(shù)//剪枝限界函數(shù)的c語言代碼doublebound(inti,intcw,intcv){doublebv=cv;inttw=cw;for(intj=i;j<n;j++){if(tw+w[j]<=c){bv+=v[j];tw+=w[j];}else{doublerc=c-tw;bv+=(rc*v[j])/w[j];break;}}returnbv;}已產(chǎn)生的價值（產(chǎn)奶量）已消耗的背包容量（飼料量）已消耗的背包容量+當(dāng)前投喂量<總量當(dāng)前不足投喂，則部分投喂進行計