礦大算法第6章 分支限界法

1、學(xué)習(xí)要點(diǎn)學(xué)習(xí)要點(diǎn)理解分支限界法的剪枝搜索策略。理解分支限界法的剪枝搜索策略。掌握分支限界法的算法框架掌握分支限界法的算法框架 （1）隊(duì)列式）隊(duì)列式(FIFO)分支限界法分支限界法 （2）優(yōu)先隊(duì)列式分支限界法）優(yōu)先隊(duì)列式分支限界法 第第6 6章章 分支限界法分支限界法通過應(yīng)用范例學(xué)習(xí)分支限界法的設(shè)計(jì)策略。通過應(yīng)用范例學(xué)習(xí)分支限界法的設(shè)計(jì)策略。 （1）單源最短路徑問題）單源最短路徑問題 （2）裝載問題；）裝載問題； （3）布線問題）布線問題 （4）0-1背包問題；背包問題；（5）最大團(tuán)問題；）最大團(tuán)問題；（6）旅行售貨員問題）旅行售貨員問題（7）電路板排列問題）電路板排列問題（8）批處理作業(yè)調(diào)度問

2、題）批處理作業(yè)調(diào)度問題2022年5月25日星期三第6章 分支限界分支限界法法26.1 分支限界法的基本思想分支限界法的基本思想n類似于回溯法，分支限界法在搜索解空間時(shí)，也類似于回溯法，分支限界法在搜索解空間時(shí)，也使用樹形結(jié)構(gòu)來組織解空間（子集樹和排列樹）。使用樹形結(jié)構(gòu)來組織解空間（子集樹和排列樹）。與回溯法不同的是，回溯算法使用深度優(yōu)先方法與回溯法不同的是，回溯算法使用深度優(yōu)先方法搜索樹結(jié)構(gòu)，而分支限界法用寬度優(yōu)先或最小耗搜索樹結(jié)構(gòu)，而分支限界法用寬度優(yōu)先或最小耗費(fèi)方法來搜索這些樹。費(fèi)方法來搜索這些樹。n分支限界（分支限界（branch and bound）是另一種系統(tǒng)地）是另一種系統(tǒng)地搜索解

3、空間的方法，它與回溯法的主要區(qū)別在于搜索解空間的方法，它與回溯法的主要區(qū)別在于對對E結(jié)點(diǎn)的擴(kuò)充方式。結(jié)點(diǎn)的擴(kuò)充方式。2022年5月25日星期三第6章 分支限界分支限界法法3n每個(gè)活結(jié)點(diǎn)有且僅有一次機(jī)會變成每個(gè)活結(jié)點(diǎn)有且僅有一次機(jī)會變成E結(jié)點(diǎn)。當(dāng)一個(gè)結(jié)點(diǎn)。當(dāng)一個(gè)結(jié)點(diǎn)變?yōu)榻Y(jié)點(diǎn)變?yōu)镋結(jié)點(diǎn)時(shí)，則生成從該結(jié)點(diǎn)移動(dòng)一步即可結(jié)點(diǎn)時(shí)，則生成從該結(jié)點(diǎn)移動(dòng)一步即可到達(dá)的所有新結(jié)點(diǎn)。在生成的結(jié)點(diǎn)中，拋棄那些不到達(dá)的所有新結(jié)點(diǎn)。在生成的結(jié)點(diǎn)中，拋棄那些不可能導(dǎo)出（最優(yōu)）可行解的結(jié)點(diǎn)，其余結(jié)點(diǎn)加入活可能導(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)作為下一

4、個(gè)E結(jié)結(jié)點(diǎn)。從活結(jié)點(diǎn)表中取出所選擇的結(jié)點(diǎn)并進(jìn)行擴(kuò)充，點(diǎn)。從活結(jié)點(diǎn)表中取出所選擇的結(jié)點(diǎn)并進(jìn)行擴(kuò)充，直到找到解或活動(dòng)表為空，擴(kuò)充過程才結(jié)束。直到找到解或活動(dòng)表為空，擴(kuò)充過程才結(jié)束。n相對而言，分支限界法的解空間比回溯法大得多，相對而言，分支限界法的解空間比回溯法大得多，因此當(dāng)內(nèi)存容量有限時(shí)，回溯法成功的可能性更大。因此當(dāng)內(nèi)存容量有限時(shí)，回溯法成功的可能性更大。2022年5月25日星期三第6章 分支限界分支限界法法4n選擇選擇E結(jié)點(diǎn)的兩種常用方法：結(jié)點(diǎn)的兩種常用方法：隊(duì)列式（隊(duì)列式（FIFO)：將活結(jié)點(diǎn)表組織成隊(duì)列，按先：將活結(jié)點(diǎn)表組織成隊(duì)列，按先進(jìn)先出原則選取下一個(gè)結(jié)點(diǎn)作為當(dāng)前擴(kuò)展結(jié)點(diǎn)。進(jìn)先出原則

5、選取下一個(gè)結(jié)點(diǎn)作為當(dāng)前擴(kuò)展結(jié)點(diǎn)。優(yōu)先隊(duì)列式：每個(gè)結(jié)點(diǎn)都有一個(gè)對應(yīng)的耗費(fèi)或收優(yōu)先隊(duì)列式：每個(gè)結(jié)點(diǎn)都有一個(gè)對應(yīng)的耗費(fèi)或收益。按優(yōu)先級選取下一個(gè)結(jié)點(diǎn)作為當(dāng)前擴(kuò)展結(jié)點(diǎn)。益。按優(yōu)先級選取下一個(gè)結(jié)點(diǎn)作為當(dāng)前擴(kuò)展結(jié)點(diǎn)。n如果求解最小耗費(fèi)的解，則活結(jié)點(diǎn)表可用最小堆如果求解最小耗費(fèi)的解，則活結(jié)點(diǎn)表可用最小堆來建立，下一個(gè)來建立，下一個(gè)E結(jié)點(diǎn)就是具有最小耗費(fèi)的活結(jié)點(diǎn)；結(jié)點(diǎn)就是具有最小耗費(fèi)的活結(jié)點(diǎn)；如果求解最大收益的解，則可用最大堆來構(gòu)造活如果求解最大收益的解，則可用最大堆來構(gòu)造活結(jié)點(diǎn)表，下一個(gè)結(jié)點(diǎn)表，下一個(gè)E結(jié)點(diǎn)是具有最大收益的活結(jié)點(diǎn)。結(jié)點(diǎn)是具有最大收益的活結(jié)點(diǎn)。2022年5月25日星期三第6章 分支限界分支限界

6、法法5n例例 0/1背包問題背包問題 n=3, w=20,15,15, p=45,25,25, c= 30。n 下面分別利用兩種方法來解決背包問題。下面分別利用兩種方法來解決背包問題。1）FIFO分支限界法分支限界法 結(jié)點(diǎn)將按照結(jié)點(diǎn)將按照FIFO順序從隊(duì)列中取出；順序從隊(duì)列中取出；2）優(yōu)先隊(duì)列式：）優(yōu)先隊(duì)列式： 使用一個(gè)最大堆，其中的使用一個(gè)最大堆，其中的E結(jié)點(diǎn)按照每個(gè)活結(jié)點(diǎn)收結(jié)點(diǎn)按照每個(gè)活結(jié)點(diǎn)收益值的降序，或是按照活結(jié)點(diǎn)任意子樹的葉結(jié)點(diǎn)所益值的降序，或是按照活結(jié)點(diǎn)任意子樹的葉結(jié)點(diǎn)所能獲得的收益估計(jì)值的降序從隊(duì)列中取出。能獲得的收益估計(jì)值的降序從隊(duì)列中取出。2022年5月25日星期三第6章 分

