算法分析與設計(第2版)分支限界法

1、第6章 分支限界法本章主要知識點本章主要知識點 6.1 分支限界法的基本思想 6.2 單源最短路徑問題 6.3 裝載問題 6.4 布線問題 6.5 01背包問題 6.6 最大團問題 6.7 旅行售貨員問題 6.8 電路板排列問題 6.9 批處理作業(yè)調(diào)度6.1 分支限界法的基本思想1. 分支限界法與回溯法的不同分支限界法與回溯法的不同（1）求解目標：回溯法的求解目標是找出解空間樹中滿）求解目標：回溯法的求解目標是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標則是找出足約束條件的所有解，而分支限界法的求解目標則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出滿足約束條件的一個解

2、，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解。在某種意義下的最優(yōu)解。 （2）搜索方式的不同：回溯法以深度優(yōu)先的方式搜索解）搜索方式的不同：回溯法以深度優(yōu)先的方式搜索解空間樹，而分支限界法則以廣度優(yōu)先或以最小耗費優(yōu)先的空間樹，而分支限界法則以廣度優(yōu)先或以最小耗費優(yōu)先的方式搜索解空間樹。方式搜索解空間樹。 2. 分支限界法基本思想分支限界法基本思想 分支限界法常以廣度優(yōu)先或以最小耗費（最大效益）分支限界法常以廣度優(yōu)先或以最小耗費（最大效益）優(yōu)先的方式搜索問題的解空間樹。在分支限界法中，每一優(yōu)先的方式搜索問題的解空間樹。在分支限界法中，每一個活結點只有一次機會成為擴展結點?；罱Y點一旦成為擴個活

3、結點只有一次機會成為擴展結點。活結點一旦成為擴展結點，就一次性產(chǎn)生其所有兒子結點。在這些兒子結點展結點，就一次性產(chǎn)生其所有兒子結點。在這些兒子結點中，導致不可行解或導致非最優(yōu)解的兒子結點被舍棄，其中，導致不可行解或導致非最優(yōu)解的兒子結點被舍棄，其余兒子結點被加入活結點表中。此后，從活結點表中取下余兒子結點被加入活結點表中。此后，從活結點表中取下一結點成為當前擴展結點，并重復上述結點擴展過程。這一結點成為當前擴展結點，并重復上述結點擴展過程。這個過程一直持續(xù)到找到所需的解或活結點表為空時為止。個過程一直持續(xù)到找到所需的解或活結點表為空時為止。 寬度優(yōu)先的問題狀態(tài)生成法寬度優(yōu)先的問題狀態(tài)生成法：在

4、一個擴展結點變成死結點：在一個擴展結點變成死結點之前，它一直是擴展結點。之前，它一直是擴展結點。3. 常見的兩種分支限界法常見的兩種分支限界法（1）隊列式）隊列式(FIFO)分支限界法分支限界法 按照隊列先進先出（按照隊列先進先出（FIFO）原則選取下一個節(jié)點為）原則選取下一個節(jié)點為擴展節(jié)點，即活結點隊列的組織是按照先來后到的原則進擴展節(jié)點，即活結點隊列的組織是按照先來后到的原則進行排隊的。行排隊的。 （2）優(yōu)先隊列式分支限界法）優(yōu)先隊列式分支限界法 按照優(yōu)先隊列中規(guī)定的優(yōu)先級選取優(yōu)先級最高的節(jié)點按照優(yōu)先隊列中規(guī)定的優(yōu)先級選取優(yōu)先級最高的節(jié)點成為當前擴展節(jié)點，即活結點隊列的組織是按照活結點的成

