第11講分支限界法

1、Design and Analysis of Computer Algorithms分支限界法分支限界法大連海事大學(xué)Design and Analysis of Computer AlgorithmsDesign and Analysis of Computer Algorithms5 55 51 1 分支搜索算法分支搜索算法 1 1基本思想基本思想 分支搜索法也是一種在問題解空間上進(jìn)行嘗試搜索算法。所謂分支搜索法也是一種在問題解空間上進(jìn)行嘗試搜索算法。所謂“分支分支”是采用廣度優(yōu)先的策略，依次生成是采用廣度優(yōu)先的策略，依次生成E-結(jié)點所有分支，也就結(jié)點所有分支，也就是所有的兒子結(jié)點。和回溯法

2、一樣，在生成的節(jié)點中，拋棄那些不是所有的兒子結(jié)點。和回溯法一樣，在生成的節(jié)點中，拋棄那些不滿足約束條件（或者說不可能導(dǎo)出最優(yōu)可行解）的結(jié)點，其余節(jié)點滿足約束條件（或者說不可能導(dǎo)出最優(yōu)可行解）的結(jié)點，其余節(jié)點加入活節(jié)點表。然后從表中選擇一個節(jié)點作為下一個加入活節(jié)點表。然后從表中選擇一個節(jié)點作為下一個E-節(jié)點。選擇節(jié)點。選擇下一個下一個E-節(jié)點的方式不同導(dǎo)致幾種不同的分支搜索方式：節(jié)點的方式不同導(dǎo)致幾種不同的分支搜索方式：1FIFO搜索 2LIFO搜索 3優(yōu)先隊列式搜索 Design and Analysis of Computer Algorithms1FIFO搜索搜索大連海事大學(xué) 一開始，根結(jié)

3、點是唯一的活結(jié)點，根結(jié)點入隊。從活結(jié)點一開始，根結(jié)點是唯一的活結(jié)點，根結(jié)點入隊。從活結(jié)點隊中取出根結(jié)點后，作為當(dāng)前擴(kuò)展結(jié)點。對當(dāng)前擴(kuò)展結(jié)點，先隊中取出根結(jié)點后，作為當(dāng)前擴(kuò)展結(jié)點。對當(dāng)前擴(kuò)展結(jié)點，先從左到右地產(chǎn)生它的所有兒子，用約束條件檢查，把所有滿足從左到右地產(chǎn)生它的所有兒子，用約束條件檢查，把所有滿足約束函數(shù)的兒子加入活結(jié)點隊列中。再從活結(jié)點表中取出隊首約束函數(shù)的兒子加入活結(jié)點隊列中。再從活結(jié)點表中取出隊首結(jié)點（隊中最先進(jìn)來的結(jié)點）為當(dāng)前擴(kuò)展結(jié)點，結(jié)點（隊中最先進(jìn)來的結(jié)點）為當(dāng)前擴(kuò)展結(jié)點，直到找，直到找到一個解或活結(jié)點隊列為空為止。到一個解或活結(jié)點隊列為空為止。 Design and Ana

4、lysis of Computer Algorithms2 2LIFOLIFO搜索搜索大連海事大學(xué) 一開始，根結(jié)點入棧。從棧中彈出一個結(jié)點為當(dāng)一開始，根結(jié)點入棧。從棧中彈出一個結(jié)點為當(dāng)前擴(kuò)展結(jié)點。對當(dāng)前擴(kuò)展結(jié)點，先從左到右地產(chǎn)生它前擴(kuò)展結(jié)點。對當(dāng)前擴(kuò)展結(jié)點，先從左到右地產(chǎn)生它的所有兒子，用約束條件檢查，把所有滿足約束函數(shù)的所有兒子，用約束條件檢查，把所有滿足約束函數(shù)的兒子入棧，再從棧中彈出一個結(jié)點（棧中最后進(jìn)來的兒子入棧，再從棧中彈出一個結(jié)點（棧中最后進(jìn)來的結(jié)點）為當(dāng)前擴(kuò)展結(jié)點，的結(jié)點）為當(dāng)前擴(kuò)展結(jié)點，直到找到一個解或，直到找到一個解或棧為空為止。棧為空為止。 Design and Analy

5、sis of Computer Algorithms3 3優(yōu)先隊列式搜索優(yōu)先隊列式搜索大連海事大學(xué) 為了加速搜索的進(jìn)程，應(yīng)采用有效地方式選擇為了加速搜索的進(jìn)程，應(yīng)采用有效地方式選擇E-結(jié)點進(jìn)行擴(kuò)展。優(yōu)先隊列式搜索，對每一活結(jié)點結(jié)點進(jìn)行擴(kuò)展。優(yōu)先隊列式搜索，對每一活結(jié)點計算一個優(yōu)先級（某些信息的函數(shù)值），并根據(jù)這計算一個優(yōu)先級（某些信息的函數(shù)值），并根據(jù)這些優(yōu)先級，從當(dāng)前活結(jié)點表中優(yōu)先選擇一個優(yōu)先級些優(yōu)先級，從當(dāng)前活結(jié)點表中優(yōu)先選擇一個優(yōu)先級最高（最有利）的結(jié)點作為擴(kuò)展結(jié)點，使搜索朝著最高（最有利）的結(jié)點作為擴(kuò)展結(jié)點，使搜索朝著解空間樹上有最優(yōu)解的分支推進(jìn)，以便盡快地找出解空間樹上有最優(yōu)解的分支

6、推進(jìn)，以便盡快地找出一個最優(yōu)解。這種擴(kuò)展方式要到下一節(jié)才用的到。一個最優(yōu)解。這種擴(kuò)展方式要到下一節(jié)才用的到。 Design and Analysis of Computer Algorithms552 分枝分枝-限界搜索算法限界搜索算法大連海事大學(xué) 【例例】有兩艘船，有兩艘船，n n 個貨箱。第一艘船的載重量是個貨箱。第一艘船的載重量是c c1，第二艘船，第二艘船的載重量是的載重量是c c2，w wi 是貨箱是貨箱i i 的重量的重量, ,且且 w 1+w2+wncc1+c+c2。我們希望確定是否有一種可將所有我們希望確定是否有一種可將所有n n 個貨箱全部裝船的方法。若有個貨箱全部裝船的方法

