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

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

如何計(jì)算？這部分是還沒(méi)有考慮投喂的奶牛最大產(chǎn)奶量，屬于未知的，所以僅對(duì)其上限進(jìn)行粗略的評(píng)估。算法改進(jìn)常用的評(píng)估方法為=在不考慮現(xiàn)有飼料余量的情況下，后面的奶牛全部產(chǎn)奶的總和，若cv+>bestv，則進(jìn)入結(jié)點(diǎn)A的右分支，否則剪枝處理。c語(yǔ)言實(shí)現(xiàn)剪枝函數(shù)，評(píng)估后面奶牛產(chǎn)奶量的最大極值intbound(inti,intcw,intcv){intbv=cv;for(intj=i;j<n;j++)bv+=v[j];returnbv;}//飼料投喂問(wèn)題（0-1背包問(wèn)題）的遞歸回溯函數(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);}}進(jìn)入左分支的剪枝約束條件進(jìn)入右分支的剪枝限界條件與前一節(jié)一樣進(jìn)一步優(yōu)化為了對(duì)進(jìn)入右分支的限界函數(shù)進(jìn)一步優(yōu)化，考慮現(xiàn)有飼料余量下精準(zhǔn)評(píng)估

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

的評(píng)估值，相較前面不考慮剩余飼料量的評(píng)估會(huì)更為精準(zhǔn)。進(jìn)一步優(yōu)化后的評(píng)估限界函數(shù)//剪枝限界函數(shù)的c語(yǔ)言代碼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)生的價(jià)值（產(chǎn)奶量）已消耗的背包容量（飼料量）已消耗的背包容量+當(dāng)前投喂量<總量當(dāng)前不足投喂，則部分投喂進(jìn)行計(jì)