5、為當前擴展節(jié)點，即活結點隊列的組織是按照活結點的優(yōu)先級的大小進行排隊的。優(yōu)先級的大小進行排隊的。 堆是實現(xiàn)優(yōu)先隊列的一種很好方法，用小頂堆可以實堆是實現(xiàn)優(yōu)先隊列的一種很好方法，用小頂堆可以實現(xiàn)最小優(yōu)先隊列；用大頂堆可以實現(xiàn)最大優(yōu)先隊列?，F(xiàn)最小優(yōu)先隊列；用大頂堆可以實現(xiàn)最大優(yōu)先隊列。例如例如: 對于對于n=3的的0-1背包問題，背包問題，當當w=16，15，15，p=45，25，25，c=30時，該時，該0-1背包問題的最優(yōu)解向量是背包問題的最優(yōu)解向量是x=（0，1，1）。）。其解空間是一個深度為其解空間是一個深度為4的滿二叉數(shù)。的滿二叉數(shù)。用隊列式分支限界法解這個用隊列式分支限界法解這個0-1

6、背包問題，它的活結點隊列是：背包問題，它的活結點隊列是：ABCDEFGHIJKLMNO剪枝剪枝6.2 單源最短路徑問題單源最短路徑問題1. 問題描述問題描述 下面以一個例子來說明單源最短路徑問題：在下圖所給的有向下面以一個例子來說明單源最短路徑問題：在下圖所給的有向圖圖G中，每一邊都有一個非負邊權。要求圖中，每一邊都有一個非負邊權。要求圖G的從源頂點的從源頂點s到目標頂?shù)侥繕隧旤c點t之間的最短路徑。之間的最短路徑。 下圖是用優(yōu)先隊列式分支限界法解有向圖下圖是用優(yōu)先隊列式分支限界法解有向圖G的單源最短路徑的單源最短路徑問題產(chǎn)生的解空間樹。其中，每一個結點旁邊的數(shù)字表示該結點問題產(chǎn)生的解空間樹。其

7、中，每一個結點旁邊的數(shù)字表示該結點所對應的當前路長。所對應的當前路長。2. 算法思想算法思想 解單源最短路徑問題的優(yōu)先隊列式分支限界法用一解單源最短路徑問題的優(yōu)先隊列式分支限界法用一極小堆來存儲活結點表。其優(yōu)先級是結點所對應的當前極小堆來存儲活結點表。其優(yōu)先級是結點所對應的當前路長。路長。 算法從圖算法從圖G的源頂點的源頂點s和空優(yōu)先隊列開始。結點和空優(yōu)先隊列開始。結點s被擴被擴展后，它的兒子結點被依次插入堆中。此后，算法從堆展后，它的兒子結點被依次插入堆中。此后，算法從堆中取出具有最小當前路長的結點作為當前擴展結點，并中取出具有最小當前路長的結點作為當前擴展結點，并依次檢查與當前擴展結點相鄰

8、的所有頂點。如果從當前依次檢查與當前擴展結點相鄰的所有頂點。如果從當前擴展結點擴展結點i到頂點到頂點j有邊可達，且從源出發(fā)，途經(jīng)頂點有邊可達，且從源出發(fā)，途經(jīng)頂點i再再到頂點到頂點j的所相應的路徑的長度小于當前最優(yōu)路徑長度，的所相應的路徑的長度小于當前最優(yōu)路徑長度，則將該頂點作為活結點插入到活結點優(yōu)先隊列中。這個則將該頂點作為活結點插入到活結點優(yōu)先隊列中。這個結點的擴展過程一直繼續(xù)到活結點優(yōu)先隊列為空時為止。結點的擴展過程一直繼續(xù)到活結點優(yōu)先隊列為空時為止。3. 剪枝策略剪枝策略 在算法的擴展結點生成其孩子結點的過程中，一旦發(fā)在算法的擴展結點生成其孩子結點的過程中，一旦發(fā)現(xiàn)一個結點的下界不小于