7、支限界分支限界法法61）FIFO分支限界法：初始時(shí)活結(jié)點(diǎn)隊(duì)列為空，以分支限界法：初始時(shí)活結(jié)點(diǎn)隊(duì)列為空，以 A作為作為E結(jié)點(diǎn)，結(jié)點(diǎn)，生成的兩個(gè)子結(jié)點(diǎn)生成的兩個(gè)子結(jié)點(diǎn)B和和C都是可行的，因此加入活結(jié)點(diǎn)隊(duì)列中，都是可行的，因此加入活結(jié)點(diǎn)隊(duì)列中，結(jié)點(diǎn)結(jié)點(diǎn)A被刪除。下一個(gè)擴(kuò)展結(jié)點(diǎn)是被刪除。下一個(gè)擴(kuò)展結(jié)點(diǎn)是B，擴(kuò)展得到結(jié)點(diǎn)，擴(kuò)展得到結(jié)點(diǎn)D和和E，D是不可行的，被刪除，而是不可行的，被刪除，而E被加入隊(duì)列中。下一步結(jié)點(diǎn)被加入隊(duì)列中。下一步結(jié)點(diǎn)C成為成為擴(kuò)展結(jié)點(diǎn)，擴(kuò)展得到結(jié)點(diǎn)擴(kuò)展結(jié)點(diǎn)，擴(kuò)展得到結(jié)點(diǎn)F和和G，兩者都是可行結(jié)點(diǎn)，加入隊(duì)，兩者都是可行結(jié)點(diǎn)，加入隊(duì)列中。擴(kuò)展列中。擴(kuò)展E得到得到J和和K，J不可行而被刪

8、除，不可行而被刪除，K是一個(gè)可行的是一個(gè)可行的葉結(jié)點(diǎn)，并產(chǎn)生一個(gè)到目前為止可行的解，它的收益值為葉結(jié)點(diǎn)，并產(chǎn)生一個(gè)到目前為止可行的解，它的收益值為45。W=(16,15,15)P=(45,25,25)C=30101116/45 30/5000112022年5月25日星期三第6章 分支限界分支限界法法7n下一個(gè)擴(kuò)展結(jié)點(diǎn)是下一個(gè)擴(kuò)展結(jié)點(diǎn)是F，它產(chǎn)生兩個(gè)孩子，它產(chǎn)生兩個(gè)孩子L、M，L代代表一個(gè)可行的解且其收益值為表一個(gè)可行的解且其收益值為50，M代表另一個(gè)收代表另一個(gè)收益值為益值為25的可行解。的可行解。G是最后一個(gè)擴(kuò)展結(jié)點(diǎn)，它的是最后一個(gè)擴(kuò)展結(jié)點(diǎn)，它的孩子孩子N和和O都是可行的。由于活結(jié)點(diǎn)隊(duì)列變?yōu)?/p>

9、空，都是可行的。由于活結(jié)點(diǎn)隊(duì)列變?yōu)榭?，因此搜索過程終止，最佳解的收益值為因此搜索過程終止，最佳解的收益值為50。n本例中，結(jié)點(diǎn)擴(kuò)展次序?yàn)楸纠校Y(jié)點(diǎn)擴(kuò)展次序?yàn)? A; B; C; E; F; G。n可見，可見，F(xiàn)IFO分支限界法與從根結(jié)點(diǎn)出發(fā)的廣度優(yōu)先分支限界法與從根結(jié)點(diǎn)出發(fā)的廣度優(yōu)先搜索非常類似，區(qū)別是在搜索非常類似，區(qū)別是在FIFO分枝定界中不可行的分枝定界中不可行的結(jié)點(diǎn)不會被搜索。結(jié)點(diǎn)不會被搜索。2022年5月25日星期三第6章 分支限界分支限界法法82）優(yōu)先隊(duì)列式：）優(yōu)先隊(duì)列式： （按物品價(jià)值優(yōu)先次序）（按物品價(jià)值優(yōu)先次序）n以以A作為初始結(jié)點(diǎn)。擴(kuò)展得到結(jié)點(diǎn)作為初始結(jié)點(diǎn)。擴(kuò)展得到結(jié)點(diǎn)B

10、和和C，兩者都是，兩者都是可行的并被插入堆中，結(jié)點(diǎn)可行的并被插入堆中，結(jié)點(diǎn)B獲得的收益值是獲得的收益值是45，而結(jié)點(diǎn)而結(jié)點(diǎn)C得到的收益值為得到的收益值為0。A被刪除，被刪除，B成為下一成為下一個(gè)擴(kuò)展結(jié)點(diǎn)。擴(kuò)展個(gè)擴(kuò)展結(jié)點(diǎn)。擴(kuò)展B得到結(jié)點(diǎn)得到結(jié)點(diǎn)D和和E，D是不可行的是不可行的而被刪除，而被刪除，E加入堆中。由于加入堆中。由于E具有收益值具有收益值45，而，而C為為0，因?yàn)?，因?yàn)镋成為下一個(gè)擴(kuò)展結(jié)點(diǎn)。成為下一個(gè)擴(kuò)展結(jié)點(diǎn)。n擴(kuò)展擴(kuò)展E時(shí)生成結(jié)點(diǎn)時(shí)生成結(jié)點(diǎn)J和和K，J不可行而被刪除，不可行而被刪除，K是一是一個(gè)可行的解，因此個(gè)可行的解，因此K為作為目前能找到的最優(yōu)解而為作為目前能找到的最優(yōu)解而記錄下來

11、，然后記錄下來，然后K被刪除。被刪除。2022年5月25日星期三第6章 分支限界分支限界法法9n由于只剩下一個(gè)活結(jié)點(diǎn)由于只剩下一個(gè)活結(jié)點(diǎn)C在堆中，因此在堆中，因此C作為擴(kuò)展作為擴(kuò)展結(jié)點(diǎn)被展開，生成結(jié)點(diǎn)被展開，生成F、G兩個(gè)結(jié)點(diǎn)插入堆中。兩個(gè)結(jié)點(diǎn)插入堆中。F的收的收益值為益值為25，因此成為下一個(gè)擴(kuò)展結(jié)點(diǎn)，展開后得到，因此成為下一個(gè)擴(kuò)展結(jié)點(diǎn)，展開后得到結(jié)點(diǎn)結(jié)點(diǎn)L和和M，但，但L、M都被刪除，因?yàn)樗鼈兪侨~結(jié)點(diǎn)，都被刪除，因?yàn)樗鼈兪侨~結(jié)點(diǎn)，同時(shí)同時(shí)L所對應(yīng)的解被作為當(dāng)前最優(yōu)解記錄下來。最所對應(yīng)的解被作為當(dāng)前最優(yōu)解記錄下來。最終，終，G成為擴(kuò)展結(jié)點(diǎn)，生成的結(jié)點(diǎn)為成為擴(kuò)展結(jié)點(diǎn)，生成的結(jié)點(diǎn)為N和和O，兩者

12、，兩者都是葉結(jié)點(diǎn)而被刪除，兩者所對應(yīng)的解都比當(dāng)前最都是葉結(jié)點(diǎn)而被刪除，兩者所對應(yīng)的解都比當(dāng)前最優(yōu)解還差，因此最優(yōu)解保持不變。此時(shí)堆變?yōu)榭眨瑑?yōu)解還差，因此最優(yōu)解保持不變。此時(shí)堆變?yōu)榭?，搜索過程終止。最優(yōu)解為搜索過程終止。最優(yōu)解為A到到L的路徑（的路徑（0,1,1）,價(jià)價(jià)值值50。n本例中，結(jié)點(diǎn)擴(kuò)展次序?yàn)楸纠?，結(jié)點(diǎn)擴(kuò)展次序?yàn)? A; B; E; C; F; G。2022年5月25日星期三第6章 分支限界分支限界法法10n利用一個(gè)限界函數(shù)能加速最優(yōu)解的搜索過程。限界利用一個(gè)限界函數(shù)能加速最優(yōu)解的搜索過程。限界函數(shù)為最大收益設(shè)置了一個(gè)上限，通過展開一個(gè)特函數(shù)為最大收益設(shè)置了一個(gè)上限，通過展開一個(gè)特殊