7、。若有的話，找出該方法的話，找出該方法 FIFO限界搜索算法限界搜索算法優(yōu)先隊列式分支限界法優(yōu)先隊列式分支限界法Design and Analysis of Computer AlgorithmsDesign and Analysis of Computer Algorithms算法算法1的缺點有的缺點有: : 1）在可解的情況下，沒有給出每艘裝載物品的方案。而要）在可解的情況下，沒有給出每艘裝載物品的方案。而要想記錄第一艘船最大裝載的方案，象回溯法中用想記錄第一艘船最大裝載的方案，象回溯法中用n個元素的數(shù)個元素的數(shù)組是不能實現(xiàn)的，可以象組是不能實現(xiàn)的，可以象5.2.2小節(jié)中的例子用數(shù)組隊列下

8、標(biāo)記小節(jié)中的例子用數(shù)組隊列下標(biāo)記錄解方案。錄解方案。 這里采用構(gòu)造二叉樹的方法，和這里采用構(gòu)造二叉樹的方法，和5.2.2小節(jié)中的例題一樣只需小節(jié)中的例題一樣只需要記錄最優(yōu)解的葉結(jié)點，這樣二叉樹就必需有指向父結(jié)點的指要記錄最優(yōu)解的葉結(jié)點，這樣二叉樹就必需有指向父結(jié)點的指針，以便從葉結(jié)點回溯找解的方案。又為了方便知道當(dāng)前結(jié)點針，以便從葉結(jié)點回溯找解的方案。又為了方便知道當(dāng)前結(jié)點對物品的取舍情況，還必須記錄當(dāng)前結(jié)點是父結(jié)點的哪一個兒對物品的取舍情況，還必須記錄當(dāng)前結(jié)點是父結(jié)點的哪一個兒子。子。數(shù)據(jù)結(jié)構(gòu)：由此，樹中結(jié)點的信息包括：數(shù)據(jù)結(jié)構(gòu)：由此，樹中結(jié)點的信息包括：weight;parent; wei

9、ght;parent; LChild;LChild;。同時這些結(jié)點的地址就是抽象隊列的元素，隊列操作。同時這些結(jié)點的地址就是抽象隊列的元素，隊列操作與算法與算法1 1相同相同 . .Design and Analysis of Computer AlgorithmsDesign and Analysis of Computer Algorithms 2 2）算法）算法1 1是在對子集樹進(jìn)行盲目搜索，我們雖然不能將搜索是在對子集樹進(jìn)行盲目搜索，我們雖然不能將搜索算法改進(jìn)為多項式復(fù)雜度，但在算法中加入了算法改進(jìn)為多項式復(fù)雜度，但在算法中加入了“限界限界”技巧，還技巧，還是能降低算法的復(fù)雜度。是能降

10、低算法的復(fù)雜度。 一個簡單的現(xiàn)象，若當(dāng)前分支的一個簡單的現(xiàn)象，若當(dāng)前分支的“裝載上界裝載上界”，比現(xiàn)有的最，比現(xiàn)有的最大裝載小，則該分支就無需繼續(xù)搜索。而一個分支的大裝載小，則該分支就無需繼續(xù)搜索。而一個分支的“裝載上裝載上界界”，也是容易求解的，就是假設(shè)裝載當(dāng)前物品以后的所有物品。，也是容易求解的，就是假設(shè)裝載當(dāng)前物品以后的所有物品。舉一個簡單的例子，舉一個簡單的例子，W=50W=50，1010，1010，C C1 1=60=60，所構(gòu)成的子集樹就，所構(gòu)成的子集樹就無需搜索結(jié)點無需搜索結(jié)點2 2的分支，因為擴(kuò)展結(jié)點的分支，因為擴(kuò)展結(jié)點1 1后，就知道最大裝載量不后，就知道最大裝載量不會小于會

11、小于5050；而擴(kuò)展結(jié)點；而擴(kuò)展結(jié)點2 2時，發(fā)現(xiàn)此分支的時，發(fā)現(xiàn)此分支的“裝載上界裝載上界”為為w w2 2+w+w3 3=2050=2050，無需搜索此分支，結(jié)點，無需搜索此分支，結(jié)點2 2不必入隊。不必入隊。Design and Analysis of Computer Algorithms數(shù)據(jù)結(jié)構(gòu)：相應(yīng)地，當(dāng)前最大裝載數(shù)據(jù)結(jié)構(gòu)：相應(yīng)地，當(dāng)前最大裝載bestwbestw不僅僅對葉結(jié)點計算，不僅僅對葉結(jié)點計算，每次搜索裝載情況（搜索左兒子）時，都重新確定每次搜索裝載情況（搜索左兒子）時，都重新確定bestwbestw的值。的值。為了方便計算一個分支的為了方便計算一個分支的“裝載上界裝載上界

12、”，用變量，用變量r r記錄當(dāng)前層以記錄當(dāng)前層以下的最大重量。下的最大重量。公共變量的定義：大連海事大學(xué)float bestw,w100,float bestw,w100,bestx100bestx100; ;int nint n；Queue Q;Queue Q;struct QNode struct QNode float weight; float weight; QNode QNode * *parent;parent; QNode LChild; QNode LChild; Design and Analysis of Computer AlgorithmsDesign and Ana

