研一考試相關(guān)算法分析6分支限界

1第七章分支限界法2分支限界法分支限界法類似于回溯法，是在問題的解空間樹上搜索問題解的算法。分支限界法與回溯法的區(qū)別：（1）求解目標(biāo)不同?；厮莘ǖ那蠼饽繕?biāo)是找出解空間中滿足約束條件的所有解；分支限界法的求解目標(biāo)是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出使某一目標(biāo)函數(shù)值達到極大或極小的解，即在某種意義下的最優(yōu)解。（2）搜索方式不同?；厮莘ㄊ且陨疃葍?yōu)先搜索的方式搜索解空間樹；分支限界法則以廣度優(yōu)先或以最小耗資優(yōu)先的方式搜索空間樹。3分支限界法的搜索策略在擴展結(jié)點處，先生成其所有的兒子結(jié)點（分支），然后再從當(dāng)前的活結(jié)點表中選擇下一個擴展結(jié)點。為了有效地選擇下一擴展結(jié)點，加速搜索進程，在每一擴展結(jié)點處，計算一個函數(shù)值（限界），并根據(jù)函數(shù)值，從當(dāng)前活結(jié)點表中選擇一個最有利的結(jié)點作為擴展結(jié)點，使搜索朝著解空間樹上有最優(yōu)解的分支推進，以便盡快地找出一個最優(yōu)解。分支限界法解決了大量離散最優(yōu)化問題。4分支限界法的基本思想在分支限界法中，每一個活結(jié)點只有一次機會成為擴展結(jié)點?；罱Y(jié)點一旦成為擴展結(jié)點，就一次性產(chǎn)生其所有兒子結(jié)點。在這些兒子結(jié)點中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點被舍棄，其余兒子結(jié)點被加入活結(jié)點表中。此后，從活結(jié)點表中取下一結(jié)點成為當(dāng)前擴展結(jié)點，并重復(fù)上述結(jié)點擴展過程。這個過程一直持續(xù)到找到所需的解或活結(jié)點表為空時為止。

5分支限界法的基本思想

從活結(jié)點表中選擇下一個擴展結(jié)點的不同方式導(dǎo)致不同的分支限界法。常見的兩種分支限界法：（1）隊列式(FIFO)分支限界法

將活結(jié)點表組成一個隊列，按照隊列先進先出（FIFO）原則選取下一個結(jié)點為擴展結(jié)點。

6分支限界法的基本思想（2）優(yōu)先隊列式分支限界法

將活結(jié)點表組成一個優(yōu)先隊列，并按照優(yōu)先隊列中規(guī)定的優(yōu)先級選取優(yōu)先級最高的結(jié)點成為當(dāng)前擴展結(jié)點。優(yōu)先隊列中規(guī)定的結(jié)點優(yōu)先級常用一個與該結(jié)點相關(guān)的數(shù)值p表示。

最大優(yōu)先隊列規(guī)定p值較大的結(jié)點優(yōu)先級較高，體現(xiàn)最大效益優(yōu)先的原則。

最小優(yōu)先隊列規(guī)定p值較小的結(jié)點優(yōu)先級較高，體現(xiàn)最小費用優(yōu)先的原則。7單源最短路徑問題1.問題描述

下面以一個例子來說明單源最短路徑問題：在下圖所給的有向圖G中，每一邊都有一個非負邊權(quán)。要求圖G從源頂點s到目標(biāo)頂點t之間的最短路徑。

8單源最短路徑問題下圖是用優(yōu)先隊列式分支限界法解有向圖G的單源最短路徑問題產(chǎn)生的解空間樹。其中，每一個結(jié)點旁邊的數(shù)字表示該結(jié)點所對應(yīng)的當(dāng)前路長。9單源最短路徑問題算法思想

解單源最短路徑問題的優(yōu)先隊列式分支限界法用一極小堆來存儲活結(jié)點表。其優(yōu)先級是結(jié)點所對應(yīng)的當(dāng)前路長。

10單源最短路徑問題算法從圖G的源頂點s和空優(yōu)先隊列開始。結(jié)點s被擴展后，它的兒子結(jié)點被依次插入堆中。此后，算法從堆中取出具有最小當(dāng)前路長的結(jié)點作為當(dāng)前擴展結(jié)點，并依次檢查與當(dāng)前擴展結(jié)點相鄰的所有頂點。如果從當(dāng)前擴展結(jié)點i到頂點j有邊可達，且從源出發(fā)，途經(jīng)頂點i再到頂點j的所相應(yīng)的路徑的長度小于當(dāng)前最優(yōu)路徑長度，則將該頂點作為活結(jié)點插入到活結(jié)點優(yōu)先隊列中。這個結(jié)點的擴展過程一直繼續(xù)到活結(jié)點優(yōu)先隊列為空時為止。11單源最短路徑問題剪枝策略

在算法擴展結(jié)點的過程中，一旦發(fā)現(xiàn)一個結(jié)點的下界不小于當(dāng)前找到的最短路長，則算法剪去以該結(jié)點為根的子樹。

在算法中，利用結(jié)點間的控制關(guān)系進行剪枝。從源頂點s出發(fā)，2條不同路徑到達圖G的同一頂點。由于兩條路徑的路長不同，因此可以將路長長的路徑所對應(yīng)的樹中的結(jié)點為根的子樹剪去。

12單源最短路徑問題while(true)//搜索問題的解空間{for(intj=1;j<=n;j++)if(a[enode.i][j]<Float.MAX_VALUE&&