13、的結(jié)點(diǎn)可能獲得這個(gè)最大收益。如果一個(gè)結(jié)點(diǎn)的殊的結(jié)點(diǎn)可能獲得這個(gè)最大收益。如果一個(gè)結(jié)點(diǎn)的限界函數(shù)值不大于目前最優(yōu)解的收益值，則此結(jié)點(diǎn)限界函數(shù)值不大于目前最優(yōu)解的收益值，則此結(jié)點(diǎn)會被刪除而不作展開，更進(jìn)一步，在優(yōu)先隊(duì)列分支會被刪除而不作展開，更進(jìn)一步，在優(yōu)先隊(duì)列分支限界法中，可以使結(jié)點(diǎn)按照它們收益的限界函數(shù)值限界法中，可以使結(jié)點(diǎn)按照它們收益的限界函數(shù)值的非升序從堆中取出，而不是按照結(jié)點(diǎn)的實(shí)際收益的非升序從堆中取出，而不是按照結(jié)點(diǎn)的實(shí)際收益值來取出。這種策略從可能到達(dá)一個(gè)好的葉結(jié)點(diǎn)的值來取出。這種策略從可能到達(dá)一個(gè)好的葉結(jié)點(diǎn)的活結(jié)點(diǎn)出發(fā)，而不是從目前具有較大收益值的結(jié)點(diǎn)活結(jié)點(diǎn)出發(fā)，而不是從目前具有較

14、大收益值的結(jié)點(diǎn)出發(fā)。出發(fā)。2022年5月25日星期三第6章 分支限界分支限界法法11n例例 旅行商問題旅行商問題 對于如下圖的四城市旅行商問題，對于如下圖的四城市旅行商問題，其對應(yīng)的解空間為一棵由結(jié)點(diǎn)其對應(yīng)的解空間為一棵由結(jié)點(diǎn)A到結(jié)點(diǎn)到結(jié)點(diǎn)Q的排列樹。的排列樹。 對于此問題，有兩種搜索解空間樹方式：對于此問題，有兩種搜索解空間樹方式：1）使用）使用FIFO分支限界法；分支限界法； 擴(kuò)展結(jié)點(diǎn)順序：擴(kuò)展結(jié)點(diǎn)順序：B C D E F G H (I) J K2）優(yōu)先隊(duì)列式分支限界法：）優(yōu)先隊(duì)列式分支限界法： 使用最小耗費(fèi)方法，即用一個(gè)最小堆來存儲活結(jié)使用最小耗費(fèi)方法，即用一個(gè)最小堆來存儲活結(jié)點(diǎn)。點(diǎn)。n

15、擴(kuò)展結(jié)點(diǎn)順序：擴(kuò)展結(jié)點(diǎn)順序：B E D H J K (I) (C)2022年5月25日星期三第6章 分支限界分支限界法法1232活結(jié)點(diǎn)：活結(jié)點(diǎn)：B CDE DEFG EFGHI FGHIJK GHIJK HIJK IJK JK K(n-1)!個(gè)葉結(jié)點(diǎn)個(gè)葉結(jié)點(diǎn) TSP問題的解空間樹問題的解空間樹143230201065443413ABEDCKJIHGFQPONML2434242559662632最優(yōu)解：最優(yōu)解：1 3 2 4 1 (結(jié)點(diǎn)結(jié)點(diǎn)N) 1 4 2 3 1 (結(jié)點(diǎn)結(jié)點(diǎn)K)E結(jié)點(diǎn)：結(jié)點(diǎn)： B C D E F G H I J K2022年5月25日星期三第6章 分支限界分支限界法法13n設(shè)計(jì)

16、限界函數(shù)的主要目是利用最少的時(shí)間，在內(nèi)存設(shè)計(jì)限界函數(shù)的主要目是利用最少的時(shí)間，在內(nèi)存允許的范圍內(nèi)去解決問題。允許的范圍內(nèi)去解決問題。n不要片面追求能產(chǎn)生具有最少數(shù)目的解空間結(jié)點(diǎn)，不要片面追求能產(chǎn)生具有最少數(shù)目的解空間結(jié)點(diǎn)，減少結(jié)點(diǎn)并不是根本的目標(biāo)。因此，我們需要的是減少結(jié)點(diǎn)并不是根本的目標(biāo)。因此，我們需要的是一個(gè)能夠有效地減少計(jì)算時(shí)間并因此而使產(chǎn)生的結(jié)一個(gè)能夠有效地減少計(jì)算時(shí)間并因此而使產(chǎn)生的結(jié)點(diǎn)數(shù)目也減少的限界函數(shù)。點(diǎn)數(shù)目也減少的限界函數(shù)。n回溯法與分支限界法在空間方面的比較回溯法與分支限界法在空間方面的比較 回溯法比分支限界法在占用內(nèi)存方面具有優(yōu)勢。回溯法比分支限界法在占用內(nèi)存方面具有優(yōu)勢

17、。n回溯法：回溯法：O(解空間的最大路徑長度解空間的最大路徑長度)n分支限界法：分支限界法：O(解空間大小解空間大小)。2022年5月25日星期三第6章 分支限界分支限界法法14n對于一個(gè)子集空間：對于一個(gè)子集空間： 回溯法回溯法O(n) 分支限界法：分支限界法：O(2n) 。n對于排列空間：對于排列空間： 回溯法：回溯法：O(n) 分支限界法：分支限界法：O(n!) 。n雖然最大收益（或最小耗費(fèi)）分支限界法在直覺上雖然最大收益（或最小耗費(fèi)）分支限界法在直覺上要好于回溯法，并且在許多情況下可能會比回溯法要好于回溯法，并且在許多情況下可能會比回溯法檢查更少的結(jié)點(diǎn)，但在實(shí)際應(yīng)用中，它可能會在回檢查

18、更少的結(jié)點(diǎn)，但在實(shí)際應(yīng)用中，它可能會在回溯法超出允許的時(shí)間限制之前就超出了內(nèi)存的限制。溯法超出允許的時(shí)間限制之前就超出了內(nèi)存的限制。2022年5月25日星期三第6章 分支限界分支限界法法156.3 6.3 裝載問題裝載問題問題描述問題描述: :n n個(gè)集裝箱裝到個(gè)集裝箱裝到2 2艘載重量分別為艘載重量分別為c1,c2c1,c2的的貨輪貨輪, ,其中集裝箱其中集裝箱i i的重量為的重量為wiwi且且 問題要求找到一個(gè)合理的裝載方案可將這問題要求找到一個(gè)合理的裝載方案可將這n個(gè)個(gè)貨貨箱箱裝上這裝上這2艘輪船。艘輪船。211ccwnii當(dāng)當(dāng) 時(shí)問題等價(jià)于子集和問題時(shí)問題等價(jià)于子集和問題; ; 當(dāng)當(dāng)c

19、1=c2c1=c2且且 時(shí)時(shí)問題等價(jià)于劃分問題問題等價(jià)于劃分問題. .211ccwnii112cwnii若裝載問題有解若裝載問題有解, 采用如下策略可得一個(gè)最優(yōu)裝載方案采用如下策略可得一個(gè)最優(yōu)裝載方案:(1)將第一艘輪船盡可能裝滿將第一艘輪船盡可能裝滿; (2)將剩余的將剩余的貨貨箱裝到第二艘輪船上。箱裝到第二艘輪船上。將第一艘船盡可能裝滿等價(jià)于如下將第一艘船盡可能裝滿等價(jià)于如下0-l背包問題背包問題:niiixw1m axm ax12cxwniii2022年5月25日星期三第6章 分支限界分支限界法法166.3 裝載問題裝載問題1）隊(duì)列式分支限界法：）隊(duì)列式分支限界法：ntemplatevo

