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

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

7.3.1裝載問題以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)品的裝載可以表示為一個四元組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)品種編號)只能等于0或1，其中0表示不裝車，1表示轉(zhuǎn)入車輛。

裝載問題4類農(nóng)產(chǎ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]：表示解空間樹上一個結(jié)點的狀態(tài)，即從第1種農(nóng)產(chǎn)品到第k種農(nóng)產(chǎn)品完成裝載選擇時，該結(jié)點表示的車輛上農(nóng)產(chǎn)品總重量為wt。Wt(X)：表示解向量X時，車輛裝載的農(nóng)產(chǎn)品總重量。

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

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