算法分析與設(shè)計第6章

1、1 2主要內(nèi)容n6.1 分支限界法的基本思想分支限界法的基本思想n6.2 單源最短路徑問題單源最短路徑問題n6.3 裝載問題裝載問題n6.4 0-1背包問題背包問題36.1 分支限界法的基本思想分支限界法的基本思想nBreadth-first search n分支限界法與回溯法分支限界法與回溯法（1）求解目標(biāo)求解目標(biāo)：回溯法的求解目標(biāo)是找出解空間：回溯法的求解目標(biāo)是找出解空間樹中滿足約束條件的樹中滿足約束條件的所有解所有解，而分支限界法的求，而分支限界法的求解目標(biāo)則是找出滿足約束條件的解目標(biāo)則是找出滿足約束條件的一個解一個解，或是在，或是在滿足約束條件的解中找出在某種意義下的滿足約束條件的解中

2、找出在某種意義下的最優(yōu)解最優(yōu)解。 （2）搜索方式的不同搜索方式的不同：回溯法以：回溯法以深度優(yōu)先的方式深度優(yōu)先的方式搜索解空間樹，而分支限界法則以搜索解空間樹，而分支限界法則以廣度優(yōu)先或以廣度優(yōu)先或以最小耗費優(yōu)先的方式最小耗費優(yōu)先的方式搜索解空間樹。搜索解空間樹。 6.1分支限界法的基本思想分支限界法的基本思想4分支限界法的搜索策略分支限界法的搜索策略在擴(kuò)展結(jié)點處，先生成其所有的兒子結(jié)點（分支），在擴(kuò)展結(jié)點處，先生成其所有的兒子結(jié)點（分支），然后再從當(dāng)前的活結(jié)點表中選擇下一個擴(kuò)展結(jié)點。然后再從當(dāng)前的活結(jié)點表中選擇下一個擴(kuò)展結(jié)點。為了有效的選擇下一擴(kuò)展結(jié)點，以加速搜索的進(jìn)程，為了有效的選擇下一擴(kuò)

3、展結(jié)點，以加速搜索的進(jìn)程，在每一活結(jié)點處，計算一個函數(shù)值，并根據(jù)這些已在每一活結(jié)點處，計算一個函數(shù)值，并根據(jù)這些已計算出的函數(shù)值，從當(dāng)前活結(jié)點表中選擇一個最有計算出的函數(shù)值，從當(dāng)前活結(jié)點表中選擇一個最有利的結(jié)點作為擴(kuò)展結(jié)點，使搜索朝著解空間樹上有利的結(jié)點作為擴(kuò)展結(jié)點，使搜索朝著解空間樹上有最優(yōu)解的分支推進(jìn)，以便盡快地找出一個最優(yōu)解最優(yōu)解的分支推進(jìn)，以便盡快地找出一個最優(yōu)解 。6.1分支限界法的基本思想分支限界法的基本思想5w = 16,15,15,v = 45, 25, 25, c = 306.1分支限界法的基本思想分支限界法的基本思想6分支限界法的基本思想分支限界法的基本思想 分支限界法常以

4、廣度優(yōu)先或以最小耗費（最大效益）分支限界法常以廣度優(yōu)先或以最小耗費（最大效益）優(yōu)先的方式搜索問題的解空間樹。優(yōu)先的方式搜索問題的解空間樹。此后，從活結(jié)點表中取下一結(jié)點成為當(dāng)前擴(kuò)展結(jié)此后，從活結(jié)點表中取下一結(jié)點成為當(dāng)前擴(kuò)展結(jié)點，并重復(fù)上述結(jié)點擴(kuò)展過程。這個過程一直持點，并重復(fù)上述結(jié)點擴(kuò)展過程。這個過程一直持續(xù)到找到所需的解或續(xù)到找到所需的解或活結(jié)點表為空時為止活結(jié)點表為空時為止。 在分支限界法中，每一個活結(jié)點在分支限界法中，每一個活結(jié)點只有一次機(jī)會只有一次機(jī)會成成為擴(kuò)展結(jié)點?；罱Y(jié)點一旦成為擴(kuò)展結(jié)點，就為擴(kuò)展結(jié)點?；罱Y(jié)點一旦成為擴(kuò)展結(jié)點，就一次一次性產(chǎn)生其所有兒子結(jié)點性產(chǎn)生其所有兒子結(jié)點。在這些兒

5、子結(jié)點中，導(dǎo)。在這些兒子結(jié)點中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點被舍棄，致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點被舍棄，其余兒子結(jié)點被加入活結(jié)點表中。其余兒子結(jié)點被加入活結(jié)點表中。6.1分支限界法的基本思想分支限界法的基本思想7常見的兩種分支限界法常見的兩種分支限界法n隊列式隊列式(FIFO)分支限界法分支限界法 按照隊列先進(jìn)先出（按照隊列先進(jìn)先出（FIFO）原則選取下一）原則選取下一個節(jié)點為擴(kuò)展節(jié)點。個節(jié)點為擴(kuò)展節(jié)點。n優(yōu)先隊列式優(yōu)先隊列式(priority queue)分支限界法分支限界法 按照優(yōu)先隊列中規(guī)定的優(yōu)先級選取優(yōu)先級按照優(yōu)先隊列中規(guī)定的優(yōu)先級選取優(yōu)先級最高的節(jié)點成為當(dāng)前擴(kuò)展節(jié)點。最