20、id EnQueue(Queue &Q, T wt, T& bestw, int i, int n)/ 若不是葉結(jié)點(diǎn)，則將結(jié)點(diǎn)權(quán)值若不是葉結(jié)點(diǎn)，則將結(jié)點(diǎn)權(quán)值wt加入加入Qif (i = n) / 葉結(jié)點(diǎn)不必加入葉結(jié)點(diǎn)不必加入Q中中 if (wt bestw) bestw = wt;/檢查并更新最優(yōu)解檢查并更新最優(yōu)解 else Q.Add(wt); / 不是葉子，應(yīng)加入不是葉子，應(yīng)加入Q中中/ EnQueue將活結(jié)點(diǎn)加入活結(jié)點(diǎn)隊(duì)列將活結(jié)點(diǎn)加入活結(jié)點(diǎn)隊(duì)列Q中。中。Q中用中用wt表示每個(gè)活結(jié)點(diǎn)對應(yīng)的當(dāng)前載重量，表示每個(gè)活結(jié)點(diǎn)對應(yīng)的當(dāng)前載重量，wt=-1表示到表示到達(dá)解空間樹的同一層結(jié)點(diǎn)的尾部。達(dá)解空

21、間樹的同一層結(jié)點(diǎn)的尾部。2022年5月25日星期三第6章 分支限界分支限界法法17n注意：注意：EnQueue可能會失敗，因?yàn)榭赡軟]有足夠的內(nèi)可能會失敗，因?yàn)榭赡軟]有足夠的內(nèi)存來給隊(duì)列增加結(jié)點(diǎn)。存來給隊(duì)列增加結(jié)點(diǎn)。 EnQueue并沒有去捕獲并沒有去捕獲Q.Add中的中的NoMem異常。異常。ntemplateT MaxLoading(T w , T c, int n) / 返回最優(yōu)裝載值返回最優(yōu)裝載值/初始化初始化Queue Q; / 活結(jié)點(diǎn)隊(duì)列活結(jié)點(diǎn)隊(duì)列Q.Add(-1); /標(biāo)記本層活結(jié)點(diǎn)的尾部標(biāo)記本層活結(jié)點(diǎn)的尾部int i = 1; / 當(dāng)前當(dāng)前E結(jié)點(diǎn)的層位于根結(jié)點(diǎn)結(jié)點(diǎn)的層位于根結(jié)點(diǎn)T

22、 Ew = 0, / E結(jié)點(diǎn)的權(quán)值（載重量）結(jié)點(diǎn)的權(quán)值（載重量）bestw = 0; / 目前的最優(yōu)載重量目前的最優(yōu)載重量/ 搜索子集空間樹搜索子集空間樹2022年5月25日星期三第6章 分支限界分支限界法法18 while (true) if (Ew+wi=bestw)時(shí)，才選擇右孩子。時(shí)，才選擇右孩子。n而在前面程序中，在而在前面程序中，在i變?yōu)樽優(yōu)閚之前，之前，bestw的值一直保的值一直保持不變（直到搜索到第一個(gè)葉結(jié)點(diǎn)時(shí)才更新持不變（直到搜索到第一個(gè)葉結(jié)點(diǎn)時(shí)才更新bestw ），），因此在因此在i等于等于n之前對右孩子的測試總為真，因?yàn)橹皩τ液⒆拥臏y試總為真，因?yàn)閎estw=0且且r

23、0。即此時(shí)對右子樹的測試不起作用。即此時(shí)對右子樹的測試不起作用。n為使對右子樹的測試盡早生效，應(yīng)盡早更新為使對右子樹的測試盡早生效，應(yīng)盡早更新bestw的的值。值。2022年5月25日星期三第6章 分支限界分支限界法法21n因?yàn)樽顑?yōu)裝載的重量是子集樹中可行結(jié)點(diǎn)的重量因?yàn)樽顑?yōu)裝載的重量是子集樹中可行結(jié)點(diǎn)的重量的最大值，所以只有在向左子樹移動(dòng)時(shí)這些重量的最大值，所以只有在向左子樹移動(dòng)時(shí)這些重量才會增大，因此可以在每次進(jìn)行這種移動(dòng)時(shí)改變才會增大，因此可以在每次進(jìn)行這種移動(dòng)時(shí)改變bestw的值。的值。n根據(jù)以上思想，改進(jìn)的算法如下。根據(jù)以上思想，改進(jìn)的算法如下。n當(dāng)活結(jié)點(diǎn)加入隊(duì)列時(shí)，當(dāng)活結(jié)點(diǎn)加入隊(duì)列時(shí)

24、，wt不會超過不會超過bestw，故，故bestw不用更新。因此在不用更新。因此在MaxLoading中直接用一中直接用一條簡單語句條簡單語句Q.Add(wt)取代了函數(shù)取代了函數(shù)EnQueue。2022年5月25日星期三第6章 分支限界分支限界法法22ntemplateT MaxLoading(T w , T c, int n) / 返回最優(yōu)裝載值。首先初始化返回最優(yōu)裝載值。首先初始化 Queue Q; / 活結(jié)點(diǎn)隊(duì)列活結(jié)點(diǎn)隊(duì)列 Q.Add(-1); /標(biāo)記本層的尾部標(biāo)記本層的尾部 int i = 1; / E結(jié)點(diǎn)的所在的層結(jié)點(diǎn)的所在的層 T Ew = 0, / E結(jié)點(diǎn)的重量結(jié)點(diǎn)的重量 be

25、stw=0; / 目前的最優(yōu)裝載量目前的最優(yōu)裝載量 r = 0; for (int j = 2; j = n; j+) r += wi; / E結(jié)點(diǎn)處目前余下的集裝箱重量結(jié)點(diǎn)處目前余下的集裝箱重量 / 開始搜索子集空間樹開始搜索子集空間樹2022年5月25日星期三第6章 分支限界分支限界法法23while (true) / 檢查檢查E結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的左孩子T wt = Ew + wi; / 左孩子的重量左孩子的重量if (wt bestw) bestw = wt; /更新更新bestw if (i bestw & i n) / 檢查右孩子檢查右孩子 Q.Add(Ew); / 可能含最優(yōu)解可能

