第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基本思想基本思想 分支搜索法也是一種在問(wèn)題解空間上進(jìn)行嘗試搜索算法。所謂分支搜索法也是一種在問(wèn)題解空間上進(jìn)行嘗試搜索算法。所謂“分支分支”是采用廣度優(yōu)先的策略，依次生成是采用廣度優(yōu)先的策略，依次生成E-結(jié)點(diǎn)所有分支，也就結(jié)點(diǎn)所有分支，也就是所有的兒子結(jié)點(diǎn)。和回溯法

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

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

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

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

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

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

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

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

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

11、小于5050；而擴(kuò)展結(jié)點(diǎn)；而擴(kuò)展結(jié)點(diǎn)2 2時(shí)，發(fā)現(xiàn)此分支的時(shí)，發(fā)現(xiàn)此分支的“裝載上界裝載上界”為為w w2 2+w+w3 3=2050=2050，無(wú)需搜索此分支，結(jié)點(diǎn)，無(wú)需搜索此分支，結(jié)點(diǎn)2 2不必入隊(duì)。不必入隊(duì)。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不僅僅對(duì)葉結(jié)點(diǎn)計(jì)算，不僅僅對(duì)葉結(jié)點(diǎn)計(jì)算，每次搜索裝載情況（搜索左兒子）時(shí)，都重新確定每次搜索裝載情況（搜索左兒子）時(shí)，都重新確定bestwbestw的值。的值。為了方便計(jì)算一個(gè)分支的為了方便計(jì)算一個(gè)分支的“裝載上界裝載上界

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; / 不是葉子不是葉子, , 添加到隊(duì)列中

16、添加到隊(duì)列中b-weight = wt;b-weight = wt;b-parent = E;b-parent = E;b-LChild = ch; /b-LChild = ch; /新節(jié)點(diǎn)是左孩子時(shí)新節(jié)點(diǎn)是左孩子時(shí)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é)點(diǎn)中余下的重量節(jié)點(diǎn)中余下的重量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é)點(diǎn)的左孩子節(jié)點(diǎn)的左孩子 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 ) ; / 下一個(gè)下一個(gè)E-E-節(jié)點(diǎn)節(jié)點(diǎn)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 ) ; / 下一個(gè)下一個(gè)E-E-節(jié)點(diǎn)節(jié)點(diǎn) i + + ; / E-i + +

20、; / E-節(jié)點(diǎn)的層次節(jié)點(diǎn)的層次 r = r - wi; / E-r = r - wi; / E-節(jié)點(diǎn)中余下的重量節(jié)點(diǎn)中余下的重量 Ew = E- w e i g h t ; / Ew = E- w e i g h t ; / 新的新的E-E-節(jié)點(diǎn)的重量節(jié)點(diǎn)的重量 / / 沿著從沿著從b e s t Eb e s t E到根的路徑構(gòu)造到根的路徑構(gòu)造x x ，x nx n由由AddLiveNodeAddLiveNode來(lái)設(shè)置來(lái)設(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è)計(jì)算法設(shè)計(jì)3：用優(yōu)先隊(duì)列式分支限界法解決【例】的問(wèn)題大連海事大學(xué) 上一節(jié)介紹的優(yōu)先隊(duì)列式擴(kuò)展方式，若不加入限界策略其實(shí)是上一節(jié)介紹的優(yōu)先隊(duì)列式擴(kuò)展方式，若不加入限界策略其實(shí)是無(wú)意義的。因?yàn)橐f(shuō)明解的最優(yōu)性，不搜索完所有問(wèn)題空間是不能無(wú)意義的。因?yàn)橐f(shuō)明解的最優(yōu)性，不搜索完

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

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

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

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

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

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

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

29、HeapNodeHeapNode代表隊(duì)列類(lèi)型，則代表隊(duì)列類(lèi)型，則HeapNode HHeapNode H；定義了一個(gè)堆；定義了一個(gè)堆H H，相，相關(guān)操作有：關(guān)操作有：Insert (QInsert (Q，) )表示入堆；表示入堆； DeleteMax (QDeleteMax (Q，););表示出堆。表示出堆。 Design and Analysis of Computer Algorithms算法設(shè)計(jì)算法設(shè)計(jì)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; / 搜索子集空間樹(shù)搜索子

32、集空間樹(shù)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算法說(shuō)明：算法說(shuō)明： 算法的復(fù)雜度仍為算法的復(fù)雜度仍為O O（2 2n n），但通過(guò)限界策略，并沒(méi)有搜），但通過(guò)限界策略，并沒(méi)有搜索子集樹(shù)中的所有結(jié)點(diǎn)，且，由于每次都是選取的最接近最優(yōu)索子集樹(shù)中的所有結(jié)點(diǎn)，且，由于每次都是選取的

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

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

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

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

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

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

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

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

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

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

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

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é)點(diǎn)的順序不同，因而存儲(chǔ)活結(jié)點(diǎn)架結(jié)構(gòu)大致相同，只是擴(kuò)

46、展結(jié)點(diǎn)的順序不同，因而存儲(chǔ)活結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)不同。的數(shù)據(jù)結(jié)構(gòu)不同。 F FIFO分支分支- -限界算法用隊(duì)限界算法用隊(duì)存儲(chǔ)活結(jié)點(diǎn)，存儲(chǔ)活結(jié)點(diǎn)，LC分分支支- -限界算法用堆限界算法用堆存儲(chǔ)活結(jié)點(diǎn)，以保證比較優(yōu)良的結(jié)點(diǎn)先被擴(kuò)展。存儲(chǔ)活結(jié)點(diǎn)，以保證比較優(yōu)良的結(jié)點(diǎn)先被擴(kuò)展。且對(duì)于且對(duì)于LC分支分支- -限界算法，一當(dāng)擴(kuò)展到葉結(jié)點(diǎn)就已經(jīng)找到最優(yōu)限界算法，一當(dāng)擴(kuò)展到葉結(jié)點(diǎn)就已經(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é)點(diǎn)，擴(kuò)展完的結(jié)點(diǎn)從數(shù)據(jù)存通常深度優(yōu)先搜索法不全部保留結(jié)點(diǎn)，擴(kuò)展完的結(jié)點(diǎn)從數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)棧中彈出刪去，這樣，一般在數(shù)據(jù)棧中存儲(chǔ)的結(jié)點(diǎn)數(shù)就是解儲(chǔ)結(jié)構(gòu)棧中彈出刪去，這樣，一般在數(shù)據(jù)棧中存儲(chǔ)的結(jié)點(diǎn)數(shù)就是解空間樹(shù)的深度，因此它占用空間較少。所以，當(dāng)搜索樹(shù)的結(jié)點(diǎn)較多，空間樹(shù)的深度，因此它占用空間較少。所以，當(dāng)搜索樹(shù)的結(jié)點(diǎn)較多，用其它方法易產(chǎn)生內(nèi)存溢出時(shí)，深度優(yōu)先搜索不失為一種有效的求用其它方法易產(chǎn)生內(nèi)存溢出時(shí)，深度優(yōu)先搜索不失為一種有效的求解方法。解方法。廣度優(yōu)先搜索算法，一般需存儲(chǔ)產(chǎn)生的所有結(jié)點(diǎn)，占用的存儲(chǔ)廣度優(yōu)先搜索算法，一般需存儲(chǔ)產(chǎn)生的所有

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

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

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

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

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

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