6、高的節(jié)點成為當(dāng)前擴(kuò)展節(jié)點。 6.1分支限界法的基本思想分支限界法的基本思想8n例：考慮例：考慮n =3 時時0-1背包問題的一個實例如下：背包問題的一個實例如下：w =16,15,15, p= 45, 25,25,c = 30。其子集樹。其子集樹6.1分支限界法的基本思想分支限界法的基本思想9用用隊列式隊列式分支限界法解此問題分支限界法解此問題n隊列式分支限界法搜索解空間樹的方式與隊列式分支限界法搜索解空間樹的方式與解空間樹的廣度優(yōu)先遍歷算法極為相似，解空間樹的廣度優(yōu)先遍歷算法極為相似，唯一的不同之處是隊列式分支限界法不搜唯一的不同之處是隊列式分支限界法不搜索以不可行結(jié)點為根的子樹。索以不可行

7、結(jié)點為根的子樹。6.1分支限界法的基本思想分支限界法的基本思想10隊列式隊列式0活結(jié)點隊列活結(jié)點隊列B ，C160C，E16F，G1504516G30501525152500E，F(xiàn)，G6.1分支限界法的基本思想分支限界法的基本思想w =16,15,15, p= 45, 25,25,c = 3011用優(yōu)先隊列式分支限界法解此問題用優(yōu)先隊列式分支限界法解此問題n也是從根結(jié)點也是從根結(jié)點A開始搜索解空間樹，用一個開始搜索解空間樹，用一個極大堆來表示活結(jié)點表的優(yōu)先隊列，該優(yōu)先極大堆來表示活結(jié)點表的優(yōu)先隊列，該優(yōu)先隊列的優(yōu)先級定義為活結(jié)點所獲得的價值。隊列的優(yōu)先級定義為活結(jié)點所獲得的價值。初始時堆為空。

8、初始時堆為空。0450452504550252500454545025502502506.1分支限界法的基本思想分支限界法的基本思想w =16,15,15, p= 45, 25,25,c = 3012n優(yōu)先隊列中規(guī)定的結(jié)點優(yōu)先級常用一個優(yōu)先隊列中規(guī)定的結(jié)點優(yōu)先級常用一個與該結(jié)點相關(guān)的數(shù)值與該結(jié)點相關(guān)的數(shù)值p來表示，結(jié)點優(yōu)先來表示，結(jié)點優(yōu)先級的高低與級的高低與p值的大小相關(guān)，最大優(yōu)先隊值的大小相關(guān)，最大優(yōu)先隊列規(guī)定列規(guī)定p值較大的結(jié)點優(yōu)先級較高，用值較大的結(jié)點優(yōu)先級較高，用大大堆堆來實現(xiàn)。來實現(xiàn)。 小優(yōu)先隊列規(guī)定小優(yōu)先隊列規(guī)定p值較小的結(jié)點優(yōu)先級較值較小的結(jié)點優(yōu)先級較高，用高，用小堆小堆來實現(xiàn)。

9、來實現(xiàn)。6.1分支限界法的基本思想分支限界法的基本思想13n當(dāng)尋求問題的一個最優(yōu)解時，可以用剪枝函數(shù)來當(dāng)尋求問題的一個最優(yōu)解時，可以用剪枝函數(shù)來加速搜索，該函數(shù)給出每一個可行結(jié)點相應(yīng)的子加速搜索，該函數(shù)給出每一個可行結(jié)點相應(yīng)的子樹可能獲得的樹可能獲得的最大價值的上界最大價值的上界。如果這個上界不。如果這個上界不會比當(dāng)前最優(yōu)值更大，則說明相應(yīng)的子樹中不含會比當(dāng)前最優(yōu)值更大，則說明相應(yīng)的子樹中不含問題的最優(yōu)解，因而可以剪去，問題的最優(yōu)解，因而可以剪去，n另一方面，我們也可以將上界函數(shù)確定的每個結(jié)另一方面，我們也可以將上界函數(shù)確定的每個結(jié)點的上界值作為優(yōu)先級，以該優(yōu)先級的非增序抽點的上界值作為優(yōu)先級

10、，以該優(yōu)先級的非增序抽取當(dāng)前擴(kuò)展結(jié)點，這種策略有時可以更迅速地找取當(dāng)前擴(kuò)展結(jié)點，這種策略有時可以更迅速地找到最優(yōu)解。到最優(yōu)解。6.1分支限界法的基本思想分支限界法的基本思想141234306102054ABCDEFGHIJKLMNOPQ1234344324422332B C,D,ED,E,F,GE,F,G,H,IF,G,H,I,J,KG,H,I,J,K59H,I,J,K66I,J,K25J,KK隊列6.1分支限界法的基本思想分支限界法的基本思想151234306102054ABCDEFGHIJKLMNOPQ1234344324422332B，0C,30D,6優(yōu)先隊列E,4J,14K,24H,1