enode.length+a[enode.i][j]<dist[j]){//頂點i到頂點j可達，且滿足控制約束

dist[j]=enode.length+a[enode.i][j];p[j]=enode.i;HeapNodenode=newHeapNode(j,dist[j]);heap.put(node);//加入活結(jié)點優(yōu)先隊列}

if(heap.isEmpty())break;elseenode=(HeapNode)heap.removeMin();

}13裝載問題1.問題描述有一批共n個集裝箱要裝上2艘載重量分別為C1和C2的輪船，其中集裝箱i的重量為Wi，且裝載問題要求確定是否有一個合理的裝載方案可將這個集裝箱裝上這2艘輪船。如果有，找出一種裝載方案。

裝載問題其實質(zhì)是要求第一艘船的最優(yōu)裝載。裝載問題是一個子集選取問題，因此其解空間樹是一棵子集樹。14裝載問題隊列式分支限界法

在算法的while循環(huán)中，首先檢測當(dāng)前擴展結(jié)點的左兒子結(jié)點是否為可行結(jié)點。如果是則將其加入到活結(jié)點隊列中。然后將其右兒子結(jié)點加入到活結(jié)點隊列中(右兒子結(jié)點一定是可行結(jié)點)。2個兒子結(jié)點都產(chǎn)生后，當(dāng)前擴展結(jié)點被舍棄。

15裝載問題隊列式分支限界法活結(jié)點隊列中的隊首元素被取出作為當(dāng)前擴展結(jié)點，由于隊列中每一層結(jié)點之后都有一個尾部標(biāo)記-1，故在取隊首元素時，活結(jié)點隊列一定不空。當(dāng)取出的元素是-1時，再判斷當(dāng)前隊列是否為空。如果隊列非空，則將尾部標(biāo)記-1加入活結(jié)點隊列，算法開始處理下一層的活結(jié)點。16裝載問題Mazloading(w[],c,n){Q.add(-1);i=1;ew=0;bestw=0;while(true){if(ew+w[i]<=c)enQueue(ew+w[i],i);//檢查左兒子結(jié)點

enQueue(ew,i);//右兒子結(jié)點總是可行的Q.delete(ew);//取下一擴展結(jié)點

if(ew==-1){if(Q.isEmpty())returnbestw;Q.add(-1);//同層結(jié)點尾部標(biāo)志

Q.delete(ew);//取下一擴展結(jié)點

i++;}}}//

進入下一層VoidenQueue(wt,i){if(i==n){if(wt>bestw)bestw=wt;}elseQ.add(wt);}17裝載問題算法maxLoading初始時將bestw置為0，直到搜索到第一個葉結(jié)點時才更新bestw。因此在算法搜索到第一個葉結(jié)點之前，總有bestw=0，r>0,故ew+r>bestw總是成立。也就是說，此時右子樹測試不起作用。18裝載問題算法的改進

結(jié)點的左子樹表示將此集裝箱裝上船，右子樹表示不將此集裝箱裝上船。設(shè)bestw是當(dāng)前最優(yōu)解；ew是當(dāng)前擴展結(jié)點所相應(yīng)的重量；r是剩余集裝箱的重量。則當(dāng)ew+r

bestw時，可將其右子樹剪去，因為此時若要船裝最多集裝箱，就應(yīng)該把此箱裝上船。

19裝載問題為了使上述右子樹測試盡早生效，應(yīng)提早更新bestw。知道算法最終找到的最優(yōu)值是所求問題的子集樹中所有可行結(jié)點相應(yīng)的重量的最大值。而結(jié)點所相應(yīng)的重量僅在搜索進入左子樹時增加。另外，為了確保右子樹成功剪枝，應(yīng)該在算法每一次進入左子樹的時候更新bestw的值。20算法的改進//檢查左兒子結(jié)點

intwt=ew+w[i];if(wt<=c){//可行結(jié)點

if(wt>bestw)bestw=wt;//加入活結(jié)點隊列

if(i<n)queue.put(newInteger(wt));}提前更新bestw//檢查右兒子結(jié)點

if(ew+r>bestw&&i<n)//可能含最優(yōu)解

queue.put(newInteger(ew));ew=((Integer)queue.remove()).intValue();//取下一擴展結(jié)點

右兒子剪枝

21裝載問題構(gòu)造最優(yōu)解

為了在算法結(jié)束后能方便地構(gòu)造出與相應(yīng)最優(yōu)值的最優(yōu)解，算法必須存儲相應(yīng)子集樹中從活結(jié)點到根結(jié)點的路徑。為此目的，可在每個結(jié)點處設(shè)置指向其父結(jié)點的指針，并設(shè)置左、右兒子標(biāo)志。

privatestaticclassQNode{QNodeparent;//父結(jié)點booleanleftChild;//左兒子標(biāo)志intweight;//結(jié)點所相應(yīng)的載重量22裝載問題找到最優(yōu)值后，可以根據(jù)parent回溯到根節(jié)點，找到最優(yōu)解。//構(gòu)造當(dāng)前最優(yōu)解

for(intj=n;j>0;j--){bestx[j]=(e.leftChild)?1:0;e=e.parent;}23裝載問題優(yōu)先隊列式分支限界法(1)解裝載問題的優(yōu)先隊列式分支限界法用最大優(yōu)先隊列存儲活結(jié)點表。(2)活結(jié)點x在優(yōu)先隊列中的優(yōu)先級定義為從根結(jié)點到結(jié)點x的路徑所相應(yīng)的載重量再加上剩余集裝箱的重量之和。(3)優(yōu)先隊列中優(yōu)先級最大的活結(jié)點成為下一個擴展結(jié)點。(4)以結(jié)點x為根的子樹中所有結(jié)點相應(yīng)的路徑的載重量不超過它的優(yōu)先級。(5)子集樹中葉結(jié)點所相應(yīng)的載重量與其優(yōu)先級相同。

24裝載問題

在優(yōu)