算法設(shè)計(jì)與分析 課件 第七章 分支限界 7.3.1 裝載問(wèn)題

計(jì)算機(jī)算法設(shè)計(jì)與分析第7章分支限界法7.3.1裝載問(wèn)題一個(gè)農(nóng)場(chǎng)需要將大量農(nóng)產(chǎn)品運(yùn)輸?shù)绞袌?chǎng)上去，假設(shè)農(nóng)場(chǎng)現(xiàn)有n種不同的農(nóng)產(chǎn)品和一輛載重量為c的車輛，農(nóng)產(chǎn)品i的重量為wi，價(jià)值為vi，每種農(nóng)產(chǎn)品只有裝車和不裝車兩種選擇。如何選擇裝入車輛的農(nóng)產(chǎn)品，使得車輛不超重的情況下一次裝下的農(nóng)產(chǎn)品總重量最大。

7.3.1裝載問(wèn)題以n=4種農(nóng)產(chǎn)品為例，車輛載重量c=10，每種農(nóng)產(chǎn)品的重量W={6,7,2,4}，即w1=6，w2=7,w3=2,w4=4。4種農(nóng)產(chǎn)品的裝載可以表示為一個(gè)四元組X=(x1,x2,x3,x4)，xi代表第i種農(nóng)產(chǎn)品裝車的數(shù)量，由于每種農(nóng)產(chǎn)品裝載只有裝與不裝兩種情況，所以xi(i=1,2,3,4，表示農(nóng)產(chǎn)品種編號(hào))只能等于0或1，其中0表示不裝車，1表示轉(zhuǎn)入車輛。

裝載問(wèn)題4類農(nóng)產(chǎn)品裝載問(wèn)題的解向量空間樹(shù)如圖所示

裝載問(wèn)題c：表示車輛的載重量。xi：表示第i種農(nóng)產(chǎn)品裝入車輛的數(shù)量，取值0或1。wi：表示第i種農(nóng)產(chǎn)品的重量。wt：表示當(dāng)前已裝入車的農(nóng)產(chǎn)品總重量。bestw：表示當(dāng)前車上裝載的農(nóng)產(chǎn)品重量的最優(yōu)值。[wt，k]：表示解空間樹(shù)上一個(gè)結(jié)點(diǎn)的狀態(tài)，即從第1種農(nóng)產(chǎn)品到第k種農(nóng)產(chǎn)品完成裝載選擇時(shí)，該結(jié)點(diǎn)表示的車輛上農(nóng)產(chǎn)品總重量為wt。Wt(X)：表示解向量X時(shí)，車輛裝載的農(nóng)產(chǎn)品總重量。