11、1I, 26256.1分支限界法的基本思想分支限界法的基本思想166.2 單源最短路徑 算法思想算法思想 解單源最短路徑問題的解單源最短路徑問題的優(yōu)先隊列式分支限界法優(yōu)先隊列式分支限界法用一用一極小堆來存儲活結(jié)點表。其優(yōu)先級是結(jié)點所對應(yīng)的當(dāng)前極小堆來存儲活結(jié)點表。其優(yōu)先級是結(jié)點所對應(yīng)的當(dāng)前路長。路長。 算法從圖算法從圖G G的源頂點的源頂點s s和空優(yōu)先隊列開始。結(jié)點和空優(yōu)先隊列開始。結(jié)點s s被擴(kuò)展被擴(kuò)展后，它的兒子結(jié)點被依次插入堆中。后，它的兒子結(jié)點被依次插入堆中。 此后，算法從堆中取出具有最小當(dāng)前路長的結(jié)點作為當(dāng)此后，算法從堆中取出具有最小當(dāng)前路長的結(jié)點作為當(dāng)前擴(kuò)展結(jié)點，并依次檢查與當(dāng)前

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

13、法擴(kuò)展結(jié)點的過程中，一旦發(fā)現(xiàn)一個結(jié)點的下界不小于當(dāng)前找到的最短路長，則算法剪去以該結(jié)點為不小于當(dāng)前找到的最短路長，則算法剪去以該結(jié)點為根的子樹。根的子樹。在算法中，利用結(jié)點間的控制關(guān)系進(jìn)行剪枝。從源頂在算法中，利用結(jié)點間的控制關(guān)系進(jìn)行剪枝。從源頂點點s s出發(fā)，出發(fā)，2 2條不同路徑到達(dá)圖條不同路徑到達(dá)圖G G的同一頂點。由于兩的同一頂點。由于兩條路徑的路長不同，因此可以將路長長的路徑所對應(yīng)條路徑的路長不同，因此可以將路長長的路徑所對應(yīng)的樹中的結(jié)點為根的子樹剪去。的樹中的結(jié)點為根的子樹剪去。 6.2單源最短路徑單源最短路徑186.2單源最短路徑單源最短路徑19templateclass Gra

14、ph friend void main(void); public: void ShortestPaths( int ); private: int n, *prev; /前驅(qū)頂點數(shù)組前驅(qū)頂點數(shù)組 Type *c, /圖圖G的鄰接矩陣的鄰接矩陣 *dist; /最短距離數(shù)組最短距離數(shù)組;templateclass MinHeapNode friend Graph; public: operator int () const return length; private: int i; /頂點編號頂點編號 Type length; /當(dāng)前路長當(dāng)前路長;6.2單源最短路徑單源最短路徑20templ

15、atevoid Graph: ShortestPaths( int v ) /單源最短路徑問題的優(yōu)先隊列式分支限界法單源最短路徑問題的優(yōu)先隊列式分支限界法 /定義最小堆的容量為定義最小堆的容量為1000 MinHeap MinHeapNode H(1000); /定義源為初始擴(kuò)展結(jié)點定義源為初始擴(kuò)展結(jié)點 MinHeapNode E; E.i = v; E.length = 0; dist v =0; /搜索問題的解空間搜索問題的解空間6.2單源最短路徑單源最短路徑21 while (true) for (int j = 1; j = n; j+) /尋找尋找E的下一個結(jié)點的下一個結(jié)點 if (

16、cE.ijinf)&(E.length+cE.ijdistj) / 頂點頂點i到頂點到頂點j可達(dá)，且滿足控制約束可達(dá)，且滿足控制約束 distj=E.length+cE.ij; prevj=E.i; / 加入活結(jié)點優(yōu)先隊列加入活結(jié)點優(yōu)先隊列 MinHeapNode N; N.i=j; N.length=distj; H.Insert(N); try H.DeleteMin(E); / 取下一擴(kuò)展結(jié)點，距源點最近取下一擴(kuò)展結(jié)點，距源點最近 catch (OutOfBounds) break; / 優(yōu)先隊列空優(yōu)先隊列空 6.2單源最短路徑單源最短路徑22while 循環(huán)體完成對解空間內(nèi)部結(jié)

17、點的擴(kuò)展，對于當(dāng)前節(jié)結(jié)點，算法依次檢查與當(dāng)前擴(kuò)展節(jié)點相鄰的所有頂點。如果從當(dāng)前擴(kuò)展結(jié)點i到頂點j有邊可達(dá)，且從源出發(fā)，途經(jīng)頂點i再到j(luò)的所有相應(yīng)的路徑長度小于當(dāng)前最優(yōu)路徑長度，則將點j插入到活結(jié)點優(yōu)先隊列中。236.2裝載問題裝載問題1. 問題描述問題描述有一批共有一批共n n個集裝箱要裝上個集裝箱要裝上2 2艘載重量分別為艘載重量分別為c1c1和和c2c2的輪的輪船，其中集裝箱船，其中集裝箱i i的重量為的重量為W Wi i，且，且211ccwnii裝載問題要求確定是否有一個合理的裝載方案可將這些裝載問題要求確定是否有一個合理的裝載方案可將這些集裝箱裝上這集裝箱裝上這2 2艘輪船。如果有，找

18、出一種裝載方案。艘輪船。如果有，找出一種裝載方案。 容易證明：容易證明：如果一個給定裝載問題有解，則采用下面的如果一個給定裝載問題有解，則采用下面的策略可得到最優(yōu)裝載方案。策略可得到最優(yōu)裝載方案。 (1)(1)首先將第一艘輪船盡可能裝滿；首先將第一艘輪船盡可能裝滿；(2)(2)將剩余的集裝箱裝上第二艘輪船。將剩余的集裝箱裝上第二艘輪船。 6.3裝載問題裝載問題2401631163116015300151506.3裝載問題裝載問題2511116011601631163116015300151501501601116150活結(jié)點隊列活結(jié)點隊列擴(kuò)展結(jié)點擴(kuò)展結(jié)點2. 隊列式分支限界法隊列式分支限界法6