26、含最優(yōu)解Q.Delete(Ew); / 取下一個(gè)取下一個(gè)E-結(jié)點(diǎn)結(jié)點(diǎn)2022年5月25日星期三第6章 分支限界分支限界法法24 if (Ew = -1) / 到達(dá)同一層的尾部到達(dá)同一層的尾部 if (Q.IsEmpty() return bestw; Q.Add(-1); /添加尾部標(biāo)記添加尾部標(biāo)記 Q.Delete(Ew); / 取下一個(gè)取下一個(gè)E-結(jié)點(diǎn)結(jié)點(diǎn) i+; / 進(jìn)入下一層進(jìn)入下一層 r -= wi; / E結(jié)點(diǎn)中余下的重量結(jié)點(diǎn)中余下的重量 2022年5月25日星期三第6章 分支限界分支限界法法253. 尋找最優(yōu)解：需記錄從每個(gè)活結(jié)點(diǎn)到達(dá)根的路徑，尋找最優(yōu)解：需記錄從每個(gè)活結(jié)點(diǎn)到達(dá)根

27、的路徑，因此對每個(gè)結(jié)點(diǎn)設(shè)置指向其父結(jié)點(diǎn)得指針?；罱Y(jié)因此對每個(gè)結(jié)點(diǎn)設(shè)置指向其父結(jié)點(diǎn)得指針。活結(jié)點(diǎn)隊(duì)列中元素的類型是點(diǎn)隊(duì)列中元素的類型是QNode。template class QNode friend void EnQueue(9個(gè)參數(shù)個(gè)參數(shù)); friend T MaxLoadig(T *, T, int, int *);private: QNode *parent; / 父結(jié)點(diǎn)指針父結(jié)點(diǎn)指針 bool LChild; / 是否為父結(jié)點(diǎn)的左孩子是否為父結(jié)點(diǎn)的左孩子 T weight; / 到達(dá)本結(jié)點(diǎn)的路徑對應(yīng)的載重量到達(dá)本結(jié)點(diǎn)的路徑對應(yīng)的載重量 ;2022年5月25日星期三第6章 分支限界分支

28、限界法法261)QueueQnode *& Q 隊(duì)列隊(duì)列Q2)T wt 從根到當(dāng)前結(jié)點(diǎn)所對應(yīng)得裝載量從根到當(dāng)前結(jié)點(diǎn)所對應(yīng)得裝載量3)int i 當(dāng)前結(jié)點(diǎn)所在的層次當(dāng)前結(jié)點(diǎn)所在的層次4)int n 集裝箱數(shù)目集裝箱數(shù)目5)T bestw 當(dāng)前最優(yōu)裝載量當(dāng)前最優(yōu)裝載量6)Qnode *E 當(dāng)前擴(kuò)展結(jié)點(diǎn)（當(dāng)前擴(kuò)展結(jié)點(diǎn)（E結(jié)點(diǎn)）結(jié)點(diǎn)）7)Qnode *bestE 當(dāng)前最優(yōu)當(dāng)前最優(yōu)E結(jié)點(diǎn)結(jié)點(diǎn)8)int * bestx 最優(yōu)解最優(yōu)解9)Bool ch 左兒子：左兒子：ch=1 ； 右兒子：右兒子：ch=0 ACB 1 30 0 15ABC2022年5月25日星期三第6章 分支限界分支限界法法27ntemp

29、latevoid EnQueue(QueueQNode* &Q , T wt, int i, int n, T bestw, QNode *E, QNode *&bestE, int bestx , bool ch) / 如果不是葉結(jié)點(diǎn)，則向隊(duì)列如果不是葉結(jié)點(diǎn)，則向隊(duì)列Q中添加一個(gè)中添加一個(gè)i 層、層、重量為重量為wt的活結(jié)點(diǎn)；的活結(jié)點(diǎn)； 新結(jié)點(diǎn)是新結(jié)點(diǎn)是E的一個(gè)孩子。當(dāng)新結(jié)的一個(gè)孩子。當(dāng)新結(jié)點(diǎn)是左孩子時(shí)，點(diǎn)是左孩子時(shí)， ch為為true。 / 若是葉子，則若是葉子，則ch的值就是的值就是bestxn。if (i = n) / 葉結(jié)點(diǎn)葉結(jié)點(diǎn)2022年5月25日星期三第6章 分支限界分支限界法法

30、28nif (wt = bestw) /wt至多等于至多等于bestw / 目前的最優(yōu)解目前的最優(yōu)解bestE = E;bestxn = ch;return; / 不是葉子不是葉子, 則添加到隊(duì)列則添加到隊(duì)列Q中中QNode *b;b = new QNode;b-weight = wt;b-parent = E;b-LChild = ch;Q.Add(b);2022年5月25日星期三第6章 分支限界分支限界法法29ntemplateT MaxLoading(T w , T c, int n, int bestx ) / 返回最優(yōu)裝載值，并在返回最優(yōu)裝載值，并在bestx中返回最優(yōu)解中返回最優(yōu)解

31、/ 使用使用F I F O分枝定界算法；分枝定界算法； 初始化初始化QueueQNode* Q; / 活結(jié)點(diǎn)隊(duì)列活結(jié)點(diǎn)隊(duì)列Q.Add(0); / 0 代表本層的尾部代表本層的尾部int i = 1; / E結(jié)點(diǎn)的層結(jié)點(diǎn)的層T Ew = 0, / E結(jié)點(diǎn)的重量結(jié)點(diǎn)的重量 bestw = 0; / 迄今得到的最優(yōu)值迄今得到的最優(yōu)值 r=0; / E結(jié)點(diǎn)中余下的重量（剩余集裝箱重量）結(jié)點(diǎn)中余下的重量（剩余集裝箱重量）for (int j = 2; j = n; j+) r += wi;QNode *E = 0, / 當(dāng)前的當(dāng)前的E-結(jié)點(diǎn)結(jié)點(diǎn) * b e s t E ; / 目前最優(yōu)的目前最優(yōu)的E結(jié)點(diǎn)

32、結(jié)點(diǎn)2022年5月25日星期三第6章 分支限界分支限界法法30n/ 搜索子集空間樹搜索子集空間樹while (true) T wt = Ew + wi; if (wt bestw) bestw = wt; EnQueue(Q, wt, i, n, bestw, E, bestE, bestx, true);/ 檢查右孩子檢查右孩子if (Ew+rbestw)EnQueue(Q, Ew, i, n, bestw, E, bestE, bestx, false);Q. Delete(E) ; / 取下一個(gè)取下一個(gè)E結(jié)點(diǎn)結(jié)點(diǎn)2022年5月25日星期三第6章 分支限界分支限界法法31nif (! E)

33、 / 同層結(jié)點(diǎn)的尾部同層結(jié)點(diǎn)的尾部 if (Q.IsEmpty() break; Q.Add(0); / 添加層結(jié)點(diǎn)尾部標(biāo)志添加層結(jié)點(diǎn)尾部標(biāo)志 Q.Delete(E) ; / 從隊(duì)列從隊(duì)列Q中取下一個(gè)中取下一個(gè)E結(jié)點(diǎn)結(jié)點(diǎn) i+ ; / E-結(jié)點(diǎn)的層次結(jié)點(diǎn)的層次 r -= wi; / E結(jié)點(diǎn)中余下的重量結(jié)點(diǎn)中余下的重量Ew=E- weight ; / 新的新的E結(jié)點(diǎn)的重量結(jié)點(diǎn)的重量/end of while/ 沿著從沿著從bestE到根的路徑構(gòu)造到根的路徑構(gòu)造xn-1,x1, 而而xn已經(jīng)在函數(shù)已經(jīng)在函數(shù)EnQueue中賦值。中賦值。for (j = n - 1; j 0; j-) bestxj

34、 = bestE-LChild; / bool型型int型型 bestE = bestE-parent;return bestw;2022年5月25日星期三第6章 分支限界分支限界法法324）優(yōu)先隊(duì)列式分支限界法）優(yōu)先隊(duì)列式分支限界法 在對子集樹進(jìn)行最大收益分支限界搜索時(shí)，活結(jié)點(diǎn)在對子集樹進(jìn)行最大收益分支限界搜索時(shí)，活結(jié)點(diǎn)列表是一個(gè)最大優(yōu)先級隊(duì)列，其中每個(gè)活結(jié)點(diǎn)列表是一個(gè)最大優(yōu)先級隊(duì)列，其中每個(gè)活結(jié)點(diǎn)x都都有一個(gè)相應(yīng)的重量上限（最大收益）。這個(gè)重量上有一個(gè)相應(yīng)的重量上限（最大收益）。這個(gè)重量上限是結(jié)點(diǎn)限是結(jié)點(diǎn)x 相應(yīng)的重量加上剩余貨箱的總重量，所相應(yīng)的重量加上剩余貨箱的總重量，所有的活結(jié)點(diǎn)按其

35、重量上限的遞減順序變?yōu)橛械幕罱Y(jié)點(diǎn)按其重量上限的遞減順序變?yōu)镋結(jié)點(diǎn)。結(jié)點(diǎn)。 注意：如果結(jié)點(diǎn)注意：如果結(jié)點(diǎn)x的重量上限是的重量上限是x.uweight，則在子，則在子樹中不可能存在重量超過樹中不可能存在重量超過x.uweight 的結(jié)點(diǎn)。另外，的結(jié)點(diǎn)。另外，當(dāng)葉結(jié)點(diǎn)對應(yīng)的重量等于它的重量上限時(shí)，可以得當(dāng)葉結(jié)點(diǎn)對應(yīng)的重量等于它的重量上限時(shí)，可以得出結(jié)論：該葉結(jié)點(diǎn)所對應(yīng)的解就是最優(yōu)解，其他任出結(jié)論：該葉結(jié)點(diǎn)所對應(yīng)的解就是最優(yōu)解，其他任何活結(jié)點(diǎn)都不會有更優(yōu)的解，搜索終止。何活結(jié)點(diǎn)都不會有更優(yōu)的解，搜索終止。2022年5月25日星期三第6章 分支限界分支限界法法33n上述策略可以用兩種方法來實(shí)現(xiàn)：上述策略