9、當前找到的最短路長，則算法剪現(xiàn)一個結點的下界不小于當前找到的最短路長，則算法剪去以該結點為根的子樹。去以該結點為根的子樹。 在算法中，利用結點間的控制關系進行剪枝。從源頂在算法中，利用結點間的控制關系進行剪枝。從源頂點點s出發(fā)，出發(fā)，2條不同路徑到達圖條不同路徑到達圖G的同一頂點。由于兩條路的同一頂點。由于兩條路徑的路長不同，因此可以將路長長的路徑所對應的樹中的徑的路長不同，因此可以將路長長的路徑所對應的樹中的結點為根的子樹剪去。結點為根的子樹剪去。 在解空間樹中，如果以結點在解空間樹中，如果以結點y為根的子樹中所含的解為根的子樹中所含的解優(yōu)于以結點優(yōu)于以結點x為根的子樹中所含的解，則稱結點為

10、根的子樹中所含的解，則稱結點y控制了結控制了結點點x，以被控制的結點，以被控制的結點x為根的子樹可以剪去。為根的子樹可以剪去。 public class BBShortest static class HeapNode implements Comparable int i； float length； HeapNode(int ii, float ll) i=ii; l=ll; public int compareto(Object x) float xl=(HeapNode)x).length; if(lengthxl) return -1; if(length=xl) return 0;

11、 return 1; static float a; public static void shortest(int v, float dist, int p) int n=p.length-1; MinHeap heap=new MinHeap(); HeapNode enode=new HeapNode(v,0);/定義源為初始擴展結點定義源為初始擴展結點 for(int j=1; j=n; j+) distj=Float.MAX-VALUE;/從源到各頂點的初始距離是無窮從源到各頂點的初始距離是無窮 distv=0; while (true) / 搜索問題的解空間搜索問題的解空間 for