13、lysis of Computer Algorithms算法如下：算法如下：main( )main( )int c1,c2,n, s=0,i;int c1,c2,n, s=0,i;input(c1,c2input(c1,c2，n);n);for(i=1;i=n;i+) for(i=1;i=n;i+) input(wi) input(wi)； s=s+wis=s+wi； if (s=c1 or s=c2) if (s=c1 or sc1+c2) print(if (sc1+c2) print(“no solutionno solution”); return;); return;Design a

14、nd Analysis of Computer Algorithms大連海事大學(xué)MaxLoading(c1);MaxLoading(c1);if (s- bestw =c2);if (s- bestw =c2); print(“The first ship loading”, bestw print(“The first ship loading”, bestw，“chosechose：”);); for(i=1;i=n;i+) for(i=1;i=n;i+) if( if(bestxi=1bestxi=1) ) print(i print(i，“，”);); print(“ print(“換

15、行符換行符 The second ship loading”, s-bestw,“chose”);The second ship loading”, s-bestw,“chose”); for(i=1;i=n;i+) for(i=1;ibestw) / if (wtbestw) / 目前的最優(yōu)解目前的最優(yōu)解/ / bestE = E; bestE = E; bestxn = ch; /bestxn bestxn = ch; /bestxn取值為取值為chch return; return; b = new QNode; / b = new QNode; / 不是葉子不是葉子, , 添加到隊列中

16、添加到隊列中b-weight = wt;b-weight = wt;b-parent = E;b-parent = E;b-LChild = ch; /b-LChild = ch; /新節(jié)點是左孩子時新節(jié)點是左孩子時add (Q,b) ;add (Q,b) ; Design and Analysis of Computer AlgorithmsDesign and Analysis of Computer AlgorithmsMaxLoading(int n, int bestx)MaxLoading(int n, int bestx)Qnode Qnode * *E; int i = 1;E

17、; int i = 1;E= new QNode;add (Q,0) ; / 0 E= new QNode;add (Q,0) ; / 0 代表本層的尾部代表本層的尾部E-weight=0; E-parent =null; E-Lchild=0; add (Q,E) ;E-weight=0; E-parent =null; E-Lchild=0; add (Q,E) ;bestw = 0; r = 0; / E-bestw = 0; r = 0; / E-節(jié)點中余下的重量節(jié)點中余下的重量Ew=E-weight;Ew=E-weight;for (int j =2; j = n; j+) r=r+