19、.3裝載問題裝載問題26算法思想算法思想 用一個隊列用一個隊列Q來存放活結(jié)點表，來存放活結(jié)點表，Q中中weight表示每個活結(jié)表示每個活結(jié)點所相應(yīng)的當(dāng)前載重量。當(dāng)點所相應(yīng)的當(dāng)前載重量。當(dāng)weight1時，表示隊列已達(dá)時，表示隊列已達(dá)到解空間樹到解空間樹同一層結(jié)點的尾部同一層結(jié)點的尾部。 算法首先檢測當(dāng)前擴(kuò)展結(jié)點的左兒子結(jié)點是否為可行結(jié)點。算法首先檢測當(dāng)前擴(kuò)展結(jié)點的左兒子結(jié)點是否為可行結(jié)點。如果是則將其加入到活結(jié)點隊列中。然后將其右兒子結(jié)點如果是則將其加入到活結(jié)點隊列中。然后將其右兒子結(jié)點加入到活結(jié)點隊列中加入到活結(jié)點隊列中(右兒子結(jié)點一定是可行結(jié)點右兒子結(jié)點一定是可行結(jié)點)。2個兒個兒子結(jié)點都

20、產(chǎn)生后，當(dāng)前擴(kuò)展結(jié)點被舍棄。子結(jié)點都產(chǎn)生后，當(dāng)前擴(kuò)展結(jié)點被舍棄。 活結(jié)點隊列中的隊首元素被取出作為當(dāng)前擴(kuò)展結(jié)點，由活結(jié)點隊列中的隊首元素被取出作為當(dāng)前擴(kuò)展結(jié)點，由于隊列中每一層結(jié)點之后都有一個尾部標(biāo)記于隊列中每一層結(jié)點之后都有一個尾部標(biāo)記-1，故在取隊首，故在取隊首元素時，活結(jié)點隊列一定不空。當(dāng)取出的元素是元素時，活結(jié)點隊列一定不空。當(dāng)取出的元素是-1時，再判時，再判斷當(dāng)前隊列是否為空。如果隊列非空，則將尾部標(biāo)記斷當(dāng)前隊列是否為空。如果隊列非空，則將尾部標(biāo)記-1加入加入活結(jié)點隊列，算法開始處理下一層的活結(jié)點?；罱Y(jié)點隊列，算法開始處理下一層的活結(jié)點。6.3裝載問題裝載問題27n該算法包含兩個函數(shù)

21、該算法包含兩個函數(shù)MaxLoading函數(shù)具體實施對解空間的分支限函數(shù)具體實施對解空間的分支限界搜索。界搜索。EnQueue用于將活結(jié)點加入到活結(jié)點隊列中，用于將活結(jié)點加入到活結(jié)點隊列中，該函數(shù)首先檢查該函數(shù)首先檢查i是否等于是否等于n，如果，如果i=n，則表示，則表示當(dāng)前活結(jié)點為一個葉結(jié)點，由于葉結(jié)點不會被當(dāng)前活結(jié)點為一個葉結(jié)點，由于葉結(jié)點不會被進(jìn)一步擴(kuò)展，因此不必加入到活結(jié)點，如果該進(jìn)一步擴(kuò)展，因此不必加入到活結(jié)點，如果該葉結(jié)點表示的可行解優(yōu)于當(dāng)前最優(yōu)解，更新最葉結(jié)點表示的可行解優(yōu)于當(dāng)前最優(yōu)解，更新最優(yōu)解。當(dāng)優(yōu)解。當(dāng)in時，當(dāng)前活結(jié)點是一個內(nèi)部結(jié)點，時，當(dāng)前活結(jié)點是一個內(nèi)部結(jié)點，加入到活結(jié)