12、(int j=1;j=n;j+)/對于當前擴展結點對于當前擴展結點enode if(aenode.ij Float.MAX_VALUE & enode.length+aenode.ij distj ) / 頂點頂點i到頂點到頂點j可達，且滿足控制約束可達，且滿足控制約束 distj=enode.length+aenode.ij; pj=enode.i;/從源到頂點從源到頂點j的路徑中的路徑中j的前驅結點是的前驅結點是i HeapNode node = new HeapNode(j,distj); heap.put(node); / 加入活結點優(yōu)先隊列加入活結點優(yōu)先隊列 if (heap

13、.isEmpty() break; else enode = (HeapNode) heap.removeMin(); 頂點頂點i i和和j j間有邊，且間有邊，且此路徑長小于原先從此路徑長小于原先從原點到原點到j j的路徑長的路徑長 6.3 裝載問題裝載問題 有一批共有一批共n個集裝箱要裝上個集裝箱要裝上2艘載艘載重量分別為重量分別為c1和和c2的輪船，其中集裝的輪船，其中集裝箱箱i的重量為的重量為wi，且，且211ccwnii 裝載問題要求確定是否有一個合理的裝載方案裝載問題要求確定是否有一個合理的裝載方案可將這個集裝箱裝上這可將這個集裝箱裝上這2艘輪船。如果有，找出一艘輪船。如果有，找出

14、一種裝載方案。種裝載方案。 容易證明，如果一個給定裝載問題有解，則采容易證明，如果一個給定裝載問題有解，則采用下面的策略可得到最優(yōu)裝載方案。用下面的策略可得到最優(yōu)裝載方案。 (1) 首先將第一艘輪船盡可能裝滿；首先將第一艘輪船盡可能裝滿； (2) 將剩余的集裝箱裝上第二艘輪船。將剩余的集裝箱裝上第二艘輪船。 將第一艘輪船盡可能裝滿等價于選取全體集裝將第一艘輪船盡可能裝滿等價于選取全體集裝箱的一個子集，使該子集中集裝箱重量和最接近。箱的一個子集，使該子集中集裝箱重量和最接近。于是，裝載問題等價于以下特殊的于是，裝載問題等價于以下特殊的0-1背包問題。背包問題。nixcxwxwiniiiniii1

15、,1 , 0s.t.max111 實質是第實質是第1艘船的最優(yōu)裝載艘船的最優(yōu)裝載 在算法的在算法的while循環(huán)中，首先檢測當前擴展結點的左兒子結點是循環(huán)中，首先檢測當前擴展結點的左兒子結點是否為可行結點，可行的條件是擴展結點所表示的已經(jīng)上第否為可行結點，可行的條件是擴展結點所表示的已經(jīng)上第1艘船的集艘船的集裝箱載重量和裝箱載重量和ew加上第加上第i個集裝箱的重量小于第個集裝箱的重量小于第1艘船的載重量艘船的載重量c，表，表明第明第i個集裝箱可以上船。如果是則將其加入到活結點隊列中。然后個集裝箱可以上船。如果是則將其加入到活結點隊列中。然后將其右兒子結點加入到活結點隊列中將其右兒子結點加入到活

16、結點隊列中(右兒子結點一定是可行結點右兒子結點一定是可行結點)。2個兒子結點都產(chǎn)生后，當前擴展結點被舍棄。個兒子結點都產(chǎn)生后，當前擴展結點被舍棄。 活結點隊列中的隊首元素被取出作為當前擴展結點，由于隊列活結點隊列中的隊首元素被取出作為當前擴展結點，由于隊列中每一層結點之后都有一個尾部標記中每一層結點之后都有一個尾部標記-1，故在取隊首元素時，活結，故在取隊首元素時，活結點隊列一定不空。當取出的元素是點隊列一定不空。當取出的元素是-1時，再判斷當前隊列是否為空。時，再判斷當前隊列是否為空。如果隊列非空，則將尾部標記如果隊列非空，則將尾部標記-1加入活結點隊列，算法開始處理下加入活結點隊列，算法開

17、始處理下一層的活結點。一層的活結點。 1. 隊列式分支限界法隊列式分支限界法public class FIFOBBLoading static int n; /集裝箱個數(shù)集裝箱個數(shù) static int bestw; /當前所求到的所有解中的最優(yōu)載重量當前所求到的所有解中的最優(yōu)載重量 static ArrayQueue queue; /活結點隊列活結點隊列 public static int maxloading(int w, int c) /隊列式分支限界法，返回最優(yōu)載重量隊列式分支限界法，返回最優(yōu)載重量 n=w.length-1; / 初始化初始化 bestw=0; queue=new A

18、rrayQueue(); queue.put(new Integer(-1); /同層結點尾部標志同層結點尾部標志 int i=1; /當前擴展結點所在的層次當前擴展結點所在的層次 int ew=0; /擴展結點所表示的已經(jīng)上第擴展結點所表示的已經(jīng)上第1艘船的集裝箱載重量和艘船的集裝箱載重量和 while(true) / 檢查左兒子結點檢查左兒子結點 if(ew+wibestw) /如果該葉子代表的解優(yōu)于當前最優(yōu)解如果該葉子代表的解優(yōu)于當前最優(yōu)解 bestw=wt; else queue.put(new Integer(wt); 結點的左孩子表示將當前集裝箱裝上船，右孩子表示不將當前結點的左孩

19、子表示將當前集裝箱裝上船，右孩子表示不將當前集裝箱裝上船。設集裝箱裝上船。設bestw是當前所求到的所有可行解中裝上船的集裝是當前所求到的所有可行解中裝上船的集裝箱重量和的最優(yōu)解；箱重量和的最優(yōu)解；ew是當前擴展結點所表示的已經(jīng)裝上船的集裝是當前擴展結點所表示的已經(jīng)裝上船的集裝箱重量和；箱重量和；r是目前尚未考慮的剩余集裝箱的重量和。則當是目前尚未考慮的剩余集裝箱的重量和。則當ew+r bestw時，可將其右子樹剪去，因為，此時即使把剩余的集裝時，可將其右子樹剪去，因為，此時即使把剩余的集裝箱全部裝上船，也不會的到比箱全部裝上船，也不會的到比bestw更優(yōu)的解。更優(yōu)的解。 另外，為了確保右子樹

20、成功剪枝，應該在算法每一次進入左子另外，為了確保右子樹成功剪枝，應該在算法每一次進入左子樹的時候更新樹的時候更新bestw的值。的值。 2. 算法的改進算法的改進public class FIFOBBLoading static int n; /集裝箱個數(shù)集裝箱個數(shù) static int bestw; /當前所求到的所有解中的最優(yōu)載重量當前所求到的所有解中的最優(yōu)載重量 static ArrayQueue queue; /活結點隊列活結點隊列 public static int maxloading(int w, int c) /隊列式分支限界法，返回最優(yōu)載重量隊列式分支限界法，返回最優(yōu)載重量

21、n=w.length-1; / 初始化初始化 bestw=0; queue=new ArrayQueue(); queue.put(new Integer(-1); /同層結點尾部標志同層結點尾部標志 int i=1; /當前擴展結點所在的層次當前擴展結點所在的層次 int ew=0; /擴展結點所表示的已經(jīng)上第擴展結點所表示的已經(jīng)上第1艘船的集裝箱載重量和艘船的集裝箱載重量和 int r=0; /目前尚未考慮的剩余集裝箱的重量和目前尚未考慮的剩余集裝箱的重量和 for(int j=2; j=n; j+) /j為什么從為什么從2開始開始 r+=wj; while(true) int wt=ew

22、+wi; / 檢查左兒子結點檢查左兒子結點 if(wtbestw) bestw=wt; if(ibestw&i 0; j-) bestxj = (e.leftchild) ? 1 : 0; e = e.parent; private static class qnode /數(shù)的雙親表示法，解空間樹是存在的數(shù)的雙親表示法，解空間樹是存在的 qnode parent; /表示該結點的雙親結點表示該結點的雙親結點 boolean leftchild; /該結點是其雙親的左孩子標志，該結點是其雙親的左孩子標志，1左左0右右 int weigth; /該結點所表示的已經(jīng)上船的集裝箱重量和該結點所

23、表示的已經(jīng)上船的集裝箱重量和 private qnode(qnode theparent, boolean theleftchild, int theweigth) parent=theparent; leftchild=theleftchild; weight=theweight; private static void enqueue(int wt, int i, qnode parent, boolean leftch) if(i=n) if(wt=bestw) beste=parent; bestxn=(leftch) ? 1: 0; return qnode b=new qnode(

24、parent,leftch,wt); queue.put(b); static int n; static int bestw; static ArrayQueue queue; static int bestx; public static int maxloading(int w, int c, int xx) n=w.length-1; bestw=0; queue=new ArrayQueue(); queue.put(null); beste=null; bestx=xx; int i=1; int ew=0; int r=0; for(int j=2;j=n; j+) r+=wj;

25、 while(true) int wt=ew+wi; / 檢查左兒子結點檢查左兒子結點 if(wtbestw) bestw=wt; enQueue(wt, i, e, true); if(ew+rbestw&i0; j-) bestxj=(beste.leftchild)? 1: 0; beste=beste.parent; 解裝載問題的優(yōu)先隊列式分支限界法用最大優(yōu)先隊列存儲活結解裝載問題的優(yōu)先隊列式分支限界法用最大優(yōu)先隊列存儲活結點表?；罱Y點點表?；罱Y點x在優(yōu)先隊列中的優(yōu)先級定義為從根結點到結點在優(yōu)先隊列中的優(yōu)先級定義為從根結點到結點x的路的路徑所相應的載重量再加上剩余集裝箱的重量之

26、和。徑所相應的載重量再加上剩余集裝箱的重量之和。 優(yōu)先隊列中優(yōu)先級最大的活結點成為下一個擴展結點。以結點優(yōu)先隊列中優(yōu)先級最大的活結點成為下一個擴展結點。以結點x為根的子樹中所有結點相應的路徑的載重量不超過它的優(yōu)先級。為根的子樹中所有結點相應的路徑的載重量不超過它的優(yōu)先級。子集樹中葉結點所相應的載重量與其優(yōu)先級相同。子集樹中葉結點所相應的載重量與其優(yōu)先級相同。 在優(yōu)先隊列式分支限界法中，一旦有一個葉結點成為當前擴展在優(yōu)先隊列式分支限界法中，一旦有一個葉結點成為當前擴展結點，則可以斷言該葉結點所相應的解即為最優(yōu)解。此時可終止算結點，則可以斷言該葉結點所相應的解即為最優(yōu)解。此時可終止算法。法。 4.

27、 優(yōu)先隊列式分支限界法優(yōu)先隊列式分支限界法static class bbnode bbnode parent; boolean leftchild; bbnode(bbnode par, boolean ch) parent=par; leftchild=ch; static class heapnode implements comparable bbnode livenode; int uweight; int level; heapnode(bbnode node, int up, int lev) livenode=node; uweight=up; level=lev; public

28、 int compareto(Object x) int xuw=(heapnode) x).uweight; if(uweight0; j-) rj=rj+1+wj+1; while(i!=n+1) if(ew+wi0; j-) bestxj=(e.leftchild)? 1: 0; e=e.parent; return ew;1. 問題描述問題描述6.4 布線問題布線問題 在劃分成在劃分成n n個方格陣列的印刷電路板上，給定方格個方格陣列的印刷電路板上，給定方格a和方格和方格b，要求確定要求確定a到到b的中點的最短布線方案。電路板只能沿水平和垂直方的中點的最短布線方案。電路板只能沿水平和垂

29、直方向以直角方式進行布線。布線過程中不能穿越作了封鎖標志的方格。向以直角方式進行布線。布線過程中不能穿越作了封鎖標志的方格。ab2. 算法設計算法設計 解此問題的隊列式分支限界法從起解此問題的隊列式分支限界法從起始位置始位置a開始將它作為第一個擴展結點。開始將它作為第一個擴展結點。與該擴展結點相鄰并且可達的方格成為與該擴展結點相鄰并且可達的方格成為可行結點被加入到活結點隊列，并將這可行結點被加入到活結點隊列，并將這些方格標記為些方格標記為1，即從起始方格，即從起始方格a到這些到這些方格的距離為方格的距離為1。 當活結點隊列不空時，從中取出隊當活結點隊列不空時，從中取出隊首結點作為新擴展結點，將

30、與當前擴展首結點作為新擴展結點，將與當前擴展結點相鄰且未標記過的方格標記為結點相鄰且未標記過的方格標記為2，并存入活結點隊列。此過程繼續(xù)直到搜并存入活結點隊列。此過程繼續(xù)直到搜索到目標方格索到目標方格b或活結點隊列為空時為或活結點隊列為空時為止。止。public class wirerouter private static class position private int row; private int col; position(int rr, int cc) row=rr; col=cc; private static int grid; private static int si

31、ze; private static ArrayQueue q; private static int pathlen; private static position start, finsh; private static position path; private static void inputdata() MyinputStream keyboard=MyinputStream(); System.out.println(“Enter grid size”); size=keyboard.readInteger(); System.out.println(“Enter the s

32、tart position”); start=new position(keyboard.readInteger(), keyboard.readInteger() ); System.out.println(“Enter the finish position”); finish=new position(keyboard.readInteger(), keyboard.readInteger() ); grid=new int size+2size+2; System.out.println(“Enter the wiring grid in row-major order”); for(

33、int i=1; i=size; i+) for(int j=1; j=size; j+) gridij=keyboard.readInteger(); private static boolean findpath() if(start.row=finish.row)&(start.col=finish.col); pathlen=0; return true; position offset=new position4; offset0=new position(0, 1); offset1=new position(1, 0); offset2=new position(0, -

34、1); offset3=new position(-1, 0); for(int i=0; i=size+1; i+); grid0i=gridsize+1i=1; gridi0=gridisize+1=1; position here=new position(start.row, start.col); gridstart.rowstart.col=2; int numofnbrs=4; arrayqueue q=new arrayqueue(); position nbr=new position(0,0);定義移動方向的相對位移定義移動方向的相對位移設置邊界的圍墻設置邊界的圍墻 do

35、for(int i=0; i=0; j-) pathj=here; for(int i=0; inumofnbrs; i+) nbr.row=here.row+offseti.row; nbr.col=here.col+offseti.col; if(gridnbr.rownbr.col=j+2) break; here=new position(nbr.row, nbr.col); return true; 6.5 0-1背包問題背包問題 首先，要對輸入數(shù)據(jù)進行預處理，將各物品依其單位首先，要對輸入數(shù)據(jù)進行預處理，將各物品依其單位重量價值從大到小進行排列。重量價值從大到小進行排列。 在下面描

36、述的優(yōu)先隊列分支限界法中，結點的優(yōu)先級在下面描述的優(yōu)先隊列分支限界法中，結點的優(yōu)先級由已裝袋的物品價值加上剩下的最大單位重量價值的物品由已裝袋的物品價值加上剩下的最大單位重量價值的物品裝滿剩余容量的價值和。裝滿剩余容量的價值和。 算法首先檢查當前擴展結點的左兒子結點的可行性。算法首先檢查當前擴展結點的左兒子結點的可行性。如果該左兒子結點是可行結點，則將它加入到子集樹和活如果該左兒子結點是可行結點，則將它加入到子集樹和活結點優(yōu)先隊列中。當前擴展結點的右兒子結點一定是可行結點優(yōu)先隊列中。當前擴展結點的右兒子結點一定是可行結點，僅當右兒子結點滿足上界約束時才將它加入子集樹結點，僅當右兒子結點滿足上界

37、約束時才將它加入子集樹和活結點優(yōu)先隊列。當擴展到葉節(jié)點時為問題的最優(yōu)值。和活結點優(yōu)先隊列。當擴展到葉節(jié)點時為問題的最優(yōu)值。static class bbnode bbnode parent; boolean leftchild; bbnode(bbnode par, boolean ch) parent=par; leftchild=ch; static class heapnode implements comparable bbnode livenode; double upperprofit; double profit; double weight; int level; heapno

38、de(bbnode node, double up, double pp, double ww, int lev) livenode=node; upperprofit=up; profit=pp; weight=ww; level=lev; public int compareto(Object x) double xup=(heapnode) x).upperprofit; if(upperprofitxup) return -1; if(upperprofit=xup) return 0; return 1; private class Element implements Compar

39、able int id; double d; private Element (int idd, double dd) id=idd; d=dd; public int compareto(Object x) double xd=(Element) x).d if(dxd) return -1; if(d=xd) return 0; return 1; public boolean equals(Object x) return d=(Element) x).d; public class bbknapsack static double c; static int n; static dou