裝載問(wèn)題給定任意狀態(tài)[wt，k]，怎么來(lái)判斷其子結(jié)點(diǎn)是否可能得出可行解？約束函數(shù)剪枝過(guò)程約束函數(shù)剪枝過(guò)程擴(kuò)展A結(jié)點(diǎn)的左子結(jié)點(diǎn)，xk+1=1，wt’=wt+wk+1，如果這時(shí)wt’>c，說(shuō)明裝入車輛的農(nóng)產(chǎn)品重量超過(guò)了車輛的載重量，顯然這時(shí)不可行的，需要被剪枝處理。而擴(kuò)展A結(jié)點(diǎn)的右子結(jié)點(diǎn)，xk+1=0，wt≤c，裝載的農(nóng)產(chǎn)品重量與父結(jié)點(diǎn)A是一樣的，因此擴(kuò)展右子結(jié)點(diǎn)總是可行的。裝載問(wèn)題給定任意狀態(tài)[wt，k]，怎么來(lái)判斷其子結(jié)點(diǎn)是否可能得出最優(yōu)解？限界函數(shù)剪枝過(guò)程：限界函數(shù)擴(kuò)展A結(jié)點(diǎn)的右子結(jié)點(diǎn)，xk+1=0，其右子結(jié)點(diǎn)B的狀態(tài)為[wt，k+1]。限界函數(shù)設(shè)裝載問(wèn)題的解向量為X=[X1,X2]，其中X1=[x1,x2,...,xk,0]，X2=[xk+2,...,xn]。X1表示第1種農(nóng)產(chǎn)品到第k+1種農(nóng)產(chǎn)品的裝車情況，是目前已得到的農(nóng)產(chǎn)品裝車結(jié)果；X2表示從第k+2種農(nóng)產(chǎn)品到第n種農(nóng)產(chǎn)品的裝車情況，是還未考慮過(guò)的未知裝車結(jié)果。限界函數(shù)對(duì)于解向量X裝載農(nóng)產(chǎn)品的總重量：第1種農(nóng)產(chǎn)品到第k+1種農(nóng)產(chǎn)品裝入車后的重量為Wt(X1)=wt；第k+2種農(nóng)產(chǎn)品到第n種農(nóng)產(chǎn)品裝入車后的重量是未知的，用Wt(X2)表示。限界函數(shù)我們只能去估計(jì)Wt(X2)值的一個(gè)上界bound(X2)，上界函數(shù)bound(X2)≥Wt(X2)。bestw表示當(dāng)前已得到的最優(yōu)值，如果Wt(X1)+bound(X2)≤bestw，則表示當(dāng)前已裝車的農(nóng)產(chǎn)品總重量加上未裝車農(nóng)產(chǎn)品重量的上界值比當(dāng)前已知的最優(yōu)解值還要小。因此，可以判定以A為根的結(jié)點(diǎn)擴(kuò)展其右子結(jié)點(diǎn)是不可能得到問(wèn)題的最優(yōu)解的，可以剪去A結(jié)點(diǎn)的右分支。限界函數(shù)那么，如何來(lái)估算bound(X2)呢？我們可以將未裝車的農(nóng)產(chǎn)品全部裝入，得到bound(X2)=這就是限界函數(shù)剪枝過(guò)程。限界函數(shù)限界函數(shù)分析過(guò)程，對(duì)于bestw值什么時(shí)候去獲??？如果按照回溯算法分析過(guò)程，當(dāng)?shù)玫絾?wèn)題第一個(gè)完整解向量時(shí)，將這個(gè)可行解的值記作第一個(gè)bestw的值。但是，得到完整向量的可行解需要搜索到解空間樹(shù)的葉子結(jié)點(diǎn)才能完成。限界函數(shù)對(duì)于基于廣度優(yōu)先搜索的分支限界法，只能對(duì)后續(xù)的葉子結(jié)點(diǎn)進(jìn)行限界函數(shù)剪枝，而剪枝對(duì)于葉子結(jié)點(diǎn)來(lái)說(shuō)已經(jīng)沒(méi)有實(shí)際意義。因此，這樣獲取的bestw無(wú)實(shí)際效果。限界函數(shù)實(shí)際上，我們?cè)跀U(kuò)展任意結(jié)點(diǎn)k的左分支時(shí)，若其左分支是一個(gè)可行解，我們將該左子結(jié)點(diǎn)之后的農(nóng)產(chǎn)品裝載全部選擇不裝車，也可以得到一個(gè)完整的解向量，即[x1,,...,xk,1,{0}]。我們可以以這樣一個(gè)可行解的值作為bestw的值，因此，在擴(kuò)展左分支時(shí)，只要可行（車輛不超重），就及時(shí)更新bestw的值。裝載問(wèn)題的約束限界函數(shù)（1）進(jìn)入左分支的約束函數(shù)：wt+wk+1≤c（2）進(jìn)入右分支的限界函數(shù)：wt+bound>bestw實(shí)例采用隊(duì)列式分支限界法搜索n=4種農(nóng)產(chǎn)品（c=10，W={6,7,2,4}，農(nóng)產(chǎn)品種編號(hào)1~4）的裝載問(wèn)題，隊(duì)列中的結(jié)點(diǎn)元素如下列步驟中的各個(gè)圖所示。我們來(lái)定義一個(gè)結(jié)點(diǎn)元素(wt,bound,k):wt已裝入車了農(nóng)產(chǎn)品的重量bound剩余未裝車農(nóng)產(chǎn)品的總重量k當(dāng)前被處理農(nóng)產(chǎn)品種編號(hào)n=4種農(nóng)產(chǎn)品：c=10，W={6,7,2,4}