22、點隊列中。加入到活結(jié)點隊列中。6.3裝載問題裝載問題28templateT MaxLoading(T w, T c, int n) / 返回最優(yōu)裝載值返回最優(yōu)裝載值 / 為層次為層次1 初始化初始化 Queue Q; / 活結(jié)點隊列活結(jié)點隊列 Q.Add(-1); /標(biāo)記本層的尾部標(biāo)記本層的尾部 int i = 1; / 當(dāng)前擴(kuò)展結(jié)點的層當(dāng)前擴(kuò)展結(jié)點的層 T Ew = 0, / 當(dāng)前擴(kuò)展結(jié)點的權(quán)當(dāng)前擴(kuò)展結(jié)點的權(quán)值值 bestw = 0; / 目前的最優(yōu)值目前的最優(yōu)值while (true) / 檢查左孩子結(jié)點檢查左孩子結(jié)點 if (Ew + wi = c) / xi = 1 EnQueue(

23、Q, Ew + wi, bestw, i, n); / 右孩子總是可行的右孩子總是可行的 EnQueue(Q, Ew, bestw, i, n); / xi = 0 Q.Delete(Ew); / 取下一個擴(kuò)展結(jié)點取下一個擴(kuò)展結(jié)點 if (Ew = -1) / 到達(dá)層的尾部到達(dá)層的尾部 if (Q.IsEmpty( ) return bestw; Q.Add(-1); / 同層結(jié)點的尾部同層結(jié)點的尾部 Q.Delete(Ew); / 取下一擴(kuò)展結(jié)點取下一擴(kuò)展結(jié)點 i+; / 進(jìn)入下一層進(jìn)入下一層 29templatevoid EnQueue( Queue &Q, T wt,T&

24、 bestw, int i, int n) /該函數(shù)負(fù)責(zé)加入活結(jié)點該函數(shù)負(fù)責(zé)加入活結(jié)點 / 如果不是葉結(jié)點，則將結(jié)點權(quán)值如果不是葉結(jié)點，則將結(jié)點權(quán)值w t加入隊列加入隊列Q if (i = n) / 葉子葉子 if (wt bestw) bestw = wt; else Q.Add(wt); / 不是葉子不是葉子6.3裝載問題裝載問題303. 算法的改進(jìn)算法的改進(jìn)節(jié)點的左子樹表示將此集裝箱裝上船，右子樹表示不將節(jié)點的左子樹表示將此集裝箱裝上船，右子樹表示不將此集裝箱裝上船。設(shè)此集裝箱裝上船。設(shè)bestw是當(dāng)前最優(yōu)解；是當(dāng)前最優(yōu)解；Ew是當(dāng)前擴(kuò)是當(dāng)前擴(kuò)展結(jié)點所相應(yīng)的重量；展結(jié)點所相應(yīng)的重量；r是

25、剩余集裝箱的重量。則當(dāng)是剩余集裝箱的重量。則當(dāng)Ew+r bestw時，可將其右子樹剪去，因為此時若要船裝時，可將其右子樹剪去，因為此時若要船裝最多集裝箱，就應(yīng)該把此箱裝上船最多集裝箱，就應(yīng)該把此箱裝上船。算法算法MaxLoading初始時將初始時將bestw置為置為0，直到搜索到第，直到搜索到第一個葉結(jié)點時才更新一個葉結(jié)點時才更新bestw。因此在算法搜索到第一個。因此在算法搜索到第一個葉結(jié)點之前，總有葉結(jié)點之前，總有bestw0，r0，故，故Ew+rbestw總是總是成立，也就是說，此時右子樹測試不起作用。成立，也就是說，此時右子樹測試不起作用。算法中結(jié)點相應(yīng)的重量僅在搜索進(jìn)入左子樹時增加，

26、因算法中結(jié)點相應(yīng)的重量僅在搜索進(jìn)入左子樹時增加，因此，可以在算法每一次進(jìn)入左子樹時更新此，可以在算法每一次進(jìn)入左子樹時更新bestw的值。的值。6.2裝載問題裝載問題311116011601631163116015300151501516011161516.3裝載問題裝載問題32n使用限界函數(shù)進(jìn)行改進(jìn)使用限界函數(shù)進(jìn)行改進(jìn)T MaxLoading( T w , T c, int n ) Queue Q; / 活節(jié)點隊列活節(jié)點隊列 Q.Add (-1) ; /標(biāo)記本層的尾部標(biāo)記本層的尾部 int i = 1; / 當(dāng)前擴(kuò)展節(jié)點的層當(dāng)前擴(kuò)展節(jié)點的層 T Ew = 0, /當(dāng)前擴(kuò)展節(jié)點的重量當(dāng)前擴(kuò)展節(jié)

27、點的重量 bestw = 0; / 目前的最優(yōu)值目前的最優(yōu)值 r = 0; / 當(dāng)前擴(kuò)展節(jié)點中余下的重量當(dāng)前擴(kuò)展節(jié)點中余下的重量 for (int j = 2; j = n; j+) r + = wi; 6.3裝載問題裝載問題33while (true) / 檢查擴(kuò)展結(jié)點的左孩子檢查擴(kuò)展結(jié)點的左孩子 T wt = Ew + wi; / 左孩子的權(quán)值左孩子的權(quán)值 if (wt bestw) bestw = wt; / 若不是葉子，則添加到隊列若不是葉子，則添加到隊列 if (i bestw & i n ) Q.Add(Ew); / 可能含最優(yōu)解可能含最優(yōu)解 Q.Delete(Ew); /

28、 取下一個擴(kuò)展結(jié)點取下一個擴(kuò)展結(jié)點 if (Ew = -1) / 到達(dá)層的尾部到達(dá)層的尾部 if (Q.IsEmpty() return bestw; Q.Add(-1); /添加尾部標(biāo)記添加尾部標(biāo)記 Q.Delete(Ew); / 取下一個擴(kuò)展結(jié)點取下一個擴(kuò)展結(jié)點 i+; r - = wi; 6.3裝載問題裝載問題35 為了在算法結(jié)束后能方便地構(gòu)造出與最優(yōu)值相為了在算法結(jié)束后能方便地構(gòu)造出與最優(yōu)值相應(yīng)的最優(yōu)解，算法必須存儲相應(yīng)子集樹中從活結(jié)點應(yīng)的最優(yōu)解，算法必須存儲相應(yīng)子集樹中從活結(jié)點到根結(jié)點的路徑。為此目的，可在每個結(jié)點處設(shè)置到根結(jié)點的路徑。為此目的，可在每個結(jié)點處設(shè)置指向其父結(jié)點的指針，

29、并設(shè)置左、右兒子標(biāo)志。指向其父結(jié)點的指針，并設(shè)置左、右兒子標(biāo)志。 templateclass QNode QNode *parent; / 指向父結(jié)點的指針指向父結(jié)點的指針 bool LChild; / 左兒子標(biāo)志左兒子標(biāo)志 Type weight; / 結(jié)點所相應(yīng)的載重量結(jié)點所相應(yīng)的載重量;4. 構(gòu)造最優(yōu)解構(gòu)造最優(yōu)解6.3裝載問題裝載問題36016311631160153001515000false16false015true016true6.3裝載問題裝載問題37優(yōu)先隊列式分支限界法優(yōu)先隊列式分支限界法存儲活結(jié)點的方式存儲活結(jié)點的方式: 最大優(yōu)先隊列存儲活結(jié)點表。最大優(yōu)先隊列存儲活結(jié)點表。

30、活結(jié)點活結(jié)點x在優(yōu)先隊列中的優(yōu)先級定義在優(yōu)先隊列中的優(yōu)先級定義: 從根結(jié)點到結(jié)點從根結(jié)點到結(jié)點x的路徑所相應(yīng)的載重量再加上剩余集裝箱的重量之和。的路徑所相應(yīng)的載重量再加上剩余集裝箱的重量之和。擴(kuò)展結(jié)點的選擇：擴(kuò)展結(jié)點的選擇： 優(yōu)先隊列中優(yōu)先級最大的活結(jié)點成優(yōu)先隊列中優(yōu)先級最大的活結(jié)點成為下一個擴(kuò)展結(jié)點。以結(jié)點為下一個擴(kuò)展結(jié)點。以結(jié)點x為根的子樹中所有結(jié)點相為根的子樹中所有結(jié)點相應(yīng)的路徑的載重量應(yīng)的路徑的載重量不超過它的優(yōu)先級不超過它的優(yōu)先級x.uweight。子集。子集樹中樹中葉結(jié)點葉結(jié)點所相應(yīng)的載重量與其優(yōu)先級相同。所相應(yīng)的載重量與其優(yōu)先級相同。算法終止條件：算法終止條件： 子集樹中葉結(jié)點所

31、相應(yīng)的載重量與其子集樹中葉結(jié)點所相應(yīng)的載重量與其優(yōu)先級相同，一旦有一個葉結(jié)點成為當(dāng)前擴(kuò)展結(jié)點，則優(yōu)先級相同，一旦有一個葉結(jié)點成為當(dāng)前擴(kuò)展結(jié)點，則可以斷言該葉結(jié)點所相應(yīng)的解即為最優(yōu)解。此時可終止可以斷言該葉結(jié)點所相應(yīng)的解即為最優(yōu)解。此時可終止算法。算法。 6.3裝載問題裝載問題如何證明？如何證明？38可以用兩種不同方式來實現(xiàn)n在結(jié)點優(yōu)先隊列的每一個活結(jié)點中保存從解空間樹在結(jié)點優(yōu)先隊列的每一個活結(jié)點中保存從解空間樹的根結(jié)點到該活結(jié)點的路徑，在算法確定了達(dá)到最的根結(jié)點到該活結(jié)點的路徑，在算法確定了達(dá)到最優(yōu)值的葉結(jié)點時，就在該葉結(jié)點處同時得到相應(yīng)的優(yōu)值的葉結(jié)點時，就在該葉結(jié)點處同時得到相應(yīng)的最優(yōu)解。最

32、優(yōu)解。n在算法的搜索進(jìn)程中保存當(dāng)前已構(gòu)造出的在算法的搜索進(jìn)程中保存當(dāng)前已構(gòu)造出的部分解空部分解空間樹間樹，這樣在算法確定了達(dá)到最優(yōu)值的葉結(jié)點時，這樣在算法確定了達(dá)到最優(yōu)值的葉結(jié)點時，就可以在解空間樹中從該葉結(jié)點開始向根結(jié)點回溯，就可以在解空間樹中從該葉結(jié)點開始向根結(jié)點回溯，構(gòu)造出相應(yīng)的最優(yōu)解。構(gòu)造出相應(yīng)的最優(yōu)解。6.2裝載問題裝載問題39優(yōu)先隊列優(yōu)先隊列解空間樹解空間樹w = 16, 15, 15 r3= 0, r2=15, r1 = 30兩種結(jié)構(gòu)：子集樹結(jié)點結(jié)構(gòu)，大堆結(jié)點結(jié)構(gòu)兩種結(jié)構(gòu)：子集樹結(jié)點結(jié)構(gòu)，大堆結(jié)點結(jié)構(gòu)462i=1E=0truefalse302i=2Ew=16Efalse313i=

33、3Ew=16Efalse164Ei=2Ew=0true303Ei=3Ew=15true304154falsei=4Ew=30E6.3裝載問題裝載問題找到最優(yōu)解找到最優(yōu)解 3040用一個元素類型為用一個元素類型為HeapNode的的最大堆最大堆來表示活結(jié)點優(yōu)先隊列。來表示活結(jié)點優(yōu)先隊列。解空間樹中結(jié)點類型為解空間樹中結(jié)點類型為bbnode。template class HeapNode;class bbnode friend void AddLiveNode( MaxHeap HeapNode &, bbnode *, int, bool, int); friend int MaxLoa

34、ding( int *, int , int, int *); friend class AdjacencyGraph; private: bbnode * parent; /指向父結(jié)點的指針指向父結(jié)點的指針 bool LChild; /左兒子結(jié)點標(biāo)志左兒子結(jié)點標(biāo)志;41用一個元素類型為用一個元素類型為HeapNode的的最大堆最大堆來表示活結(jié)點優(yōu)先隊列。來表示活結(jié)點優(yōu)先隊列。解空間樹中結(jié)點類型為解空間樹中結(jié)點類型為bbnodetemplateclass HeapNode friend void AddLiveNode( MaxHeap HeapNode &, bbnode *, Ty

35、pe, bool, int); friend Type MaxLoading (Type *, Type, int , int *); public: operator Type() const return uweight; private: bbnode *ptr /指向活結(jié)點在子集樹中相應(yīng)結(jié)點的指針指向活結(jié)點在子集樹中相應(yīng)結(jié)點的指針 Type uweight; /活結(jié)點優(yōu)先級（上界）活結(jié)點優(yōu)先級（上界） int level; /活結(jié)點在子集樹中所處的層序號活結(jié)點在子集樹中所處的層序號 ；42函數(shù)函數(shù)AddLiveNode以結(jié)點元素類型以結(jié)點元素類型bbnode將一個新產(chǎn)生的活結(jié)將一個新產(chǎn)

36、生的活結(jié)點加入到子集樹中，并以結(jié)點元素類型點加入到子集樹中，并以結(jié)點元素類型HeapNode將這個新結(jié)將這個新結(jié)點插入到表示活結(jié)點優(yōu)先隊列的最大堆中。點插入到表示活結(jié)點優(yōu)先隊列的最大堆中。templatevoid AddLiveNode(MaxHeap HeapNode &H, bbnode *E, Type wt, bool ch, int lev) /將活結(jié)點加入到表示活結(jié)點優(yōu)先隊列的最大堆將活結(jié)點加入到表示活結(jié)點優(yōu)先隊列的最大堆H中中 bbnode *b = new bbnode; b - parent = E; b - LChild = ch; HeapNode N; N.uw

37、eight = wt; N.level = lev; N.ptr = b; H.Insert(N);向子集樹中向子集樹中添加結(jié)點添加結(jié)點向活結(jié)點優(yōu)向活結(jié)點優(yōu)先隊列插入先隊列插入新結(jié)點新結(jié)點43n函數(shù)函數(shù)MaxLoading具體實施對解空間的優(yōu)先隊列式分具體實施對解空間的優(yōu)先隊列式分支限界搜索，在函數(shù)中，定義最大堆的容量為支限界搜索，在函數(shù)中，定義最大堆的容量為1000，即在運行期間，最多容納即在運行期間，最多容納1000個結(jié)點。個結(jié)點。n第第i+1層結(jié)點的剩余重量層結(jié)點的剩余重量ri定義為第定義為第i+1到第到第n個物品個物品重量的和。重量的和。n變量變量E指向子集樹中當(dāng)前擴(kuò)展結(jié)點，指向子集樹

38、中當(dāng)前擴(kuò)展結(jié)點，Ew是相應(yīng)的重是相應(yīng)的重量。算法開始時，量。算法開始時，i=1, Ew =0，子集樹的根結(jié)點為擴(kuò)，子集樹的根結(jié)點為擴(kuò)展結(jié)點。展結(jié)點。6.2裝載問題裝載問題44templateType MaxLoading(Type w , Type c, int n, int bestx ) /優(yōu)先隊列式分支限界法，返回最優(yōu)載重量，優(yōu)先隊列式分支限界法，返回最優(yōu)載重量，bestx返回最優(yōu)解返回最優(yōu)解 /定義最大堆的容量為定義最大堆的容量為1000 MaxHeap HeapNode H( 1000 ); /定義剩余重量數(shù)組定義剩余重量數(shù)組r Type * r = new Type n + 1 ;

39、 r n = 0; for( int j = n -1; j 0; j - -) r j = r j+1 + w j + 1 ; /初始化初始化 int i = 1; / 當(dāng)前擴(kuò)展結(jié)點所處的層當(dāng)前擴(kuò)展結(jié)點所處的層 bbnode * E =0; /當(dāng)前擴(kuò)展結(jié)點當(dāng)前擴(kuò)展結(jié)點 Type Ew = 0; /擴(kuò)展結(jié)點所相應(yīng)的載重量擴(kuò)展結(jié)點所相應(yīng)的載重量 45 while( i ! = n + 1 ) /非葉結(jié)點非葉結(jié)點 /檢查當(dāng)前擴(kuò)展結(jié)點的兒子結(jié)點檢查當(dāng)前擴(kuò)展結(jié)點的兒子結(jié)點 if( Ew + w i = c ) /左兒子結(jié)點為可行結(jié)點左兒子結(jié)點為可行結(jié)點 AddLiveNode( H, E, Ew +

40、w i + r i , true, i +1); /end if AddLiveNode(H, E, Ew+r i , false, i+1); /右兒子結(jié)點右兒子結(jié)點/取下一擴(kuò)展結(jié)點取下一擴(kuò)展結(jié)點 HeapNode N; H.DeletMax(N); /非空非空 i = N.level; E = N.ptr; Ew = N. uweight r i -1 ; /優(yōu)先權(quán)優(yōu)先權(quán)uweight = Ew + r i - 1; /end while for( int j = n ; j 0; j - - ) /構(gòu)造當(dāng)前最優(yōu)解構(gòu)造當(dāng)前最優(yōu)解 bestx j = E - LChild; E = E -

41、parent; /end for return Ew; 46優(yōu)先隊列優(yōu)先隊列解空間樹解空間樹w = 16, 15, 15 r n = 0; for( int j = n -1; j 0; j - -) r j = r j+1 + w j + 1 ;r3= 0, r2=15, r1 = 30if( Ew + w i = c ) AddLiveNode( H, E, Ew + w i + r i , true, i +1); AddLiveNode(H, E, Ew+r i , false, i+1); HeapNode N; H.DeletMax(N); i = N.level; E = N.p

42、tr; Ew = N. uweight r i -1 ; 462i=1E=0truefalse302i=2Ew=16Efalse313i=3Ew=16Efalse164Ei=2Ew=0true303Ei=3Ew=15true304154falsei=4Ew=30E6.2裝載問題裝載問題47truefalsefalsefalsetruetruefalseEfor( int j = n ; j 0; j - - ) /構(gòu)造當(dāng)前最優(yōu)解構(gòu)造當(dāng)前最優(yōu)解 bestx j = E - LChild; E = E - parent;bestx3 = truebestx2 = truebestx1 = fals

43、eEE6.3裝載問題裝載問題480-1背包問題背包問題6.4 0-1背包問題背包問題49采用優(yōu)先隊列式分支限界采用優(yōu)先隊列式分支限界n活結(jié)點優(yōu)先隊列中結(jié)點元素活結(jié)點優(yōu)先隊列中結(jié)點元素N的優(yōu)先級由該的優(yōu)先級由該結(jié)點的上界函數(shù)結(jié)點的上界函數(shù)Bound計算出的值計算出的值uprofit給給出。出。n以結(jié)點以結(jié)點N為根的子樹中任一結(jié)點的價值不超為根的子樹中任一結(jié)點的價值不超過過N.profit。6.4 0-1背包問題背包問題50nclass Object : 描述物品描述物品nclass bbnode: 子集樹結(jié)點子集樹結(jié)點 nclass HeapNode: 優(yōu)先隊列結(jié)點優(yōu)先隊列結(jié)點nclass Kn

44、ap: 對整個問題的初始化及調(diào)用其它函數(shù)解決問對整個問題的初始化及調(diào)用其它函數(shù)解決問題題nKnap: Bound(i) :計算第計算第i層結(jié)點相應(yīng)價值的上界層結(jié)點相應(yīng)價值的上界nKnap: AddLiveNode(Typep up, Typep cp, Typew cw, bool ch, int level); ) 將一個新的活結(jié)點插入到子集樹和最大堆將一個新的活結(jié)點插入到子集樹和最大堆H中中nKnap: MaxKnapsack() :優(yōu)先隊列式分支限界法優(yōu)先隊列式分支限界法6.4 0-1背包問題背包問題51class Object friend int Knapsack( int *, i

45、nt *, int, int, int *); public: int operator = a.d); private: int ID; float d; /單位重量價值單位重量價值template class Knap;class bbnode /子集空間樹中結(jié)點類型子集空間樹中結(jié)點類型 friend Knap ; friend int Knapsack(int *, int *, int, int, int *); private: bbnode *parent; /指向父結(jié)點的指針指向父結(jié)點的指針 bool LChild; /左兒子結(jié)點標(biāo)志左兒子結(jié)點標(biāo)志;6.4 0-1背包問題背包問題