40、ble w; static double p; static double cw; static double cp; static int bestx; static maxheap heap; private static double bound(int i) double cleft=c-cw; double b=cp; while(i=n&wi=cleft) cleft-=wi; b+=pi; i+; if(i=n) b+=pi/wi*cleft; private static void addlivenode(double up, double pp, double ww,

41、 int lev, bbnode par, boolean ch) bbnode b=new bbnode(par, ch); heapnode node=new heapnode(b, up, pp, ww, lev); heap.put(node); private static double bbknapsack() bbnode enode=null; int i=1; double bestp=0.0; double up=bound(1); while(i!=n+1) double wt=cw+wi; if(wtbest) bestp=cp+pi; addlivenode(up,

42、cp+pi, cw+wi, i+1, enode, true); up=bound(i+1); if(upbestp) addlivenode(up, cp, i+1, enode, false); heapnode node=(heapnode) heap.removemax(); enode=node.livenode; cw=node.weight; cp=fit; upnode.upperprofit; i=node.level; for(int j=n; j0; j-) bestxj=(enode.leftchild) ? 1: 0; enode=enode.pare

43、nt; return cp; public static double knapsack(double pp, double ww, double cc, int xx) c=cc; n=pp.lenght-1; element q=new elementn; double ws=0.0; double ps=0.0; for(int i=1; i=n; i+) qi-1=new element(i, ppi/wwi); ps+=ppi; ws+=wwi; if(ws=c) for(int i=1; i=n; i+) xxi=1; return ps; MergeSort.mergesort(

44、q); p=new doublen+1; w=new doublen+1; for(int i=1; i=n; i+) pi=ppqn-i.id; wi=wwqn-i.id; cw=0.0; cp=0.0; bestx=new intn+1; heap=new maxheap(); double maxp=bbknapsack(); for(int i=1; ibestn時，右子樹中可能含有最優(yōu)解，此時，右子樹中可能含有最優(yōu)解，此時將右兒子結點加入到子集樹中并插入到活結點優(yōu)先隊列中。時將右兒子結點加入到子集樹中并插入到活結點優(yōu)先隊列中。 算法的算法的while循環(huán)的終止條件是遇到子集樹中的一個

45、葉結點循環(huán)的終止條件是遇到子集樹中的一個葉結點(即即n+1層結點層結點)成為當前擴展結點。成為當前擴展結點。 對于子集樹中的葉結點，有對于子集樹中的葉結點，有upperSizecliqueSize。此時活結。此時活結點優(yōu)先隊列中剩余結點的點優(yōu)先隊列中剩余結點的upperSize值均不超過當前擴展結點的值均不超過當前擴展結點的upperSize值，從而進一步搜索不可能得到更大的團，此時算法已找值，從而進一步搜索不可能得到更大的團，此時算法已找到一個最優(yōu)解。到一個最優(yōu)解。 static class bbnode bbnode parent; boolean leftchild; bbnode(bb

46、node par, boolean ch) parent=par; leftchild=ch; static class heapnode implements comparable bbnode livenode; int uppersize; int cliquesize; int level; heapnode(bbnode node, int up, int size, int lev) livenode=node; uppersize=up; cliquesize=size; level=lev; public int compareto(Object x) double xup=(

47、heapnode) x).uppersize; if(uppersize0; bnode=bnode.parent, j-) if(bnode.leftchild&!aij) ok=false; break; if(ok) if(cn+1bestn) bestn=cn+1; addlivenode(cn+n-i+1, cn+1, i+1, enode, true); if(cn+n-i=bestn) addlivenode(cn+n-i, cn, i+1, enode, false); enode=node.livenode; cn=node.cliquesize; i=node.le

