算法分析及設計 分支限界法

1、第6章 分支限界法6.1分支限界法的基本思想6.2單源最短路徑問題6.3 0-1背包問題本章主要知識點：6.1 分支限界法的基本思想（1）求解目標求解目標：回溯法的求解目標是找出解空間樹中滿 足約束條件的所有解，而分支限界法的求解目標則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解。 1. 1. 分支限界法與回溯法的不同分支限界法與回溯法的不同（2）搜索方式的不同搜索方式的不同：回溯法以深度優(yōu)先的方式搜索解 空間樹，而分支限界法則以廣度優(yōu)先或以最小耗費優(yōu) 先的方式搜索解空間樹。 6.1分支限界法的基本思想 分支限界法常以廣度優(yōu)先或以最小耗費（最大效益）優(yōu)先的方式搜

2、索問題的解空間樹。 2. 分支限界法基本思想在分支限界法中，每一個活結點只有一次機會成為擴展結點。活結點一旦成為擴展結點，就一次性產(chǎn)生其所有兒子結點。在這些兒子結點中，導致不可行解或導致非最優(yōu)解的兒子結點被舍棄，其余兒子結點被加入活結點表中。此后，從活結點表中取下一結點成為當前擴展結點，并重復上述結點擴展過程。這個過程一直持續(xù)到找到所需的解或活結點表為空時為止。6.1分支限界法的基本思想3. 常見的兩種分支限界法（1）隊列式(FIFO)分支限界法 按照隊列先進先出（FIFO）原則選取下一個節(jié)點為擴展節(jié)點。 （2）優(yōu)先隊列式分支限界法 按照優(yōu)先隊列中規(guī)定的優(yōu)先級選取優(yōu)先級最高的節(jié)點成為當前擴展節(jié)

3、點。 例如：考慮n=3時0-1背包問題，其中w=16,15,15, p=45,25,25,c=30。6.1分支限界法的基本思想 解空間 隊列分支限界法6.2 單源最短路徑問題 從根結點A開始。初始時活結點隊列為空，結點A是當前的擴展結點。 結點A的2個兒子結點B和C均為可行結點，故將這兩個兒子結點按從左到右的順序加入到活結點隊列，并舍棄當前的擴展結點A。 以先進先出的原則，下一個擴展結點是活結點隊列的隊首結點B。擴展結點B得到其兒子結點D和E。由于D是不可行結點，故被舍棄。E是可行結點，被加入活結點隊列。 接下來，C成為當前的擴展結點，它的2個兒子結點F和G 均為可行結點，因此被加入到活結點隊

4、列中。6.2 單源最短路徑問題 擴展下一個結點E得到J和K。J是不可行結點，因而被舍棄。K是可行葉結點，表示問題所求問題的一個可行解，其價值為45. 當前的活結點隊列的首結點F成為下一個擴展結點。它的2個兒子結點L和M均為葉結點。L表示獲得的價值為50的可行解，M表示獲得價值為25的可行解。G是最后一個擴展結點，其兒子結點N和O均為可行葉結點。最后活結點隊列已空，算法終止。算法搜索到的最優(yōu)值為50. 從根結點A開始。用一個極大堆表示活結點表的優(yōu)先隊列。6.2 單源最短路徑問題 優(yōu)先隊列式分支限界法初始堆為空，擴展結點A得到它的2個兒子結點B和C。這2個結點均為可行結點，因此被加入到堆中，結點A

5、被舍棄。結點B獲得的當前價值為40，而結點C的當前價值為0.由于B的價值大于C的價值，所以B是堆中的最大元素，從而成為下一個擴展結點。 擴展結點B得到結點D和E。D是不可行結點，因而被舍棄。E是可行結點被加入到堆中，E的價值為40，成為當前堆中的最大元素，從而成為下一個擴展結點。 擴展結點E得到2個葉結點J和K。J是不可行結點被舍棄。K是一個可行葉結點，表示問題的一個可行解，其價值為45.此時堆中僅剩下一個活結點C，它成為當前的擴展結點。它的2個兒子結點F和G均為可行結點，因此被插入到當前堆中。6.2 單源最短路徑問題 結點F的價值為25，是堆中最大元素，成為下一個擴展結點。F的2個兒子結點L

6、和M均為葉結點。葉結點L相應于價值為50的可行解。葉結點M相應于價值為25的可行解。葉結點L所相應的解成為最優(yōu)解。最后，結點G成為擴展結點，其兒子結點N和O均為葉結點，它們的價值分別為25和0. 接下來，存儲活結點的堆已空，算法終止。算法搜索到的最優(yōu)值為50.第6章 分支限界法6.1分支限界法的基本思想6.2單源最短路徑問題6.3 0-1背包問題本章主要知識點：6.1分支限界法的基本思想 分支限界法常以廣度優(yōu)先或以最小耗費（最大效益）優(yōu)先的方式搜索問題的解空間樹。 2. 分支限界法基本思想在分支限界法中，每一個活結點只有一次機會成為擴展結點。活結點一旦成為擴展結點，就一次性產(chǎn)生其所有兒子結點。