36、可以用兩種方法來實(shí)現(xiàn)：1)最大優(yōu)先級隊(duì)列中的活結(jié)點(diǎn)都是互相獨(dú)立的，最大優(yōu)先級隊(duì)列中的活結(jié)點(diǎn)都是互相獨(dú)立的，因此每個(gè)活結(jié)點(diǎn)內(nèi)部必須記錄從子集樹的根到因此每個(gè)活結(jié)點(diǎn)內(nèi)部必須記錄從子集樹的根到此結(jié)點(diǎn)的路徑。一旦找到了最優(yōu)裝載所對應(yīng)的此結(jié)點(diǎn)的路徑。一旦找到了最優(yōu)裝載所對應(yīng)的葉結(jié)點(diǎn)，就利用這些路徑信息來計(jì)算葉結(jié)點(diǎn)，就利用這些路徑信息來計(jì)算x 值。值。2)除了把結(jié)點(diǎn)加入最大優(yōu)先隊(duì)列之外，結(jié)點(diǎn)還必除了把結(jié)點(diǎn)加入最大優(yōu)先隊(duì)列之外，結(jié)點(diǎn)還必須放在另一個(gè)獨(dú)立的樹結(jié)構(gòu)中，這個(gè)樹結(jié)構(gòu)用須放在另一個(gè)獨(dú)立的樹結(jié)構(gòu)中，這個(gè)樹結(jié)構(gòu)用來表示所生成的子集樹的一部分。當(dāng)找到最大來表示所生成的子集樹的一部分。當(dāng)找到最大裝載之后，就可

37、以沿著路徑從葉結(jié)點(diǎn)逐步返回裝載之后，就可以沿著路徑從葉結(jié)點(diǎn)逐步返回到根，從而計(jì)算出到根，從而計(jì)算出x 值。值。2022年5月25日星期三第6章 分支限界分支限界法法34n采用第二種方案：優(yōu)先隊(duì)列用采用第二種方案：優(yōu)先隊(duì)列用HeapNode 類型類型的最大堆來表示。的最大堆來表示。ntemplateclass HeapNode public: operator T () const return uweight;private: bbnode *ptr; /指向活結(jié)點(diǎn)在子集樹中位置指向活結(jié)點(diǎn)在子集樹中位置 T uweight; / 活結(jié)點(diǎn)的重量上限活結(jié)點(diǎn)的重量上限 int level; /活結(jié)點(diǎn)

38、所在子集樹的層活結(jié)點(diǎn)所在子集樹的層 ;2022年5月25日星期三第6章 分支限界分支限界法法35n子集樹中結(jié)點(diǎn)的類型是子集樹中結(jié)點(diǎn)的類型是bbnode。結(jié)點(diǎn)按。結(jié)點(diǎn)按uweight值值從最大堆中取出。從最大堆中取出。nclass bbnode private: bbnode *parent; / 父結(jié)點(diǎn)指針父結(jié)點(diǎn)指針 bool LChild; / 當(dāng)是父結(jié)點(diǎn)的左孩子時(shí)取當(dāng)是父結(jié)點(diǎn)的左孩子時(shí)取true ;n函數(shù)函數(shù)AddLiveNode用于把用于把bbnode類型的活結(jié)點(diǎn)加類型的活結(jié)點(diǎn)加到子樹中，并把到子樹中，并把HeapNode類型的活結(jié)點(diǎn)插入最大類型的活結(jié)點(diǎn)插入最大堆。堆。AddLiveNo

39、de必須被定義為必須被定義為bbnode和和HeapNode的友元。的友元。2022年5月25日星期三第6章 分支限界分支限界法法36ntemplate void AddLiveNode(MaxHeapHeapNode &H, bbnode *E, T wt, bool ch, int lev) / 向最大堆向最大堆H中增添一個(gè)層為中增添一個(gè)層為lev，上限重量為，上限重量為wt的活結(jié)點(diǎn)，新結(jié)點(diǎn)是的活結(jié)點(diǎn)，新結(jié)點(diǎn)是E的兒子的兒子(左孩子：左孩子：ch=true) bbnode *b = new bbnode; /新結(jié)點(diǎn)加入子集樹新結(jié)點(diǎn)加入子集樹 b-parent = E; b-LChild =

40、 ch; HeapNode N; /新結(jié)點(diǎn)插入隊(duì)列中新結(jié)點(diǎn)插入隊(duì)列中 N.uweight = wt; N.level = lev; N.ptr = b; H.Insert(N);2022年5月25日星期三第6章 分支限界分支限界法法37n函數(shù)函數(shù)MaxLoading的思路的思路1)定義一個(gè)容量為定義一個(gè)容量為1000的最大堆?？梢杂盟鼇斫鉀Q的最大堆?？梢杂盟鼇斫鉀Q優(yōu)先隊(duì)列中活結(jié)點(diǎn)數(shù)在任何時(shí)候都不超過優(yōu)先隊(duì)列中活結(jié)點(diǎn)數(shù)在任何時(shí)候都不超過1000的的裝箱問題。對于更大型的問題，需要一個(gè)容量更裝箱問題。對于更大型的問題，需要一個(gè)容量更大的最大堆。如果改用基于指針的優(yōu)先隊(duì)列，則大的最大堆。如果改用基于

41、指針的優(yōu)先隊(duì)列，則不必預(yù)置隊(duì)列容量。不必預(yù)置隊(duì)列容量。2)初始化剩余重量數(shù)組初始化剩余重量數(shù)組r。第。第i+1層的結(jié)點(diǎn)（即層的結(jié)點(diǎn)（即x1 i的值都已確定）對應(yīng)的剩余總重量為的值都已確定）對應(yīng)的剩余總重量為ri=wj，j從從i+1到到n。3)變量變量E指向子集樹中的當(dāng)前指向子集樹中的當(dāng)前E結(jié)點(diǎn)，結(jié)點(diǎn)，Ew 是該結(jié)點(diǎn)是該結(jié)點(diǎn)對應(yīng)的重量，對應(yīng)的重量， i是它所在的層。是它所在的層。2022年5月25日星期三第6章 分支限界分支限界法法38n起初，根結(jié)點(diǎn)是起初，根結(jié)點(diǎn)是E結(jié)點(diǎn)，因此取結(jié)點(diǎn)，因此取i=1, Ew=0。由于。由于沒有明確地存儲根結(jié)點(diǎn)，因此沒有明確地存儲根結(jié)點(diǎn)，因此E的初始值取為的初始值取