48、vel; for(int j=n; j0; j-) bestxj=(enode.leftchild) ? 1: 0; enode=enode.parent; return bestn; 1. 問題描述問題描述6.7 旅行售貨員問題旅行售貨員問題 某售貨員要到若干城市去推銷商品，已知各城市之間某售貨員要到若干城市去推銷商品，已知各城市之間的路程。他要選定一條從駐地出發(fā)，經(jīng)過每個城市一次，的路程。他要選定一條從駐地出發(fā)，經(jīng)過每個城市一次，最后回到駐地的路線，使總的路程最后回到駐地的路線，使總的路程(或總旅費或總旅費)最小。最小。 路線是一個帶權圖。圖中各邊的費用（權）為正數(shù)。路線是一個帶權圖。圖中

49、各邊的費用（權）為正數(shù)。圖的一條周游路線是包括圖的一條周游路線是包括V中的每個頂點在內(nèi)的一條回路。中的每個頂點在內(nèi)的一條回路。周游路線的費用是這條路線上所有邊的費用之和。周游路線的費用是這條路線上所有邊的費用之和。 旅行售貨員問題的解空間可以組織成一棵樹，從樹的旅行售貨員問題的解空間可以組織成一棵樹，從樹的根結點到任一葉結點的路徑定義了圖的一條周游路線。旅根結點到任一葉結點的路徑定義了圖的一條周游路線。旅行售貨員問題要在圖行售貨員問題要在圖G中找出費用最小的周游路線。中找出費用最小的周游路線。 2. 算法設計算法設計 算法開始時創(chuàng)建一個最小堆，用于表示活結點優(yōu)先隊算法開始時創(chuàng)建一個最小堆，用于表示活結點優(yōu)先隊列。堆中每個結點的子樹費用的下界列。堆中每個結點的子樹費用的下界l