7、在這些兒子結點中，導致不可行解或導致非最優(yōu)解的兒子結點被舍棄，其余兒子結點被加入活結點表中。此后，從活結點表中取下一結點成為當前擴展結點，并重復上述結點擴展過程。這個過程一直持續(xù)到找到所需的解或活結點表為空時為止。6.1分支限界法的基本思想3. 常見的兩種分支限界法（1）隊列式(FIFO)分支限界法 按照隊列先進先出（FIFO）原則選取下一個節(jié)點為擴展節(jié)點。 （2）優(yōu)先隊列式分支限界法 按照優(yōu)先隊列中規(guī)定的優(yōu)先級選取優(yōu)先級最高的節(jié)點成為當前擴展節(jié)點。6.2 單源最短路徑問題1. 問題描述 給定帶權有向圖G =(V,E)，其中每條邊的權是非負實數(shù)。另外，還給定V中的一個頂點，稱為源源?，F(xiàn)在要計算

8、從源到所有其它各頂點的最短路長度最短路長度。這里路的長度是指路上各邊權之和。這個問題通常稱為單源最短路徑單源最短路徑問題問題。h2g2n5j3k3l5i5m1o5p2f9e2d7a2b3c4u3q1r2字母旁邊的數(shù)字為路長字母旁邊的數(shù)字為路長012345678910下面以一個例子來說明單源最短路徑問題：在下圖所給的有向圖G中，每一邊都有一個非負邊權。要求圖G的從源頂點s到目標頂點t之間的最短路徑。6.2 單源最短路徑問題6.2 單源最短路徑問題 下圖是用優(yōu)先隊列式分支限界法解有向圖G的單源最短路徑問題產(chǎn)生的解空間樹。其中，每一個結點旁邊的數(shù)字表示該結點所對應的當前路長。6.2 單源最短路徑問題

9、 2. 算法思想 解單源最短路徑問題的優(yōu)先隊列式分支限界法用一極小堆來存儲活結點表。其優(yōu)先級是結點所對應的當前路長。 算法從圖G的源頂點s和空優(yōu)先隊列開始。結點s被擴展后，它的兒子結點被依次插入堆中。此后，算法從堆中取出具有最小當前路長的結點作為當前擴展結點，并依次檢查與當前擴展結點相鄰的所有頂點。如果從當前擴如果從當前擴展結點展結點i i到頂點到頂點j j有邊可達，且從源出發(fā)，途經(jīng)頂點有邊可達，且從源出發(fā)，途經(jīng)頂點i i再到再到頂點頂點j j的所相應的路徑的長度小于當前最優(yōu)路徑長度，則的所相應的路徑的長度小于當前最優(yōu)路徑長度，則將該頂點作為活結點插入到活結點優(yōu)先隊列中。將該頂點作為活結點插入