42、為0。while 循環(huán)用于產(chǎn)生當(dāng)前循環(huán)用于產(chǎn)生當(dāng)前E結(jié)點(diǎn)的左、右孩子。如結(jié)點(diǎn)的左、右孩子。如果左孩子是可行的（即沒有超出容量），則將它果左孩子是可行的（即沒有超出容量），則將它加入到子集樹中并作為一個(gè)第加入到子集樹中并作為一個(gè)第i+1層結(jié)點(diǎn)加入最大層結(jié)點(diǎn)加入最大堆中。可行結(jié)點(diǎn)的右孩子總是可行的，它總被加堆中?？尚薪Y(jié)點(diǎn)的右孩子總是可行的，它總被加入子樹及最大堆中。在完成添加操作后，接著從入子樹及最大堆中。在完成添加操作后，接著從最大堆中取出下一個(gè)最大堆中取出下一個(gè)E結(jié)點(diǎn)。如果沒有下一個(gè)結(jié)點(diǎn)。如果沒有下一個(gè)E結(jié)結(jié)點(diǎn)，則不存在可行的解。如果下一個(gè)點(diǎn)，則不存在可行的解。如果下一個(gè)E結(jié)點(diǎn)是葉結(jié)點(diǎn)是葉結(jié)點(diǎn)

43、（結(jié)點(diǎn)（n+1結(jié)點(diǎn)），則它是一個(gè)最優(yōu)裝載，可以結(jié)點(diǎn)），則它是一個(gè)最優(yōu)裝載，可以沿著從葉到根的路徑來確定裝載方案。沿著從葉到根的路徑來確定裝載方案。2022年5月25日星期三第6章 分支限界分支限界法法39ntemplateT MaxLoading(T w , T c, int n, int bestx )/ 返回最優(yōu)裝載值，返回最優(yōu)裝載值，bestx保存最優(yōu)解保存最優(yōu)解/ 定義一個(gè)最多有定義一個(gè)最多有1000個(gè)活結(jié)點(diǎn)的最大堆個(gè)活結(jié)點(diǎn)的最大堆MaxHeapHeapNode H(1000);/ 定義剩余集裝箱重量的數(shù)組定義剩余集裝箱重量的數(shù)組r/ rj 為為wj+1n的重量之和的重量之和T *r

44、= new Tn+1;rn = 0;for (int j = n-1; j 0; j-) rj = rj+1 + wj+1;/ 初始化層初始化層12022年5月25日星期三第6章 分支限界分支限界法法40int i = 1; / E結(jié)點(diǎn)的層結(jié)點(diǎn)的層bbnode *E = 0; / 當(dāng)前當(dāng)前E結(jié)點(diǎn)結(jié)點(diǎn)T Ew = 0; / E結(jié)點(diǎn)的重量結(jié)點(diǎn)的重量/ 搜索子集空間樹搜索子集空間樹while (i != n+1) / 不在葉子上不在葉子上/ 檢查檢查E結(jié)點(diǎn)的孩子結(jié)點(diǎn)的孩子 if (Ew + wi = c) / 可行的左孩子可行的左孩子 AddLiveNode(H, E, Ew+wi+ri, true

45、, i+1);/ 右孩子右孩子 AddLiveNode(H, E, Ew+ri, false, i+1);/ 取下一個(gè)取下一個(gè)E-結(jié)點(diǎn)結(jié)點(diǎn)2022年5月25日星期三第6章 分支限界分支限界法法41 HeapNode N; H.DeleteMax(N); / 不能為空不能為空 i = N.level; E = N.ptr; Ew = N.uweight - ri-1;/ 沿著從沿著從E結(jié)點(diǎn)到根的路徑構(gòu)造結(jié)點(diǎn)到根的路徑構(gòu)造bestx for (int j = n; j 0; j-) bestxj = E-LChild; / 從從bool轉(zhuǎn)換為轉(zhuǎn)換為int E = E- parent;return

46、Ew;2022年5月25日星期三第6章 分支限界分支限界法法42n說明：說明：bestw表示當(dāng)前所有可行結(jié)點(diǎn)的重量的最大值，表示當(dāng)前所有可行結(jié)點(diǎn)的重量的最大值，而優(yōu)先隊(duì)列中可能有許多其而優(yōu)先隊(duì)列中可能有許多其uweight不超過不超過bestw的的活結(jié)點(diǎn)，因此這些結(jié)點(diǎn)不可能幫助我們找到最優(yōu)的活結(jié)點(diǎn)，因此這些結(jié)點(diǎn)不可能幫助我們找到最優(yōu)的葉結(jié)點(diǎn)，這些結(jié)點(diǎn)浪費(fèi)了隊(duì)列空間及插入葉結(jié)點(diǎn)，這些結(jié)點(diǎn)浪費(fèi)了隊(duì)列空間及插入/刪除時(shí)間，刪除時(shí)間，所以應(yīng)清除這些結(jié)點(diǎn)。一種策略是，在插入某個(gè)結(jié)所以應(yīng)清除這些結(jié)點(diǎn)。一種策略是，在插入某個(gè)結(jié)點(diǎn)之前檢查是否有點(diǎn)之前檢查是否有uweight bestw。但由于。但由于best

47、w在在執(zhí)行過程中不斷增大，所以目前插入的結(jié)點(diǎn)在以后執(zhí)行過程中不斷增大，所以目前插入的結(jié)點(diǎn)在以后并不能保證有效。更好的策略是在每次并不能保證有效。更好的策略是在每次bestw增大時(shí)，增大時(shí)，刪除隊(duì)列中所有刪除隊(duì)列中所有uweightbesew的結(jié)點(diǎn)。這要求刪除的結(jié)點(diǎn)。這要求刪除具有最小具有最小uweight的結(jié)點(diǎn)。因此，隊(duì)列必須支持如下的結(jié)點(diǎn)。因此，隊(duì)列必須支持如下的操作：插入、刪除最大結(jié)點(diǎn)、刪除最小結(jié)點(diǎn)。這的操作：插入、刪除最大結(jié)點(diǎn)、刪除最小結(jié)點(diǎn)。這種優(yōu)先隊(duì)列也被稱作雙端優(yōu)先隊(duì)列。種優(yōu)先隊(duì)列也被稱作雙端優(yōu)先隊(duì)列。2022年5月25日星期三第6章 分支限界分支限界法法436.7 旅行商問題旅行商

48、問題n旅行商問題的解空間是一個(gè)排列樹。與在子集旅行商問題的解空間是一個(gè)排列樹。與在子集樹中進(jìn)行最大收益和最小耗費(fèi)分支限界搜索類樹中進(jìn)行最大收益和最小耗費(fèi)分支限界搜索類似，該問題有兩種實(shí)現(xiàn)的方法：似，該問題有兩種實(shí)現(xiàn)的方法：1)只使用一個(gè)優(yōu)先隊(duì)列，隊(duì)列中的每個(gè)元素中都只使用一個(gè)優(yōu)先隊(duì)列，隊(duì)列中的每個(gè)元素中都包含到達(dá)根的路徑。包含到達(dá)根的路徑。2)保留一個(gè)部分解空間樹和一個(gè)優(yōu)先隊(duì)列，優(yōu)先保留一個(gè)部分解空間樹和一個(gè)優(yōu)先隊(duì)列，優(yōu)先隊(duì)列中的元素并不包含到達(dá)根的路徑。這里只隊(duì)列中的元素并不包含到達(dá)根的路徑。這里只實(shí)現(xiàn)方法實(shí)現(xiàn)方法(1)。2022年5月25日星期三第6章 分支限界分支限界法法44n用一個(gè)最小