18、 wi;for (int j =2; j weight + wi; / wt = E-weight + wi; / 檢查檢查E-E-節(jié)點的左孩子節(jié)點的左孩子 if (wt = c) / if (wt bestw) if (wt bestw) bestw = wt; bestw = wt; AddLiveNode(wt,i, E ,1); AddLiveNode(wt,i, E ,1); if (Ew+r bestw) / if (Ew+r bestw) / 檢查右孩子檢查右孩子 AddLiveNode(Ew,i,E,0); AddLiveNode(Ew,i,E,0); Delete (Q,E

19、) ; / Delete (Q,E ) ; / 下一個下一個E-E-節(jié)點節(jié)點Design and Analysis of Computer AlgorithmsDesign and Analysis of Computer Algorithms if (!E) / if (!E) / 層的尾部層的尾部 if (Empty(Q ) if (Empty(Q ) break; break; add (Q 0 ) ; / add (Q 0 ) ; / 層尾指針層尾指針 Delete(Q,E ) ; / Delete(Q,E ) ; / 下一個下一個E-E-節(jié)點節(jié)點 i + + ; / E-i + +

20、; / E-節(jié)點的層次節(jié)點的層次 r = r - wi; / E-r = r - wi; / E-節(jié)點中余下的重量節(jié)點中余下的重量 Ew = E- w e i g h t ; / Ew = E- w e i g h t ; / 新的新的E-E-節(jié)點的重量節(jié)點的重量 / / 沿著從沿著從b e s t Eb e s t E到根的路徑構(gòu)造到根的路徑構(gòu)造x x ，x nx n由由AddLiveNodeAddLiveNode來設(shè)置來設(shè)置for (j = n - 1; j 0; j-) for (j = n - 1; j 0; j-) bestxj = bestE-LChild; / bestxj =

21、bestE-LChild; / 從從b o o lb o o l轉(zhuǎn)換為轉(zhuǎn)換為i n ti n t bestE = bestE-parent; bestE = bestE-parent;return bestw;return bestw; Design and Analysis of Computer Algorithms算法設(shè)計算法設(shè)計3：用優(yōu)先隊列式分支限界法解決【例】的問題大連海事大學(xué) 上一節(jié)介紹的優(yōu)先隊列式擴(kuò)展方式，若不加入限界策略其實是上一節(jié)介紹的優(yōu)先隊列式擴(kuò)展方式，若不加入限界策略其實是無意義的。因為要說明解的最優(yōu)性，不搜索完所有問題空間是不能無意義的。因為要說明解的最優(yōu)性，不搜索完

22、所有問題空間是不能下結(jié)論的，而要對問題空間進(jìn)行完全搜索，考慮優(yōu)先級也就沒有意下結(jié)論的，而要對問題空間進(jìn)行完全搜索，考慮優(yōu)先級也就沒有意義了。義了。 優(yōu)先隊列式搜索通過結(jié)點的優(yōu)先級，可以使搜索盡快朝著解空優(yōu)先隊列式搜索通過結(jié)點的優(yōu)先級，可以使搜索盡快朝著解空間樹上有最優(yōu)解的分支推進(jìn)，這樣當(dāng)前最優(yōu)解一定較接近真正的最間樹上有最優(yōu)解的分支推進(jìn)，這樣當(dāng)前最優(yōu)解一定較接近真正的最優(yōu)解。其后我們將當(dāng)前最優(yōu)解作為一個優(yōu)解。其后我們將當(dāng)前最優(yōu)解作為一個“界界”，對上界（或下界），對上界（或下界）不可能達(dá)到（大于）這個界的分支則不去進(jìn)行搜索，這樣就縮小搜不可能達(dá)到（大于）這個界的分支則不去進(jìn)行搜索，這樣就縮小搜

23、索范圍，提高了搜索效率。這種搜索策略稱為優(yōu)先隊列式分支限界索范圍，提高了搜索效率。這種搜索策略稱為優(yōu)先隊列式分支限界法法LC-LC-檢索。檢索。Design and Analysis of Computer Algorithms大連海事大學(xué) 1 1）結(jié)點擴(kuò)展方式：無論那種分支限界法，都需要有一張活）結(jié)點擴(kuò)展方式：無論那種分支限界法，都需要有一張活結(jié)點表。優(yōu)先隊列的分支限界法將活結(jié)點組織成一個優(yōu)先隊列，結(jié)點表。優(yōu)先隊列的分支限界法將活結(jié)點組織成一個優(yōu)先隊列，并按優(yōu)先隊列中規(guī)定的結(jié)點優(yōu)先級選取優(yōu)先級最高的下一個結(jié)并按優(yōu)先隊列中規(guī)定的結(jié)點優(yōu)先級選取優(yōu)先級最高的下一個結(jié)點成為當(dāng)前擴(kuò)展結(jié)點。點成為當(dāng)前擴(kuò)

24、展結(jié)點。 2 2）結(jié)點優(yōu)先級確定：優(yōu)先隊列中結(jié)點優(yōu)先級常規(guī)定為一個）結(jié)點優(yōu)先級確定：優(yōu)先隊列中結(jié)點優(yōu)先級常規(guī)定為一個與該結(jié)點相關(guān)的數(shù)值與該結(jié)點相關(guān)的數(shù)值p p，它一般表示其接近最優(yōu)解的程度，本例，它一般表示其接近最優(yōu)解的程度，本例題就以當(dāng)前結(jié)點的所在分支的裝載上界為優(yōu)先值。題就以當(dāng)前結(jié)點的所在分支的裝載上界為優(yōu)先值。 3 3）優(yōu)先隊列組織：結(jié)點優(yōu)先級確定后，簡單地按結(jié)點優(yōu)先級）優(yōu)先隊列組織：結(jié)點優(yōu)先級確定后，簡單地按結(jié)點優(yōu)先級進(jìn)行排序，就生成了優(yōu)先隊列。排序算法的時間復(fù)雜度較高，考慮進(jìn)行排序，就生成了優(yōu)先隊列。排序算法的時間復(fù)雜度較高，考慮到搜索算法每次只擴(kuò)展一個結(jié)點，回憶數(shù)據(jù)結(jié)構(gòu)中堆排序，適

25、合這到搜索算法每次只擴(kuò)展一個結(jié)點，回憶數(shù)據(jù)結(jié)構(gòu)中堆排序，適合這一特點且比較交換的次數(shù)最少。此題應(yīng)該采用最大堆來實現(xiàn)優(yōu)先隊一特點且比較交換的次數(shù)最少。此題應(yīng)該采用最大堆來實現(xiàn)優(yōu)先隊列。列。 Design and Analysis of Computer Algorithms大連海事大學(xué)數(shù)據(jù)結(jié)構(gòu)設(shè)計：數(shù)據(jù)結(jié)構(gòu)設(shè)計：1）要輸出解的方案，在搜索過程中仍需要生成解結(jié)構(gòu)樹，其結(jié)）要輸出解的方案，在搜索過程中仍需要生成解結(jié)構(gòu)樹，其結(jié)點信息包括指向父結(jié)點的指針和標(biāo)識物品取舍（或是父結(jié)點的點信息包括指向父結(jié)點的指針和標(biāo)識物品取舍（或是父結(jié)點的左、右孩子）。左、右孩子）。 2 2）堆結(jié)點首先應(yīng)該包括結(jié)點優(yōu)先級信息

26、：結(jié)點的所在分支）堆結(jié)點首先應(yīng)該包括結(jié)點優(yōu)先級信息：結(jié)點的所在分支的裝載上界的裝載上界uweightuweight；堆中無法體現(xiàn)結(jié)點的層次信息（；堆中無法體現(xiàn)結(jié)點的層次信息（levellevel），），只能存儲在結(jié)點中；只能存儲在結(jié)點中；AddLiveNodeAddLiveNode用于把用于把bbnodebbnode類型的活節(jié)點加到子樹中，并把類型的活節(jié)點加到子樹中，并把HeapNodeHeapNode類型的活節(jié)點插入最大堆。類型的活節(jié)點插入最大堆。 3）不同與算法）不同與算法2，由于擴(kuò)展結(jié)點不是按層進(jìn)行的計算結(jié)點，由于擴(kuò)展結(jié)點不是按層進(jìn)行的計算結(jié)點的所在分支的裝載上界時，要用數(shù)組變量的所在分

27、支的裝載上界時，要用數(shù)組變量r r記錄當(dāng)前層以下的最記錄當(dāng)前層以下的最大重量，這樣可以隨時方便使用各層結(jié)點的裝載上界。大重量，這樣可以隨時方便使用各層結(jié)點的裝載上界。 Design and Analysis of Computer AlgorithmsDesign and Analysis of Computer Algorithms算法設(shè)計算法設(shè)計3 3（3 3）：）：算法算法3 3如下：如下： HeapNode H1000;HeapNode H1000;struct bbnode struct bbnode bbnode bbnode * *parent; / parent; / 父節(jié)點指

28、針父節(jié)點指針int LChild; ; / int LChild; ; / 當(dāng)且僅當(dāng)是父節(jié)點的左孩子當(dāng)且僅當(dāng)是父節(jié)點的左孩子時，取值為時，取值為1 1struct HeapNodestruct HeapNode bbnode bbnode * *ptr; / ptr; / 活節(jié)點指針活節(jié)點指針 float uweight; / float uweight; / 活節(jié)點的重量上限活節(jié)點的重量上限 int level; ; / int level; ; / 活節(jié)點所在層活節(jié)點所在層 同樣為了突出算法本身的思想，對堆操作也只進(jìn)行抽象的描述：同樣為了突出算法本身的思想，對堆操作也只進(jìn)行抽象的描述：用用

29、HeapNodeHeapNode代表隊列類型，則代表隊列類型，則HeapNode HHeapNode H；定義了一個堆；定義了一個堆H H，相，相關(guān)操作有：關(guān)操作有：Insert (QInsert (Q，) )表示入堆；表示入堆； DeleteMax (QDeleteMax (Q，););表示出堆。表示出堆。 Design and Analysis of Computer Algorithms算法設(shè)計算法設(shè)計3 3（4 4）大連海事大學(xué)AddLiveNode(float wt, int lev,bbnode AddLiveNode(float wt, int lev,bbnode * *E,

30、int ch)E, int ch)bbnode bbnode * *b = new bbnode;b = new bbnode; b -parent = E; b -parent = E; b-LChild = ch; b-LChild = ch; HeapNode N; HeapNode N; N.uweight = wt; N.uweight = wt; N.level=lev; N.level=lev; N.ptr=b; N.ptr=b; Insert(H Insert(H，N) ;N) ; Design and Analysis of Computer Algorithms大連海事大學(xué)

31、MaxLoading(float c, int n, int bestx)MaxLoading(float c, int n, int bestx)froat r100,Ewfroat r100,Ew，bestw=0; rn = 0;bestw=0; rn = 0;for (int j = n-1; j 0; j-) rj=rj+1 + wj+1;for (int j = n-1; j 0; j-) rj=rj+1 + wj+1;int i = 1; bbnode int i = 1; bbnode * *E = 0; Ew = 0; / E = 0; Ew = 0; / 搜索子集空間樹搜索子

32、集空間樹while (i != n+1) / while (i != n+1) / 不在葉子上不在葉子上 if (Ew + wi = c) / if (Ew + wi = c) / 可行的左孩子可行的左孩子 AddLiveNode(E, Ew+wi+ri, 1, i+1);AddLiveNode(E, Ew+wi+ri, 1, i+1); if (bestwEw+wi) bestw=Ew+wi; if (bestwEw+wi) bestw=Ew+wi; if(bestwEw+ri) AddLiveNode(E, Ew+ri, 0, i+1); if(bestw 0; j-) for (int

33、j = n; j 0; j-) bestxj = E-LChild; E = E-parent; bestxj = E-LChild; E = E-parent;return Ew;return Ew; Design and Analysis of Computer AlgorithmsDesign and Analysis of Computer Algorithms算法說明：算法說明： 算法的復(fù)雜度仍為算法的復(fù)雜度仍為O O（2 2n n），但通過限界策略，并沒有搜），但通過限界策略，并沒有搜索子集樹中的所有結(jié)點，且，由于每次都是選取的最接近最優(yōu)索子集樹中的所有結(jié)點，且，由于每次都是選取的

34、最接近最優(yōu)解的結(jié)點擴(kuò)展，所以一當(dāng)搜索到葉結(jié)點作解的結(jié)點擴(kuò)展，所以一當(dāng)搜索到葉結(jié)點作E結(jié)點時算法就可以結(jié)點時算法就可以結(jié)束了。算法結(jié)束時堆并不一定為空。結(jié)束了。算法結(jié)束時堆并不一定為空。 Design and Analysis of Computer AlgorithmsDesign and Analysis of Computer Algorithms小結(jié)討論：小結(jié)討論：FIFO搜索或搜索或LIFO搜索也可以通過加入搜索也可以通過加入“限界限界”策略加速搜索策略加速搜索嗎？嗎？那與優(yōu)先隊列式分支限界法那與優(yōu)先隊列式分支限界法LCLC檢索的區(qū)別在哪兒呢？檢索的區(qū)別在哪兒呢？ 答案：由于答案：由于

35、FIFO搜索或搜索或LIFO搜索是盲目擴(kuò)展地結(jié)點，當(dāng)前最優(yōu)解搜索是盲目擴(kuò)展地結(jié)點，當(dāng)前最優(yōu)解距真正的最優(yōu)解距離較大，作為距真正的最優(yōu)解距離較大，作為“界界”所起到的剪枝作用很有限，所起到的剪枝作用很有限，不能有效提高搜索速度。其實看了下面的例子大家會發(fā)現(xiàn)，優(yōu)先隊不能有效提高搜索速度。其實看了下面的例子大家會發(fā)現(xiàn)，優(yōu)先隊列式擴(kuò)展結(jié)點的過程，一開始實際是在進(jìn)行類似列式擴(kuò)展結(jié)點的過程，一開始實際是在進(jìn)行類似“深度優(yōu)先深度優(yōu)先”的搜的搜索。索。 例如：例如：W=10，30，50，C1=60， 所構(gòu)成的子集樹如下圖所表示：所構(gòu)成的子集樹如下圖所表示：Design and Analysis of Comp

36、uter AlgorithmsFIFOFIFO限界搜索過程為：限界搜索過程為： 大連海事大學(xué)1 1） 初始隊列中只有結(jié)點初始隊列中只有結(jié)點A A；2 2） 結(jié)點結(jié)點A A變?yōu)樽優(yōu)镋-E-結(jié)點擴(kuò)充結(jié)點擴(kuò)充B B入隊，入隊，bestw=10bestw=10； 結(jié)點結(jié)點C C的裝載上界為的裝載上界為30+50=80 bestw30+50=80 bestw，也入隊；，也入隊；3 3） 結(jié)點結(jié)點B B變?yōu)樽優(yōu)镋-E-結(jié)點擴(kuò)充結(jié)點擴(kuò)充D D入隊，入隊，bestw=40bestw=40； 結(jié)點結(jié)點E E的裝載上界為的裝載上界為60 bestw60 bestw，也入隊；，也入隊；4 4） 結(jié)點結(jié)點C C變?yōu)樽?/p>

