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

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

5分支限界法的基本思想

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

將活結(jié)點(diǎn)表組成一個(gè)隊(duì)列，按照隊(duì)列先進(jìn)先出（FIFO）原則選取下一個(gè)結(jié)點(diǎn)為擴(kuò)展結(jié)點(diǎn)。

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

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

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

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

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

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

解單源最短路徑問(wèn)題的優(yōu)先隊(duì)列式分支限界法用一極小堆來(lái)存儲(chǔ)活結(jié)點(diǎn)表。其優(yōu)先級(jí)是結(jié)點(diǎn)所對(duì)應(yīng)的當(dāng)前路長(zhǎng)。

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

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

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

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

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

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

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

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

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

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

15裝載問(wèn)題隊(duì)列式分支限界法活結(jié)點(diǎn)隊(duì)列中的隊(duì)首元素被取出作為當(dāng)前擴(kuò)展結(jié)點(diǎn)，由于隊(duì)列中每一層結(jié)點(diǎn)之后都有一個(gè)尾部標(biāo)記-1，故在取隊(duì)首元素時(shí)，活結(jié)點(diǎn)隊(duì)列一定不空。當(dāng)取出的元素是-1時(shí)，再判斷當(dāng)前隊(duì)列是否為空。如果隊(duì)列非空，則將尾部標(biāo)記-1加入活結(jié)點(diǎn)隊(duì)列，算法開(kāi)始處理下一層的活結(jié)點(diǎn)。16裝載問(wèn)題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é)點(diǎn)

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

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

Q.delete(ew);//取下一擴(kuò)展結(jié)點(diǎn)

i++;}}}//

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

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

bestw時(shí)，可將其右子樹(shù)剪去，因?yàn)榇藭r(shí)若要船裝最多集裝箱，就應(yīng)該把此箱裝上船。

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

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

if(wt>bestw)bestw=wt;//加入活結(jié)點(diǎn)隊(duì)列

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

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

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

右兒子剪枝

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

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

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

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

24裝載問(wèn)題

在優(yōu)