46、52templateclass HeapNode friend Knap ; public: operator Typep() const return uprofit; private: Typep uprofit, /結(jié)點的價值上界結(jié)點的價值上界 profit; /結(jié)點所相應(yīng)的價值結(jié)點所相應(yīng)的價值 Typew weight; /結(jié)點所相應(yīng)的重量結(jié)點所相應(yīng)的重量 int level; /活結(jié)點在子集樹中所處的層序號活結(jié)點在子集樹中所處的層序號 bbnode * ptr; /指向活結(jié)點在子集樹中相應(yīng)結(jié)點的指針指向活結(jié)點在子集樹中相應(yīng)結(jié)點的指針;6.4 0-1背包問題背包問題53template

47、 class Knap friend Typep Knapsack(Typep *, Typew *, Typew, int, int *); public: Typep MaxKnapsack(); private: MaxHeapHeapNode *H; Typep Bound( int i); void AddLiveNode( Typep up, Typep cp, Typew cw, bool ch, int level); bbnode * E; /指向擴(kuò)展結(jié)點的指針指向擴(kuò)展結(jié)點的指針 Typew c; /背包容量背包容量 int n; /物品總數(shù)物品總數(shù) Typew * w; /物品重量數(shù)組物品重量數(shù)組 Typep * p; /物品價值數(shù)組物品價值數(shù)組 Typew cw; /當(dāng)前裝包重量當(dāng)前裝包重量 Typep cp; /當(dāng)前裝包價值當(dāng)前裝包價值 int *bestx; /最優(yōu)解最優(yōu)解；6.4 0-1背包問題背包問題54函數(shù)函數(shù)MaxKnapsack實施對于子集樹的優(yōu)先隊列式實施對于子集樹的優(yōu)先隊列式分支限界搜索分支限界搜索templateTypep Knap: MaxKnapsack() /優(yōu)先隊列式分支限界法，返回最大價值，優(yōu)先隊列式分支限界法，返回最大價值，bestx返回最優(yōu)解返回最優(yōu)解 /