37、為E-E-結(jié)點擴(kuò)充結(jié)點擴(kuò)充F F入隊，入隊，bestwbestw仍為仍為4040； 結(jié)點結(jié)點G G的裝載上界為的裝載上界為50 bestw50 bestw，也入隊；，也入隊；5 5） 結(jié)點結(jié)點D D變?yōu)樽優(yōu)镋-E-結(jié)點，葉結(jié)點結(jié)點，葉結(jié)點H H超過容量，超過容量， 葉結(jié)點葉結(jié)點I I的裝載為的裝載為4040，bestwbestw仍為仍為4040；6 6） 結(jié)點結(jié)點E E變?yōu)樽優(yōu)镋-E-結(jié)點，葉結(jié)點結(jié)點，葉結(jié)點J J裝載量為裝載量為6060，bestwbestw為為6060； 葉結(jié)點葉結(jié)點K K被剪掉；被剪掉；7 7） 結(jié)點結(jié)點F F變?yōu)樽優(yōu)镋-E-結(jié)點，葉結(jié)點結(jié)點，葉結(jié)點L L超過容量，超過容

38、量，bestwbestw為為6060； 葉結(jié)點葉結(jié)點M M被剪掉；被剪掉；8 8） 結(jié)點結(jié)點G G變?yōu)樽優(yōu)镋-E-結(jié)點，葉結(jié)點結(jié)點，葉結(jié)點N N、O O都被剪掉；都被剪掉； 此時隊列空算法結(jié)束。此時隊列空算法結(jié)束。 Design and Analysis of Computer AlgorithmsLC-LC-搜索的過程如下：搜索的過程如下： 大連海事大學(xué)1 1） 初始隊列中只有結(jié)點初始隊列中只有結(jié)點A A；2 2） 結(jié)點結(jié)點A A變?yōu)樽優(yōu)镋-E-結(jié)點擴(kuò)充結(jié)點擴(kuò)充B B入堆，入堆，bestw=10bestw=10；結(jié)點結(jié)點C C的裝載上界為的裝載上界為30+50=80 bestw30+50=8