左子結(jié)點(diǎn)采用約束函數(shù)wt≤c=10作為剪枝策略右子結(jié)點(diǎn)采用限界函數(shù)wt+bound>bestw作為剪枝策略（1）初始結(jié)點(diǎn)1的三個(gè)數(shù)據(jù)項(xiàng)值為（0，19，0），即wt=0，bound=19，k=0。bestw初值為0。初始結(jié)點(diǎn)1入隊(duì)。1（0,19,0）n=4種農(nóng)產(chǎn)品：c=10，W={6,7,2,4}（2）取隊(duì)首結(jié)點(diǎn)1，擴(kuò)展它的左子結(jié)點(diǎn)2，wt=6<10，滿足約束條件是可行的，x1=1，結(jié)點(diǎn)2的三個(gè)數(shù)據(jù)項(xiàng)值為（6,13,1），結(jié)點(diǎn)2入隊(duì)，同時(shí)修改bestw=6。然后再來(lái)擴(kuò)展1的右子結(jié)點(diǎn)3，wt+bound=0+19>bestw=6，滿足限界條件是可行的，x1=0，結(jié)點(diǎn)3的三個(gè)數(shù)據(jù)項(xiàng)為（0,13,1），結(jié)點(diǎn)3入隊(duì)。左右子結(jié)點(diǎn)擴(kuò)展完畢，隊(duì)首結(jié)點(diǎn)1出隊(duì)。之后隊(duì)列情況：2（6,13,1），3（0,13,1）n=4種農(nóng)產(chǎn)品：c=10，W={6,7,2,4}（3）取隊(duì)首元素結(jié)點(diǎn)2，擴(kuò)展它的左子結(jié)點(diǎn)4，wt=6+7=13>10，不滿足約束條件，是不可行的，結(jié)點(diǎn)4被剪枝處理。然后再來(lái)擴(kuò)展它的右子結(jié)點(diǎn)5，wt+bound=6+6>bestw，滿足限界條件是可行的，x2=0，結(jié)點(diǎn)5的三個(gè)數(shù)據(jù)項(xiàng)為（6,6,2），結(jié)點(diǎn)5入隊(duì)。左右子結(jié)點(diǎn)擴(kuò)展完畢，隊(duì)首結(jié)點(diǎn)2出隊(duì)。之后隊(duì)列情況：3（0,13,1），5（6,6,2）n=4種農(nóng)產(chǎn)品：c=10，W={6,7,2,4}（4）取隊(duì)首結(jié)點(diǎn)3，擴(kuò)展它的左子結(jié)點(diǎn)6，wt=0+7<10，滿足約束條件是可行的，x2=1，結(jié)點(diǎn)6的三個(gè)數(shù)據(jù)項(xiàng)值為（7,6,2），結(jié)點(diǎn)6入隊(duì)，同時(shí)修改bestw=7。然后再來(lái)擴(kuò)展它的右子結(jié)點(diǎn)7，wt+bound=0+6<bestw=7，不滿足限界條件，是不可能產(chǎn)生最優(yōu)解的，結(jié)點(diǎn)7被剪枝處理。左右子結(jié)點(diǎn)擴(kuò)展完畢，隊(duì)首結(jié)點(diǎn)3出隊(duì)。之后隊(duì)列情況：5（6,6,2），6（7,6,2）n=4種農(nóng)產(chǎn)品：c=10，W={6,7,2,4}（5）取隊(duì)首結(jié)點(diǎn)5，擴(kuò)展它的左子結(jié)點(diǎn)10，wt=6+4=10，滿足約束條件是可行的，x3=1，結(jié)點(diǎn)10的三個(gè)數(shù)據(jù)項(xiàng)值為（10,2,3），結(jié)點(diǎn)10入隊(duì)，同時(shí)修改bestw=10。然后再來(lái)擴(kuò)展它的右子結(jié)點(diǎn)11，wt+bound=6+2<bestw=10，不滿足限界條件，是不可能產(chǎn)生最優(yōu)解的，結(jié)點(diǎn)11被剪枝處理。左右子結(jié)點(diǎn)擴(kuò)展完畢，隊(duì)首結(jié)點(diǎn)5出隊(duì)。之后隊(duì)列情況：6（7,6,2），10（10,2,3）n=4種農(nóng)產(chǎn)品：c=10，W={6,7,2,4}（6）取隊(duì)首結(jié)點(diǎn)6，擴(kuò)展它的左子結(jié)點(diǎn)12，wt=7+4>10，不滿足約束條件，是不可行的，結(jié)點(diǎn)12被剪枝處理。然后再來(lái)擴(kuò)展它的右子結(jié)點(diǎn)13，wt+bound=7+2<bestw=10，不滿足限界條件，是不可能產(chǎn)生最優(yōu)解的，結(jié)點(diǎn)13被剪枝處理。左右子結(jié)點(diǎn)擴(kuò)展完畢，隊(duì)首結(jié)點(diǎn)6出隊(duì)。之后隊(duì)列情況：10（10,2,3）n=4種農(nóng)產(chǎn)品：c=10，W={6,7,2,4}（7）取隊(duì)首結(jié)點(diǎn)10，擴(kuò)展它的左子結(jié)點(diǎn)20，wt=10+2>10，不滿足約束條件，是不可行的，結(jié)點(diǎn)2