10、到活結點優(yōu)先隊列中。這個結點的擴展過程一直繼續(xù)到活結點優(yōu)先隊列為空時為止。6.2 單源最短路徑問題 3. 剪枝策略 在算法擴展結點的過程中，一旦發(fā)現(xiàn)一個結點的下界不小于當前找到的最短路長，則算法剪去以該結點為根的子樹。 在算法中，利用結點間的控制關系進行剪枝。從源頂點s出發(fā)，2條不同路徑到達圖G的同一頂點。由于兩條路徑的路長不同，因此可以將路長長的路徑所對應的樹中的結點為根的子樹剪去。6.2 單源最短路徑問題 while (true) / 搜索問題的解空間 for (int j=1;j=n;j+) if(aenode.ij Float.MAX_VALUE & enode.length+

11、aenode.ij distj) / 頂點i到頂點j可達，且滿足控制約束 distj=enode.length+aenode.ij; pj=enode.i; HeapNode node = new HeapNode(j,distj); heap.put(node); / 加入活結點優(yōu)先隊列 if (heap.isEmpty() break; else enode = (HeapNode) heap.removeMin(); 頂點頂點i i和和j j間有邊，且此間有邊，且此路徑長小于原先從原點路徑長小于原先從原點到到j j的路徑長的路徑長 4. 算法實現(xiàn)46.2 單源最短路徑問題 算法從源節(jié)點S

12、和空優(yōu)先隊列開始。 5. 例子實現(xiàn) S被擴展，3個子節(jié)點1、2、3被插入堆中。計算0-1、0-2和0-3當前最短路徑長為2。 將當前路徑最短的節(jié)點1擴展，即走0-1-2,0-1-5,0-1-4計算，但是在計算0-1-2過程中當前最短路徑為3 (0-2)，剪掉0-1-2上以2為根的子樹。將2進行擴展，走bg和bf。將3進行擴展，走ch。選擇路徑長最小0-1-5的結點5作為擴展結點。當前最短路徑為4.同時剪掉0-2-5路徑中以5為根的子樹。shfgdeucba25461259301235465626.2 單源最短路徑問題當前最短路徑為4。以5作為擴展結點，走0-1-5-6和0-1-5-8，但是路徑

13、0-1-5-6的長度不小于已存的最短路0-2-6，不在擴展。同時，剪掉0-3-6路徑中以6為根結點為子樹。下一個活結點6成為擴展結點，走0-2-6-9和0-2-6-8，選擇9結點作為擴展結點。64sqhfgdeucbalmk2541259310675012354668985626.2 單源最短路徑問題當前最短路徑長為6，選擇9結點作為擴展結點。走0-2-6-9-8，0-2-6-9-10路徑。此時0-2-6-9-8中路徑長度大于0-1-5-8，所以選擇0-1-5-8中結點8作為擴展結點。 將結點8作為擴展結點0-1-5-8-12-10路徑長度小于0-2-6-9-10，選擇路徑0-2-6-9-10

14、作為最短路徑。 從s到T的最短路為0-2-6-9-10，長度為8。64sqhfgdeucbalmk25412593106750123546689856r8810p812 10o2第6章 分支限界法6.1分支限界法的基本思想6.2單源最短路徑問題6.3 0-1背包問題本章主要知識點：6.2 單源最短路徑問題1. 問題描述 給定帶權有向圖G =(V,E)，其中每條邊的權是非負實數(shù)。另外，還給定V中的一個頂點，稱為源源?，F(xiàn)在要計算從源到所有其它各頂點的最短路長度最短路長度。這里路的長度是指路上各邊權之和。這個問題通常稱為單源最短路徑單源最短路徑問題問題。6.2 單源最短路徑問題 2. 算法思想 解單

15、源最短路徑問題的優(yōu)先隊列式分支限界法用一極小堆來存儲活結點表。其優(yōu)先級是結點所對應的當前路長。 算法從圖G的源頂點s和空優(yōu)先隊列開始。結點s被擴展后，它的兒子結點被依次插入堆中。此后，算法從堆中取出具有最小當前路長的結點作為當前擴展結點，并依次檢查與當前擴展結點相鄰的所有頂點。如果從當前擴如果從當前擴展結點展結點i i到頂點到頂點j j有邊可達，且從源出發(fā)，途經(jīng)頂點有邊可達，且從源出發(fā)，途經(jīng)頂點i i再到再到頂點頂點j j的所相應的路徑的長度小于當前最優(yōu)路徑長度，則的所相應的路徑的長度小于當前最優(yōu)路徑長度，則將該頂點作為活結點插入到活結點優(yōu)先隊列中。將該頂點作為活結點插入到活結點優(yōu)先隊列中。這

16、個結點的擴展過程一直繼續(xù)到活結點優(yōu)先隊列為空時為止。6.3 0-1背包問題 算法的思想 首先，要對輸入數(shù)據(jù)進行預處理，將各物品依其單位重量價值從大到小進行排列。(1). (1). 數(shù)據(jù)預處理數(shù)據(jù)預處理 Element q=new Element n double ws=0;/裝包物品重量 double ps=0;/裝包物品重量 for(int i=1;i=n;i+) qi-1=new Element(I,ppi/wwi); ps=ps+ppi; ws=ws+wwi; if(ws=c)/所有物品裝包 for(int i=1;i=n;i+) xxi=1; return ps; /依單位重量價值排序

17、 MergeSort.mergeSort(q);ElementElement類參見課本類參見課本217217頁；頁；pppp存物品的價值；存物品的價值；wwww存物品的重量；存物品的重量；c c是背包的容量；是背包的容量；xxxx背包問題的解。背包問題的解。6.3 0-1背包問題6.3 0-1背包問題(2). (2). 優(yōu)先隊列式分支限界搜索優(yōu)先隊列式分支限界搜索i). 結點的優(yōu)先級由已裝包的物品價值加上剩下的最大單位重量價值的物品裝滿剩余容量的價值和。由該結點的上界函數(shù)bound給出。private static double bound(int i) /計算結點所相應的價值上界 doubl

18、e cleft=c-cw; /剩余容量 double b=cp; /價值上界/以物品單位重量價值遞減順序裝載剩余容量while (i = n & wi = cleft) / n表示物品總數(shù)，cleft為剩余空間 cleft -= wi; /wi表示i所占空間 b += pi; /pi表示i的價值 i+; /裝填剩余容量裝滿背包if (i = n) b += pi / wi * cleft; / 裝填剩余容量裝滿背包return b; /b為上界函數(shù)6.3 0-1背包問題算法首先檢查當前擴展結點的左兒子結點的可行性。如果該左兒子結點是可行結點，則將它加入到子集樹和活結點優(yōu)先隊列中。當前擴

19、展結點的右兒子結點一定是可行結點，僅當右兒子結點滿足上界約束時才將它加入子集樹和活結點優(yōu)先隊列。當擴展到葉節(jié)點時為問題的最優(yōu)值。6.3 0-1背包問題ii）. 搜索過程6.3 0-1背包問題 while (i != n + 1) / 非葉結點 double wt = cw + wi; if (wt bestp) bestp = cp + pi; addLiveNode(up,cp + pi,cw + wi,i + 1, enode, true); up = bound(i + 1); if (up = bestp) /檢查右兒子節(jié)點 addLiveNode(up,cp,cw,i + 1, enode, false); / 取下一個擴展節(jié)點 HeapNode node=(HeapNode) heap.remo