39、0 bestw，也入堆；堆中，也入堆；堆中B B上界為上界為9090在優(yōu)先隊列首。在優(yōu)先隊列首。3 3） 結(jié)點結(jié)點B B變?yōu)樽優(yōu)镋-E-結(jié)點擴(kuò)充結(jié)點擴(kuò)充D D入堆，入堆，bestw=40bestw=40；結(jié)點結(jié)點E E的裝載上界為的裝載上界為60 bestw60 bestw，也入堆；此時堆中，也入堆；此時堆中D D上界為上界為9090為優(yōu)先隊列首。為優(yōu)先隊列首。4 4） 結(jié)點結(jié)點D D變?yōu)樽優(yōu)镋-E-結(jié)點，葉結(jié)點結(jié)點，葉結(jié)點H H超過容量，葉結(jié)點超過容量，葉結(jié)點I I的裝載為的裝載為4040入堆，入堆， bestwbestw仍為仍為4040；此時堆中；此時堆中C C上界為上界為8080為優(yōu)先隊

40、列首。為優(yōu)先隊列首。5 5） 結(jié)點結(jié)點C C變?yōu)樽優(yōu)镋-E-結(jié)點擴(kuò)充結(jié)點擴(kuò)充F F入堆，入堆，bestwbestw仍為仍為4040；結(jié)點結(jié)點G G的裝載上界為的裝載上界為50 bestw50 bestw，也入堆；此時堆中，也入堆；此時堆中E E上界為上界為6060為優(yōu)先隊列首。為優(yōu)先隊列首。6 6） 結(jié)點結(jié)點E E變?yōu)樽優(yōu)镋-E-結(jié)點，葉結(jié)點結(jié)點，葉結(jié)點J J裝載量為裝載量為6060入堆，入堆，bestwbestw變?yōu)樽優(yōu)?060； 葉結(jié)點葉結(jié)點K K上界為上界為10bestw10bestw被剪掉；此時堆中被剪掉；此時堆中J J上界為上界為6060為優(yōu)先隊列首。為優(yōu)先隊列首。7 7） 結(jié)點結(jié)點

41、J J變?yōu)樽優(yōu)镋-E-結(jié)點，擴(kuò)展的層次為結(jié)點，擴(kuò)展的層次為4 4算法結(jié)束。算法結(jié)束。 雖然此時堆并不空，但可以確定已找到了最優(yōu)解。雖然此時堆并不空，但可以確定已找到了最優(yōu)解。Design and Analysis of Computer Algorithms大連海事大學(xué)FIFO限界算法搜索解空間的過程是按圖限界算法搜索解空間的過程是按圖5-26子集樹中字母子集樹中字母序進(jìn)行的，而優(yōu)先隊列限界搜索解空間的過程是：序進(jìn)行的，而優(yōu)先隊列限界搜索解空間的過程是：A-B-D-C-E-J看了上面的例子大家會發(fā)現(xiàn)，優(yōu)先隊列法擴(kuò)展結(jié)點的過程，看了上面的例子大家會發(fā)現(xiàn)，優(yōu)先隊列法擴(kuò)展結(jié)點的過程，一開始實際是在進(jìn)

42、行類似一開始實際是在進(jìn)行類似“深度優(yōu)先深度優(yōu)先”的搜索。的搜索。Design and Analysis of Computer Algorithms553 算法框架算法框架 上一小節(jié)的例子是求最大值的最優(yōu)化問題，下面我們以求找上一小節(jié)的例子是求最大值的最優(yōu)化問題，下面我們以求找最小成本的最優(yōu)化問題，給出最小成本的最優(yōu)化問題，給出FIFO分支搜索算法框架。分支搜索算法框架。 假定問題解空間樹為假定問題解空間樹為T，T至少包含一個解結(jié)點（即答案結(jié)至少包含一個解結(jié)點（即答案結(jié)點）。點）。u為當(dāng)前的最優(yōu)解，初值為一個較大的數(shù)為當(dāng)前的最優(yōu)解，初值為一個較大的數(shù);E表示當(dāng)前擴(kuò)表示當(dāng)前擴(kuò)展的活結(jié)點，展的活結(jié)