49、優(yōu)先隊(duì)列來記錄活結(jié)點(diǎn)，隊(duì)列中結(jié)點(diǎn)的用一個(gè)最小優(yōu)先隊(duì)列來記錄活結(jié)點(diǎn)，隊(duì)列中結(jié)點(diǎn)的類型為類型為MinHeapNode。說明：。說明：ns表示結(jié)點(diǎn)在排列樹中的層次表示結(jié)點(diǎn)在排列樹中的層次n x：記錄當(dāng)前解。：記錄當(dāng)前解。 x0:s為根結(jié)點(diǎn)到當(dāng)前結(jié)點(diǎn)的路徑為根結(jié)點(diǎn)到當(dāng)前結(jié)點(diǎn)的路徑, 而剩余待訪問的結(jié)點(diǎn)是而剩余待訪問的結(jié)點(diǎn)是xs+1:n-1）ncc：從根結(jié)點(diǎn)到當(dāng)前結(jié)點(diǎn)的耗費(fèi)：從根結(jié)點(diǎn)到當(dāng)前結(jié)點(diǎn)的耗費(fèi)nLcost：該結(jié)點(diǎn)子樹中任意葉結(jié)點(diǎn)中的最小耗費(fèi)，表：該結(jié)點(diǎn)子樹中任意葉結(jié)點(diǎn)中的最小耗費(fèi)，表示子樹費(fèi)用的下界。示子樹費(fèi)用的下界。n rcost：從頂點(diǎn)：從頂點(diǎn)xsxn-1出發(fā)的所有邊的最小耗費(fèi)出發(fā)的所有邊的最

50、小耗費(fèi)之和。之和。nOperator T ( )const return lcost當(dāng)類型為當(dāng)類型為MinHeapNode(T)的數(shù)據(jù)被轉(zhuǎn)換成為類型的數(shù)據(jù)被轉(zhuǎn)換成為類型T時(shí)，其結(jié)時(shí)，其結(jié)果即為果即為lcost的值。的值。2022年5月25日星期三第6章 分支限界分支限界法法45n首先生成一個(gè)容量為首先生成一個(gè)容量為1000的最小堆，表示活結(jié)點(diǎn)最的最小堆，表示活結(jié)點(diǎn)最小優(yōu)先隊(duì)列。活結(jié)點(diǎn)按其小優(yōu)先隊(duì)列?；罱Y(jié)點(diǎn)按其lcost值從最小堆中取出。值從最小堆中取出。接下來，計(jì)算有向圖中從每個(gè)頂點(diǎn)出發(fā)的邊中耗費(fèi)接下來，計(jì)算有向圖中從每個(gè)頂點(diǎn)出發(fā)的邊中耗費(fèi)最小的邊所具有的耗費(fèi)最小的邊所具有的耗費(fèi)MinOut。

51、如果某個(gè)頂點(diǎn)沒有。如果某個(gè)頂點(diǎn)沒有出邊，則沒有旅行路徑，搜索終止。否則啟動(dòng)最小出邊，則沒有旅行路徑，搜索終止。否則啟動(dòng)最小耗費(fèi)分支限界搜索。根的孩子（結(jié)點(diǎn)耗費(fèi)分支限界搜索。根的孩子（結(jié)點(diǎn)B）作為第一）作為第一個(gè)個(gè)E結(jié)點(diǎn)，在此結(jié)點(diǎn)上，所生成的旅行路徑前綴只結(jié)點(diǎn)，在此結(jié)點(diǎn)上，所生成的旅行路徑前綴只有一個(gè)頂點(diǎn)有一個(gè)頂點(diǎn)1，因此，因此s=0, x0=1, x1:n-1是剩余的頂是剩余的頂點(diǎn)（即頂點(diǎn)點(diǎn)（即頂點(diǎn)2,3, n）。旅行路徑前綴）。旅行路徑前綴1 的開銷為的開銷為0 ，即即cc=0 ，并且，并且，rcost=MinOuti。bestc 給出了當(dāng)給出了當(dāng)前能找到的最少的耗費(fèi)值。初始時(shí)，由于沒有找到

52、前能找到的最少的耗費(fèi)值。初始時(shí)，由于沒有找到任何旅行路徑，因此任何旅行路徑，因此bestc的值被設(shè)為的值被設(shè)為NoEdge。2022年5月25日星期三第6章 分支限界分支限界法法46ntemplateT Traveling :BBTSP(int v ) / 旅行商問題的最小耗費(fèi)分枝定界算法旅行商問題的最小耗費(fèi)分枝定界算法/ 最小堆最多可容納最小堆最多可容納1000個(gè)活結(jié)點(diǎn)個(gè)活結(jié)點(diǎn)MinHeapMinHeapNode H(1000);T *MinOut = new T n+1;/ 計(jì)算計(jì)算MinOuti=離開頂點(diǎn)離開頂點(diǎn)i的最小出邊耗費(fèi)的最小出邊耗費(fèi)T MinSum=0; / 離開頂點(diǎn)離開頂點(diǎn)i

53、的最小出邊耗費(fèi)之和的最小出邊耗費(fèi)之和for (int i = 1; i = n; i+) T Min = NoEdge;2022年5月25日星期三第6章 分支限界分支限界法法47nfor (int j = 1; j = n; j+) if (aij != NoEdge & (aij Min | Min = NoEdge) Min = aij; if (Min = NoEdge) return NoEdge; / 無回路無回路 MinOuti = Min; MinSum += Min;/ 把把E-結(jié)點(diǎn)初始化為樹根結(jié)點(diǎn)初始化為樹根MinHeapNode E;E.x = new int n;for

54、(i = 0; i n; i+) E.xi = i + 1;2022年5月25日星期三第6章 分支限界分支限界法法48nE.s = 0; / 局部旅行路徑為局部旅行路徑為x 1 : 0 E.cc = 0; / 其耗費(fèi)為其耗費(fèi)為0E.rcost = MinSum;T bestc = NoEdge; / 目前沒有找到旅行路徑目前沒有找到旅行路徑n/ 搜索排列樹搜索排列樹while (E.s n - 1) / 不是葉子不是葉子if (E.s = n - 2) / 葉子的父結(jié)點(diǎn)葉子的父結(jié)點(diǎn)/ 通過添加兩條邊來完成旅行通過添加兩條邊來完成旅行/ 檢查新的旅行路徑是不是更好檢查新的旅行路徑是不是更好if

55、(aE.xn-2E.xn-1 != NoEdge & aE.xn-11 != NoEdge & (E.cc +aE.xn-2E.xn-1 + aE.xn-11 bestc | bestc = NoEdge) 2022年5月25日星期三第6章 分支限界分支限界法法49n/ 找到更優(yōu)的旅行路徑找到更優(yōu)的旅行路徑 bestc = E.cc + aE.xn-2E.xn-1 + aE.xn-11; E.cc = bestc; E.lcost = bestc; E.s+; H.Insert(E);else delete E.x;else / 擴(kuò)展子結(jié)點(diǎn)擴(kuò)展子結(jié)點(diǎn)for (int i = E.s + 1;

56、i n; i+) if (aE.xE.sE.xi != NoEdge) / 可行的兒子結(jié)點(diǎn)可行的兒子結(jié)點(diǎn)2022年5月25日星期三第6章 分支限界分支限界法法50nT cc = E.cc + aE.xE.sE.xi;T rcost = E.rcost - MinOutE.xE.s;T b = cc + rcost; /下限下限if (b bestc | bestc = NoEdge) / 子樹可能有更好的葉子子樹可能有更好的葉子/ 把根保存到最小堆中把根保存到最小堆中 MinHeapNode N; N.x = new int n; for (int j = 0; j n; j+) N.xj = E.xj; N.xE.s+1 = E.xi; N.xi = E.xE.s+1;2022年5月25日星期三第6章 分支限界分支限界法法51n N.cc = cc; N.s = E.s + 1; N.lcost = b; N.rcost = rcost; H . I n s