43、點，x為為E的兒子，的兒子，s(x)為結(jié)點為結(jié)點x下界函數(shù)，當(dāng)其值比下界函數(shù)，當(dāng)其值比u大時，不可能為最優(yōu)解，不繼續(xù)搜索此分支，該結(jié)點不入隊；大時，不可能為最優(yōu)解，不繼續(xù)搜索此分支，該結(jié)點不入隊；當(dāng)其值比當(dāng)其值比u小時，可能達(dá)到最優(yōu)解，繼續(xù)搜索此分支，該結(jié)點入小時，可能達(dá)到最優(yōu)解，繼續(xù)搜索此分支，該結(jié)點入隊；隊；cost（X）為當(dāng)前葉結(jié)點所在分支的解。）為當(dāng)前葉結(jié)點所在分支的解。算法框架如下：算法框架如下：大連海事大學(xué)Design and Analysis of Computer Algorithms2 2）：）： 大連海事大學(xué)search（T） /為找出最小成本答案結(jié)點檢索為找出最小成本答案

44、結(jié)點檢索T。 leaf=0; 初始化隊；初始化隊；ADDQ（T）；）； /根結(jié)點入隊根結(jié)點入隊 parent（E）=0； /記錄擴(kuò)展路徑，當(dāng)前結(jié)點的父結(jié)點記錄擴(kuò)展路徑，當(dāng)前結(jié)點的父結(jié)點 while （隊不空）（隊不空）DELETEQ(E) /隊首結(jié)點出隊為新的隊首結(jié)點出隊為新的E結(jié)點；結(jié)點；for （E的每個兒子的每個兒子 X） if (s（X）u) /當(dāng)是可能的最優(yōu)解時入隊當(dāng)是可能的最優(yōu)解時入隊 ADD Q（X）；）； parent（X）=E; if (X是解結(jié)點是解結(jié)點 ) /x為葉結(jié)點為葉結(jié)點 U=min（cost（X），），u）; leaf=x; /方案的葉結(jié)點存儲在方案的葉結(jié)點存儲在

45、leaf中中 Design and Analysis of Computer Algorithms3 3）：）： 大連海事大學(xué) print（”least cost=，u）；）； while （leaf0） /輸出最優(yōu)解方案輸出最優(yōu)解方案 print（leaf）；）； leaf=parent（leaf）；）；Design and Analysis of Computer Algorithms大連海事大學(xué) 找最小成本的找最小成本的LC分支分支- -限界算法限界算法框架框架與與 F FIFO分支分支- -限界算法限界算法框框架結(jié)構(gòu)大致相同，只是擴(kuò)展結(jié)點的順序不同，因而存儲活結(jié)點架結(jié)構(gòu)大致相同，只是擴(kuò)

46、展結(jié)點的順序不同，因而存儲活結(jié)點的數(shù)據(jù)結(jié)構(gòu)不同。的數(shù)據(jù)結(jié)構(gòu)不同。 F FIFO分支分支- -限界算法用隊限界算法用隊存儲活結(jié)點，存儲活結(jié)點，LC分分支支- -限界算法用堆限界算法用堆存儲活結(jié)點，以保證比較優(yōu)良的結(jié)點先被擴(kuò)展。存儲活結(jié)點，以保證比較優(yōu)良的結(jié)點先被擴(kuò)展。且對于且對于LC分支分支- -限界算法，一當(dāng)擴(kuò)展到葉結(jié)點就已經(jīng)找到最優(yōu)限界算法，一當(dāng)擴(kuò)展到葉結(jié)點就已經(jīng)找到最優(yōu)解，可以停止搜索。解，可以停止搜索。Design and Analysis of Computer Algorithms56 圖的搜索算法小結(jié)圖的搜索算法小結(jié) 大連海事大學(xué)1 1深度優(yōu)先搜索與廣度優(yōu)先搜索算法有何區(qū)別深度優(yōu)先

47、搜索與廣度優(yōu)先搜索算法有何區(qū)別 通常深度優(yōu)先搜索法不全部保留結(jié)點，擴(kuò)展完的結(jié)點從數(shù)據(jù)存通常深度優(yōu)先搜索法不全部保留結(jié)點，擴(kuò)展完的結(jié)點從數(shù)據(jù)存儲結(jié)構(gòu)棧中彈出刪去，這樣，一般在數(shù)據(jù)棧中存儲的結(jié)點數(shù)就是解儲結(jié)構(gòu)棧中彈出刪去，這樣，一般在數(shù)據(jù)棧中存儲的結(jié)點數(shù)就是解空間樹的深度，因此它占用空間較少。所以，當(dāng)搜索樹的結(jié)點較多，空間樹的深度，因此它占用空間較少。所以，當(dāng)搜索樹的結(jié)點較多，用其它方法易產(chǎn)生內(nèi)存溢出時，深度優(yōu)先搜索不失為一種有效的求用其它方法易產(chǎn)生內(nèi)存溢出時，深度優(yōu)先搜索不失為一種有效的求解方法。解方法。廣度優(yōu)先搜索算法，一般需存儲產(chǎn)生的所有結(jié)點，占用的存儲廣度優(yōu)先搜索算法，一般需存儲產(chǎn)生的所有

48、結(jié)點，占用的存儲空間要比深度優(yōu)先搜索大得多，因此，程序設(shè)計中，必須考慮溢出空間要比深度優(yōu)先搜索大得多，因此，程序設(shè)計中，必須考慮溢出和節(jié)省內(nèi)存空間的問題。但廣度優(yōu)先搜索法一般無回溯操作，即入和節(jié)省內(nèi)存空間的問題。但廣度優(yōu)先搜索法一般無回溯操作，即入棧和出棧的操作，所以運行速度比深度優(yōu)先搜索要快些。棧和出棧的操作，所以運行速度比深度優(yōu)先搜索要快些。 Design and Analysis of Computer Algorithms大連海事大學(xué)2 2回溯與分支限界法回溯與分支限界法 回溯法以深度優(yōu)先的方式搜索解空間樹回溯法以深度優(yōu)先的方式搜索解空間樹T T，而分支限界法則，而分支限界法則以廣度優(yōu)

49、先或以最小耗費優(yōu)先的方式搜索解空間樹以廣度優(yōu)先或以最小耗費優(yōu)先的方式搜索解空間樹T T。由于它由于它們在問題的解空間樹們在問題的解空間樹T上搜索的方法不同，適合解決的問題上搜索的方法不同，適合解決的問題也就不同。一般情況下，回溯法的求解目標(biāo)是找出也就不同。一般情況下，回溯法的求解目標(biāo)是找出T中滿足中滿足約束條件的所有解的方案，而分支限界法的求解目標(biāo)則是找約束條件的所有解的方案，而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出出滿足約束條件的一個解，或是在滿足約束條件的解中找出使用某一目標(biāo)函數(shù)值達(dá)到極大或極小的解，即在某種意義下使用某一目標(biāo)函數(shù)值達(dá)到極大或極小的解

50、，即在某種意義下的最優(yōu)解。的最優(yōu)解。相對而言，分支限界算法的解空間比回溯法大得相對而言，分支限界算法的解空間比回溯法大得多，多，因此當(dāng)內(nèi)存容量有限時，回溯法成功的可能性更大。因此當(dāng)內(nèi)存容量有限時，回溯法成功的可能性更大。下表列出了回溯法和分支限界法的一些區(qū)別：下表列出了回溯法和分支限界法的一些區(qū)別：Design and Analysis of Computer AlgorithmsDesign and Analysis of Computer Algorithms3 3. .Design and Analysis of Computer Algorithms在處理最優(yōu)問題時，采用窮舉法、回溯法

51、或分支限界法都可以在處理最優(yōu)問題時，采用窮舉法、回溯法或分支限界法都可以通過利用當(dāng)前最優(yōu)解和上界函數(shù)加速。僅就對限界剪支的效率而通過利用當(dāng)前最優(yōu)解和上界函數(shù)加速。僅就對限界剪支的效率而言，優(yōu)先隊列的分支限界法顯然要更充分一些。在窮舉法中通過言，優(yōu)先隊列的分支限界法顯然要更充分一些。在窮舉法中通過上界函數(shù)與當(dāng)前情況下函數(shù)值的比較可以直接略過不合要求的情上界函數(shù)與當(dāng)前情況下函數(shù)值的比較可以直接略過不合要求的情況而省去了更進(jìn)一步的枚舉和判斷；回溯法則因為層次的劃分，況而省去了更進(jìn)一步的枚舉和判斷；回溯法則因為層次的劃分，可以在上界函數(shù)值小于當(dāng)前最優(yōu)解時，剪去以該結(jié)點為根的子樹，可以在上界函數(shù)值小于當(dāng)

52、前最優(yōu)解時，剪去以該結(jié)點為根的子樹，也就是節(jié)省了搜索范圍；分支限界法在這方面除了可以做到回溯也就是節(jié)省了搜索范圍；分支限界法在這方面除了可以做到回溯法能做到的之外，同時若采用優(yōu)先隊列的分支限界法，用上界函法能做到的之外，同時若采用優(yōu)先隊列的分支限界法，用上界函數(shù)作為活結(jié)點的優(yōu)先級，一旦有葉結(jié)點成為當(dāng)前擴(kuò)展結(jié)點，就意數(shù)作為活結(jié)點的優(yōu)先級，一旦有葉結(jié)點成為當(dāng)前擴(kuò)展結(jié)點，就意味著該葉結(jié)點所對應(yīng)的解即為最優(yōu)解，可以立即終止其余的過程。味著該葉結(jié)點所對應(yīng)的解即為最優(yōu)解，可以立即終止其余的過程。在前面的例題中曾說明，優(yōu)先隊列的分支限界法更象是有選擇、在前面的例題中曾說明，優(yōu)先隊列的分支限界法更象是有選擇、

53、有目的地進(jìn)行深度優(yōu)先搜索，時間效率、空間效率都是比較高的。有目的地進(jìn)行深度優(yōu)先搜索，時間效率、空間效率都是比較高的。大連海事大學(xué)Design and Analysis of Computer Algorithms5 5. . 大連海事大學(xué) 3動態(tài)規(guī)劃與搜索算法動態(tài)規(guī)劃與搜索算法撇開時空效率的因素不談，在解決最優(yōu)化問題的算法中，搜索撇開時空效率的因素不談，在解決最優(yōu)化問題的算法中，搜索可以說是可以說是“萬能萬能”的。所以動態(tài)規(guī)劃可以解決的問題，搜索也一的。所以動態(tài)規(guī)劃可以解決的問題，搜索也一定可以解決。動態(tài)規(guī)劃要求階段決策具有無后向性，而搜索算法定可以解決。動態(tài)規(guī)劃要求階段決策具有無后向性，而搜索算法沒有此限止。沒有此限止。動態(tài)規(guī)劃是自底向上的遞推求解，而無論深度優(yōu)先搜索或廣度動態(tài)規(guī)劃是自底向上的遞推求解，而無論深度優(yōu)先搜索或廣度優(yōu)先搜索都是自頂向下求解。利用動態(tài)規(guī)劃法