任何美好的事情都有結(jié)束的時(shí)候。現(xiàn)在我們學(xué)習(xí)的是本書的最后一章。幸運(yùn)的是，本章用到的大部分概念在前面各章中已作了介紹。類似于回溯法，分枝定界法在搜索解空間時(shí)，也經(jīng)常使用樹形結(jié)構(gòu)來(lái)組織解空間（常用的樹結(jié)構(gòu)是第1 6章所介紹的子集樹和排列樹）。然而與回溯法不同的是，回溯算法使用深度優(yōu)先方法搜索樹結(jié)構(gòu)，而分枝定界一般用寬度優(yōu)先或最小耗費(fèi)方法來(lái)搜索這些樹。本章與第1 6章所考察的應(yīng)用完全相同，因此，可以很容易比較回溯法與分枝定界法的異同。相對(duì)而言，分枝定界算法的解空間比回溯法大得多，因此當(dāng)內(nèi)存容量有限時(shí)，回溯法成功的可能性更大。
5.1 算法思想
分枝定界（branch and bound）是另一種系統(tǒng)地搜索解空間的方法，它與回溯法的主要區(qū)別在于對(duì)E-節(jié)點(diǎn)的擴(kuò)充方式。每個(gè)活節(jié)點(diǎn)有且僅有一次機(jī)會(huì)變成E-節(jié)點(diǎn)。當(dāng)一個(gè)節(jié)點(diǎn)變?yōu)镋-節(jié)點(diǎn)時(shí)，則生成從該節(jié)點(diǎn)移動(dòng)一步即可到達(dá)的所有新節(jié)點(diǎn)。在生成的節(jié)點(diǎn)中，拋棄那些不可能導(dǎo)出（最優(yōu)）可行解的節(jié)點(diǎn)，其余節(jié)點(diǎn)加入活節(jié)點(diǎn)表，然后從表中選擇一個(gè)節(jié)點(diǎn)作為下一個(gè)E-節(jié)點(diǎn)。從活節(jié)點(diǎn)表中取出所選擇的節(jié)點(diǎn)并進(jìn)行擴(kuò)充，直到找到解或活動(dòng)表為空，擴(kuò)充過(guò)程才結(jié)束。
有兩種常用的方法可用來(lái)選擇下一個(gè)E-節(jié)點(diǎn)（雖然也可能存在其他的方法）：
1) 先進(jìn)先出（F I F O） 即從活節(jié)點(diǎn)表中取出節(jié)點(diǎn)的順序與加入節(jié)點(diǎn)的順序相同，因此活節(jié)點(diǎn)表的性質(zhì)與隊(duì)列相同。
2) 最小耗費(fèi)或最大收益法在這種模式中，每個(gè)節(jié)點(diǎn)都有一個(gè)對(duì)應(yīng)的耗費(fèi)或收益。如果查找一個(gè)具有最小耗費(fèi)的解，則活節(jié)點(diǎn)表可用最小堆來(lái)建立，下一個(gè)E-節(jié)點(diǎn)就是具有最小耗費(fèi)的活節(jié)點(diǎn)；如果希望搜索一個(gè)具有最大收益的解，則可用最大堆來(lái)構(gòu)造活節(jié)點(diǎn)表，下一個(gè)E-節(jié)點(diǎn)是具有最大收益的活節(jié)點(diǎn)。
例5-1 [迷宮老鼠] 考察圖16-3a 給出的迷宮老鼠例子和圖1 6 - 1的解空間結(jié)構(gòu)。使用F I F O分枝定界，初始時(shí)取（1，1）作為E-節(jié)點(diǎn)且活動(dòng)隊(duì)列為空。迷宮的位置（ 1 , 1）被置為1，以免再次返回到這個(gè)位置。（1，1）被擴(kuò)充，它的相鄰節(jié)點(diǎn)（ 1，2）和（2，1）加入到隊(duì)列中（即活節(jié)點(diǎn)表）。為避免再次回到這兩個(gè)位置，將位置（ 1，2）和（2，1）置為1。此時(shí)迷宮如圖1 7 - 1 a所示，E-節(jié)點(diǎn)（1，1）被刪除。
節(jié)點(diǎn)（1，2）從隊(duì)列中移出并被擴(kuò)充。檢查它的三個(gè)相鄰節(jié)點(diǎn)（見圖1 6 - 1的解空間），只有（1，3）是可行的移動(dòng)（剩余的兩個(gè)節(jié)點(diǎn)是障礙節(jié)點(diǎn)），將其加入隊(duì)列，并把相應(yīng)的迷宮位置置為1，所得到的迷宮狀態(tài)如圖17-1b 所示。節(jié)點(diǎn)（1，2）被刪除，而下一個(gè)E-節(jié)點(diǎn)（2，1）將會(huì)被取出，當(dāng)此節(jié)點(diǎn)被展開時(shí)，節(jié)點(diǎn)（3，1）被加入隊(duì)列中，節(jié)點(diǎn)（3，1）被置為1，節(jié)點(diǎn)（2，1）被刪除，所得到的迷宮如圖17-1c 所示。此時(shí)隊(duì)列中包含（1，3）和（3，1）兩個(gè)節(jié)點(diǎn)。隨后節(jié)點(diǎn)（1，3）變成下一個(gè)E-節(jié)點(diǎn)，由于此節(jié)點(diǎn)不能到達(dá)任何新的節(jié)點(diǎn)，所以此節(jié)點(diǎn)即被刪除，節(jié)點(diǎn)（3，1）成為新的E-節(jié)點(diǎn)，將隊(duì)列清空。節(jié)點(diǎn)（ 3，1）展開，（3，2）被加入隊(duì)列中，而（3，1）被刪除。（3，2）變?yōu)樾碌腅-節(jié)點(diǎn)，展開此節(jié)點(diǎn)后，到達(dá)節(jié)點(diǎn)（3，3），即迷宮的出口。
使用F I F O搜索，總能找出從迷宮入口到出口的最短路徑。需要注意的是：利用回溯法找到的路徑卻不一定是最短路徑。有趣的是，程序6 - 11已經(jīng)給出了利用F I F O分枝定界搜索從迷宮的（1，1）位置到（n，n） 位置的最短路徑的代碼。
例5-2 [0/1背包問(wèn)題] 下面比較分別利用F I F O分枝定界和最大收益分枝定界方法來(lái)解決如下背包問(wèn)題：n=3, w=[20,15,15], p=[40,25,25], c= 3 0。F I F O分枝定界利用一個(gè)隊(duì)列來(lái)記錄活節(jié)點(diǎn)，節(jié)點(diǎn)將按照F I F O順序從隊(duì)列中取出；而最大收益分枝定界使用一個(gè)最大堆，其中的E-節(jié)點(diǎn)按照每個(gè)活節(jié)點(diǎn)收益值的降序，或是按照活節(jié)點(diǎn)任意子樹的葉節(jié)點(diǎn)所能獲得的收益估計(jì)值的降序從隊(duì)列中取出。本例所使用的背包問(wèn)題與例1 6 . 2相同，并且有相同的解空間樹。
使用F I F O分枝定界法搜索，初始時(shí)以根節(jié)點(diǎn)A作為E-節(jié)點(diǎn)，此時(shí)活節(jié)點(diǎn)隊(duì)列為空。當(dāng)節(jié)點(diǎn)
A展開時(shí)，生成了節(jié)點(diǎn)B和C，由于這兩個(gè)節(jié)點(diǎn)都是可行的，因此都被加入活節(jié)點(diǎn)隊(duì)列中，節(jié)點(diǎn)A被刪除。下一個(gè)E-節(jié)點(diǎn)是B，展開它并產(chǎn)生了節(jié)點(diǎn)D和E，D是不可行的，被刪除，而E被加入隊(duì)列中。下一步節(jié)點(diǎn)C成為E-節(jié)點(diǎn)，它展開后生成節(jié)點(diǎn)F和G，兩者都是可行節(jié)點(diǎn)，加入隊(duì)列中。下一個(gè)E-節(jié)點(diǎn)E生成節(jié)點(diǎn)J和K，J不可行而被刪除，K是一個(gè)可行的葉節(jié)點(diǎn)，并產(chǎn)生一個(gè)到目前為止可行的解，它的收益值為4 0。
下一個(gè)E-節(jié)點(diǎn)是F，它產(chǎn)生兩個(gè)孩子L、M，L代表一個(gè)可行的解且其收益值為5 0，M代表另一個(gè)收益值為1 5的可行解。G是最后一個(gè)E-節(jié)點(diǎn)，它的孩子N和O都是可行的。由于活節(jié)點(diǎn)隊(duì)列變?yōu)榭眨虼怂阉鬟^(guò)程終止，最佳解的收益值為5 0。
可以看到，工作在解空間樹上的F I F O分枝定界方法非常象從根節(jié)點(diǎn)出發(fā)的寬度優(yōu)先搜索。它們的主要區(qū)別是在F I F O分枝定界中不可行的節(jié)點(diǎn)不會(huì)被搜索。最大收益分枝定界算法以解空間樹中的節(jié)點(diǎn)A作為初始節(jié)點(diǎn)。展開初始節(jié)點(diǎn)得到節(jié)點(diǎn)B和C，兩者都是可行的并被插入堆中，節(jié)點(diǎn)B獲得的收益值是4 0（設(shè)x1 = 1），而節(jié)點(diǎn)C得到的收益值為0。A被刪除，B成為下一個(gè)E-節(jié)點(diǎn)，因?yàn)樗氖找嬷当菴的大。當(dāng)展開B時(shí)得到了節(jié)點(diǎn)D和E，D是不可行的而被刪除，E加入堆中。由于E具有收益值4 0，而C為0，因?yàn)镋成為下一個(gè)E-節(jié)點(diǎn)。
展開E時(shí)生成節(jié)點(diǎn)J和K，J不可行而被刪除，K是一個(gè)可行的解，因此K為作為目前能找到的最優(yōu)解而記錄下來(lái)，然后K被刪除。由于只剩下一個(gè)活節(jié)點(diǎn)C在堆中，因此C作為E-節(jié)點(diǎn)被展開，生成F、G兩個(gè)節(jié)點(diǎn)插入堆中。F的收益值為2 5，因此成為下一個(gè)E-節(jié)點(diǎn)，展開后得到節(jié)點(diǎn)L和M，但L、M都被刪除，因?yàn)樗鼈兪侨~節(jié)點(diǎn)，同時(shí)L所對(duì)應(yīng)的解被作為當(dāng)前最優(yōu)解記錄下來(lái)。最終，G成為E-節(jié)點(diǎn)，生成的節(jié)點(diǎn)為N和O，兩者都是葉節(jié)點(diǎn)而被刪除，兩者所對(duì)應(yīng)的解都不比當(dāng)前的最優(yōu)解更好，因此最優(yōu)解保持不變。此時(shí)堆變?yōu)榭眨瑳]有下一個(gè)E-節(jié)點(diǎn)產(chǎn)生，搜索過(guò)程終止。終止于J的搜索即為最優(yōu)解。
猶如在回溯方法中一樣，可利用一個(gè)定界函數(shù)來(lái)加速最優(yōu)解的搜索過(guò)程。定界函數(shù)為最大收益設(shè)置了一個(gè)上限，通過(guò)展開一個(gè)特殊的節(jié)點(diǎn)可能獲得這個(gè)最大收益。如果一個(gè)節(jié)點(diǎn)的定界函數(shù)值不大于目前最優(yōu)解的收益值，則此節(jié)點(diǎn)會(huì)被刪除而不作展開，更進(jìn)一步，在最大收益分枝定界方法中，可以使節(jié)點(diǎn)按照它們收益的定界函數(shù)值的非升序從堆中取出，而不是按照節(jié)點(diǎn)的實(shí)際收益值來(lái)取出。這種策略從可能到達(dá)一個(gè)好的葉節(jié)點(diǎn)的活節(jié)點(diǎn)出發(fā)，而不是從目前具有較大收益值的節(jié)點(diǎn)出發(fā)。
例5-3 [旅行商問(wèn)題] 對(duì)于圖1 6 - 4的四城市旅行商問(wèn)題，其對(duì)應(yīng)的解空間為圖1 6 - 5所示的排列樹。F I F O分枝定界使用節(jié)點(diǎn)B作為初始的E-節(jié)點(diǎn)，活節(jié)點(diǎn)隊(duì)列初始為空。當(dāng)B展開時(shí)，生成節(jié)點(diǎn)C、D和E。由于從頂點(diǎn)1到頂點(diǎn)2，3，4都有邊相連，所以C、D、E三個(gè)節(jié)點(diǎn)都是可行的并加入隊(duì)列中。當(dāng)前的E-節(jié)點(diǎn)B被刪除，新的E-節(jié)點(diǎn)是隊(duì)列中的第一個(gè)節(jié)點(diǎn)，即節(jié)點(diǎn)C。因?yàn)樵趫D1 6 - 4中存在從頂點(diǎn)2到頂點(diǎn)3和4的邊，因此展開C，生成節(jié)點(diǎn)F和G，兩者都被加入隊(duì)列。下一步，D成為E-節(jié)點(diǎn)，接著又是E，到目前為止活節(jié)點(diǎn)隊(duì)列中包含節(jié)點(diǎn)F到K。下一個(gè)E-節(jié)點(diǎn)是F，展開它得到了葉節(jié)點(diǎn)L。至此找到了一個(gè)旅行路徑，它的開銷是5 9。展開下一個(gè)E-節(jié)點(diǎn)G，得到葉節(jié)點(diǎn)M，它對(duì)應(yīng)于一個(gè)開銷為6 6的旅行路徑。接著H成為E-節(jié)點(diǎn)，從而找到葉節(jié)點(diǎn)N，對(duì)應(yīng)開銷為2 5的旅行路徑。下一個(gè)E-節(jié)點(diǎn)是I，它對(duì)應(yīng)的部分旅行1 - 3 - 4的開銷已經(jīng)為2 6，超過(guò)了目前最優(yōu)的旅行路徑，因此， I不會(huì)被展開。最后，節(jié)點(diǎn)J，K成為E-節(jié)點(diǎn)并被展開。經(jīng)過(guò)這些展開過(guò)程，隊(duì)列變?yōu)榭眨惴ńY(jié)束。找到的最優(yōu)方案是節(jié)點(diǎn)N所對(duì)應(yīng)的旅行路徑。
如果不使用F I F O方法，還可以使用最小耗費(fèi)方法來(lái)搜索解空間樹，即用一個(gè)最小堆來(lái)存儲(chǔ)活節(jié)點(diǎn)。這種方法同樣從節(jié)點(diǎn)B開始搜索，并使用一個(gè)空的活節(jié)點(diǎn)列表。當(dāng)節(jié)點(diǎn)B展開時(shí)，生成節(jié)點(diǎn)C、D和E并將它們加入最小堆中。在最小堆的節(jié)點(diǎn)中， E具有最小耗費(fèi)（因?yàn)? - 4的局部旅行的耗費(fèi)是4），因此成為E-節(jié)點(diǎn)。展開E生成節(jié)點(diǎn)J和K并將它們加入最小堆，這兩個(gè)節(jié)點(diǎn)的耗費(fèi)分別為1 4和2 4。此時(shí)，在所有最小堆的節(jié)點(diǎn)中，D具有最小耗費(fèi)，因而成為E-節(jié)點(diǎn)，并生成節(jié)點(diǎn)H和I。至此，最小堆中包含節(jié)點(diǎn)C、H、I、J和K，H具有最小耗費(fèi)，因此H成為下一個(gè)E-節(jié)點(diǎn)。展開節(jié)點(diǎn)E，得到一個(gè)完整的旅行路徑1 - 3 - 2 - 4 - 1，它的開銷是2 5。節(jié)點(diǎn)J是下一個(gè)E-節(jié)點(diǎn)，展開它得到節(jié)點(diǎn)P，它對(duì)應(yīng)于一個(gè)耗費(fèi)為2 5的旅行路徑。節(jié)點(diǎn)K和I是下兩個(gè)E-節(jié)點(diǎn)。由于I的開銷超過(guò)了當(dāng)前最優(yōu)的旅行路徑，因此搜索結(jié)束，而剩下的所有活節(jié)點(diǎn)都不能使我們找到更優(yōu)的解。
對(duì)于例5 - 2的背包問(wèn)題，可以使用一個(gè)定界函數(shù)來(lái)減少生成和展開的節(jié)點(diǎn)數(shù)量。這種函數(shù)將確定旅行的最小耗費(fèi)的下限，這個(gè)下限可通過(guò)展開某個(gè)特定的節(jié)點(diǎn)而得到。如果一個(gè)節(jié)點(diǎn)的定界函數(shù)值不能比當(dāng)前的最優(yōu)旅行更小，則它將被刪除而不被展開。另外，對(duì)于最小耗費(fèi)分枝定界，節(jié)點(diǎn)按照它在最小堆中的非降序取出。
在以上幾個(gè)例子中，可以利用定界函數(shù)來(lái)降低所產(chǎn)生的樹型解空間的節(jié)點(diǎn)數(shù)目。當(dāng)設(shè)計(jì)定界函數(shù)時(shí)，必須記住主要目的是利用最少的時(shí)間，在內(nèi)存允許的范圍內(nèi)去解決問(wèn)題。而通過(guò)產(chǎn)生具有最少節(jié)點(diǎn)的樹來(lái)解決問(wèn)題并不是根本的目標(biāo)。因此，我們需要的是一個(gè)能夠有效地減少計(jì)算時(shí)間并因此而使產(chǎn)生的節(jié)點(diǎn)數(shù)目也減少的定界函數(shù)。
回溯法比分枝定界在占用內(nèi)存方面具有優(yōu)勢(shì)。回溯法占用的內(nèi)存是O（解空間的最大路徑長(zhǎng)度），而分枝定界所占用的內(nèi)存為O（解空間大小）。對(duì)于一個(gè)子集空間，回溯法需要(n)的內(nèi)存空間，而分枝定界則需要O ( 2n ) 的空間。對(duì)于排列空間，回溯需要(n) 的內(nèi)存空間，分枝定界需要O (n!) 的空間。雖然最大收益（或最小耗費(fèi)）分枝定界在直覺上要好于回溯法，并且在許多情況下可能會(huì)比回溯法檢查更少的節(jié)點(diǎn)，但在實(shí)際應(yīng)用中，它可能會(huì)在回溯法超出允許的時(shí)間限制之前就超出了內(nèi)存的限制。
練習(xí)
1. 假定在一個(gè)L I F O分枝定界搜索中，活節(jié)點(diǎn)列表的行為與堆棧相同，請(qǐng)使用這種方法來(lái)解決例5 - 2的背包問(wèn)題。L I F O分枝定界與回溯有何區(qū)別？
2. 對(duì)于如下0 / 1背包問(wèn)題：n=4, p=[4,3,2,1], w=[1,2,3,4], c =6。
1) 畫出有四個(gè)對(duì)象的背包問(wèn)題的解空間樹。
2) 像例1 7 - 2那樣，描述用F I F O分枝定界法解決上述問(wèn)題的過(guò)程。
3) 使用程序1 6 - 6的B o u n d函數(shù)來(lái)計(jì)算子樹上任一葉節(jié)點(diǎn)可能獲得的最大收益值，并根據(jù)每一步所能得到的最優(yōu)解對(duì)應(yīng)的定界函數(shù)值來(lái)判斷是否將節(jié)點(diǎn)加入活節(jié)點(diǎn)列表中。解空間中哪些節(jié)點(diǎn)是使用以上機(jī)制的F I F O分枝定界方法產(chǎn)生的？
4) 像例1 7 - 2那樣，描述用最大收益分枝定界法解決上述問(wèn)題的過(guò)程。
5) 在最大收益分枝定界中，若使用3）中的定界函數(shù)，將產(chǎn)生解空間樹中的哪些節(jié)點(diǎn)？
5.2 應(yīng)用
5.2.1 貨箱裝船
1. FIFO分枝定界
4 . 2 . 1節(jié)的貨箱裝船問(wèn)題主要是尋找第一條船的最大裝載方案。這個(gè)問(wèn)題是一個(gè)子集選擇
問(wèn)題，它的解空間被組織成一個(gè)子集樹。對(duì)程序1 6 - 1進(jìn)行改造，即得到程序1 7 - 1中的F I F O分枝定界代碼。程序1 7 - 1只是尋找最大裝載的重量。
程序17-1 貨箱裝船問(wèn)題的F I F O分枝定界算法
template<class T>
void AddLiveNode(LinkedQueue<T> &Q, T wt,
T& bestw, int i, int n)
{// 如果不是葉節(jié)點(diǎn)，則將節(jié)點(diǎn)權(quán)值w t加入隊(duì)列Q
if (i == n) {// 葉子
if (wt > bestw) bestw = wt;}
else Q.Add(wt); // 不是葉子
}
template<class T>
T MaxLoading(T w[], T c, int n)
{// 返回最優(yōu)裝載值
// 使用F I F O分枝定界算法
// 為層次1 初始化
LinkedQueue<T> Q; // 活節(jié)點(diǎn)隊(duì)列
Q.Add(-1); //標(biāo)記本層的尾部
int i = 1; // E-節(jié)點(diǎn)的層
T Ew = 0, // E-節(jié)點(diǎn)的權(quán)值
bestw = 0; // 目前的最優(yōu)值
// 搜索子集空間樹
while (true) {
// 檢查E-節(jié)點(diǎn)的左孩子
if (Ew + w[i] <= c) // x[i] = 1
AddLiveNode(Q, Ew + w[i], bestw, i, n);
// 右孩子總是可行的
AddLiveNode(Q, Ew, bestw, i, n); // x[i] = 0
Q.Delete(Ew); // 取下一個(gè)E-節(jié)點(diǎn)
if (Ew == -1) { // 到達(dá)層的尾部
if (Q.IsEmpty()) return bestw;
Q.Add(-1); //添加尾部標(biāo)記
Q.Delete(Ew); // 取下一個(gè)E-節(jié)點(diǎn)
i++;} // Ew的層
}
}
其中函數(shù)MaxLoading 在解空間樹中進(jìn)行分枝定界搜索。鏈表隊(duì)列Q用于保存活節(jié)點(diǎn)，其中記錄著各活節(jié)點(diǎn)對(duì)應(yīng)的權(quán)值。隊(duì)列還記錄了權(quán)值- 1，以標(biāo)識(shí)每一層的活節(jié)點(diǎn)的結(jié)尾。函數(shù)AddLiveNode 用于增加節(jié)點(diǎn)（即把節(jié)點(diǎn)對(duì)應(yīng)的權(quán)值加入活節(jié)點(diǎn)隊(duì)列），該函數(shù)首先檢驗(yàn)i（當(dāng)前E-節(jié)點(diǎn)在解空間樹中的層）是否等于n，如果相等，則已到達(dá)了葉節(jié)點(diǎn)。葉節(jié)點(diǎn)不被加入隊(duì)列中，因?yàn)樗鼈儾槐徽归_。搜索中所到達(dá)的每個(gè)葉節(jié)點(diǎn)都對(duì)應(yīng)著一個(gè)可行的解，而每個(gè)解都會(huì)與目前的最優(yōu)解來(lái)比較，以確定最優(yōu)解。如果i＜n，則節(jié)點(diǎn)i 就會(huì)被加入隊(duì)列中。
M a x L o a d i n g函數(shù)首先初始化i = 1（因?yàn)楫?dāng)前E-節(jié)點(diǎn)是根節(jié)點(diǎn)），b e s t w = 0（目前最優(yōu)解的對(duì)應(yīng)值），此時(shí)，活節(jié)點(diǎn)隊(duì)列為空。下一步， A - 1被加入隊(duì)列以說(shuō)明正處在第一層的末尾。當(dāng)前E-節(jié)點(diǎn)對(duì)應(yīng)的權(quán)值為Ew。在while 循環(huán)中，首先檢查節(jié)點(diǎn)的左孩子是否可行。如果可行，則調(diào)用A d d L i v e N o d e，然后將右孩子加入隊(duì)列（此節(jié)點(diǎn)必定是可行的），注意到A d d l i v e N o d e可能會(huì)失敗，因?yàn)榭赡軟]有足夠的內(nèi)存來(lái)給隊(duì)列增加節(jié)點(diǎn)。A d d L i v e N o d e并沒有去捕獲Q . A d d中的N o M e m異常，這項(xiàng)工作留給用戶完成。
如果E-節(jié)點(diǎn)的兩個(gè)孩子都已經(jīng)被生成，則刪除該E-節(jié)點(diǎn)。從隊(duì)列中取出下一個(gè)E-節(jié)點(diǎn)，此時(shí)隊(duì)列必不為空，因?yàn)殛?duì)列中至少含有本層末尾的標(biāo)識(shí)- 1。如果到達(dá)了某一層的結(jié)尾，則從下一層尋找活節(jié)點(diǎn)，當(dāng)且僅當(dāng)隊(duì)列不為空時(shí)這些節(jié)點(diǎn)存在。當(dāng)下一層存在活節(jié)點(diǎn)時(shí)，向隊(duì)列中加入下一層的結(jié)尾標(biāo)志并開始處理下一層的活節(jié)點(diǎn)。
M a x L o a d i n g函數(shù)的時(shí)間和空間復(fù)雜性都是O ( 2n )。
2. 改進(jìn)
我們可以嘗試使用程序1 6 - 2的優(yōu)化方法改進(jìn)上述問(wèn)題的求解過(guò)程。在程序1 6 - 2中，只有當(dāng)右孩子對(duì)應(yīng)的重量加上剩余貨箱的重量超出b e s t w時(shí)，才選擇右孩子。而在程序1 7 - 1中，在i變?yōu)閚之前，b e s t w的值一直保持不變，因此在i等于n之前對(duì)右孩子的測(cè)試總能成功，因?yàn)閎 e s t w = 0且r > 0。當(dāng)i等于n時(shí)，不會(huì)再有節(jié)點(diǎn)加入隊(duì)列中，因此這時(shí)對(duì)右孩子的測(cè)試不再有效。
如想要使右孩子的測(cè)試仍然有效，應(yīng)當(dāng)提早改變b e s t w的值。我們知道，最優(yōu)裝載的重量是子集樹中可行節(jié)點(diǎn)的重量的最大值。由于僅在向左子樹移動(dòng)時(shí)這些重量才會(huì)增大，因此可以在每次進(jìn)行這種移動(dòng)時(shí)改變b e s t w的值。根據(jù)以上思想，我們?cè)O(shè)計(jì)了程序1 7 - 2。當(dāng)活節(jié)點(diǎn)加入隊(duì)列時(shí)，w t不會(huì)超過(guò)b e s t w，故b e s t w不用更新。因此用一條直接插入M a x L o a d i n g的簡(jiǎn)單語(yǔ)句取代了函數(shù)A d d L i v e N o d e。
程序17-2 對(duì)程序1 7 - 1改進(jìn)之后
template<class T>
T MaxLoading(T w[], T c, int n)
{// 返回最優(yōu)裝載值
// 使用F I F O分枝定界算法
// 為層1初始化
LinkedQueue<T> Q; // 活節(jié)點(diǎn)隊(duì)列
Q . A d d ( - 1 ) ; / /標(biāo)記本層的尾部
int i = 1; // E-節(jié)點(diǎn)的層
T Ew = 0, // E-節(jié)點(diǎn)的重量
bestw = 0; // 目前的最優(yōu)值
r = 0; // E-節(jié)點(diǎn)中余下的重量
for (int j = 2; j <= n; j++)
r += w[i];
// 搜索子集空間樹
while (true) {
// 檢查E-節(jié)點(diǎn)的左孩子
T wt = Ew + w[i]; // 左孩子的權(quán)值
if (wt <= c) { // 可行的左孩子
if (wt > bestw) bestw = wt;
// 若不是葉子，則添加到隊(duì)列中
if (i < n) Q.Add(wt);}
// 檢查右孩子
if (Ew + r > bestw && i < n)
Q.Add(Ew); // 可以有一個(gè)更好的葉子
Q.Delete(Ew); // 取下一個(gè)E-節(jié)點(diǎn)
if (Ew == -1) { // 到達(dá)層的尾部
if (Q.IsEmpty()) return bestw;
Q.Add(-1); //添加尾部標(biāo)記
Q.Delete(Ew); // 取下一個(gè)E-節(jié)點(diǎn)
i++; // E-節(jié)點(diǎn)的層
r -= w[i];} // E-節(jié)點(diǎn)中余下的重量
}
}
3. 尋找最優(yōu)子集
為了找到最優(yōu)子集，需要記錄從每個(gè)活節(jié)點(diǎn)到達(dá)根的路徑，因此在找到最優(yōu)裝載所對(duì)應(yīng)的葉節(jié)點(diǎn)之后，就可以利用所記錄的路徑返回到根節(jié)點(diǎn)來(lái)設(shè)置x的值。活節(jié)點(diǎn)隊(duì)列中元素的類型是Q N o d e (見程序1 7 - 3 )。這里，當(dāng)且僅當(dāng)節(jié)點(diǎn)是它的父節(jié)點(diǎn)的左孩子時(shí)， L C h i l d為t r u e。
程序17-3 類Q N o d e
template<class T>
class QNode {
p r i v a t e :
QNode *parent; // 父節(jié)點(diǎn)指針
bool LChild; // 當(dāng)且僅當(dāng)是父節(jié)點(diǎn)的左孩子時(shí)，取值為t r u e
T weight; // 由到達(dá)本節(jié)點(diǎn)的路徑所定義的部分解的值
} ;
程序1 7 - 4是新的分枝定界方法的代碼。為了避免使用大量的參數(shù)來(lái)調(diào)用A d d L i v e N o d e，可以把該函數(shù)定義為一個(gè)內(nèi)部函數(shù)。使用內(nèi)部函數(shù)會(huì)使空間需求稍有增加。此外，還可以把A d d L i v e N o d e和M a x L o a d i n g定義成類成員函數(shù)，這樣，它們就可以共享諸如Q , i , n , b e s t w, E , b e s t E和bestw 等類成員。
程序1 7 - 4并未刪除類型為Q N o d e的節(jié)點(diǎn)。為了刪除這些節(jié)點(diǎn)，可以保存由A d d L i v e N o d e創(chuàng)建的所有節(jié)點(diǎn)的指針，以便在程序結(jié)束時(shí)刪除這些節(jié)點(diǎn)。
程序17-4 計(jì)算最優(yōu)子集的分枝定界算法
template<class T>
void AddLiveNode(LinkedQueue<QNode<T>*> &Q, T wt, int i, int n, T bestw, QNode<T> *E,
QNode<T> *&bestE, int bestx[], bool ch)
{// 如果不是葉節(jié)點(diǎn)，則向隊(duì)列Q中添加一個(gè)i 層、重量為w t的活節(jié)點(diǎn)
// 新節(jié)點(diǎn)是E的一個(gè)孩子。當(dāng)且僅當(dāng)新節(jié)點(diǎn)是左孩子時(shí)， c h為t r u e。
// 若是葉子，則c h取值為b e s t x [ n ]
if (i == n) {// 葉子
if (wt == bestw) {
// 目前的最優(yōu)解
bestE = E;
bestx[n] = ch;}
r e t u r n ; }
// 不是葉子, 添加到隊(duì)列中
QNode<T> *b;
b = new QNode<T>;
b->weight = wt;
b->parent = E;
b->LChild = ch;
Q . A d d ( b ) ;
}
template<class T>
T MaxLoading(T w[], T c, int n, int bestx[])
{// 返回最優(yōu)裝載值，并在b e s t x中返回最優(yōu)裝載
// 使用F I F O分枝定界算法
// 初始化層1
LinkedQueue<QNode<T>*> Q; // 活節(jié)點(diǎn)隊(duì)列
Q . A d d ( 0 ) ; // 0 代表本層的尾部
int i = 1; // E-節(jié)點(diǎn)的層
T Ew = 0, // E-節(jié)點(diǎn)的重量
bestw = 0; // 迄今得到的最優(yōu)值
r = 0; // E-節(jié)點(diǎn)中余下的重量
for (int j = 2; j <= n; j++)
r += w[i];
QNode<T> *E = 0, // 當(dāng)前的E-節(jié)點(diǎn)
* b e s t E ; // 目前最優(yōu)的E-節(jié)點(diǎn)
// 搜索子集空間樹
while (true) {
// 檢查E-節(jié)點(diǎn)的左孩子
T wt = Ew + w[i];
if (wt <= c) {// 可行的左孩子
if (wt > bestw) bestw = wt;
AddLiveNode(Q, wt, i, n, bestw, E, bestE, bestx, true);}
// 檢查右孩子
if (Ew + r > bestw) AddLiveNode(Q, Ew, i, n, bestw, E, bestE, bestx, false);
Q . D e l e t e ( E ) ; // 下一個(gè)E-節(jié)點(diǎn)
if (!E) { // 層的尾部
if (Q.IsEmpty()) break;
Q . A d d ( 0 ) ; // 層尾指針
Q . D e l e t e ( E ) ; // 下一個(gè)E-節(jié)點(diǎn)
i + + ; // E-節(jié)點(diǎn)的層次
r -= w[i];} // E-節(jié)點(diǎn)中余下的重量
Ew = E-> w e i g h t ; // 新的E-節(jié)點(diǎn)的重量
}
// 沿著從b e s t E到根的路徑構(gòu)造x[ ] ， x [ n ]由A d d L i v e N o d e來(lái)設(shè)置
for (j = n - 1; j > 0; j--) {
bestx[j] = bestE->LChild; // 從b o o l轉(zhuǎn)換為i n t
bestE = bestE-> p a r e n t ;
}
return bestw;
}
4. 最大收益分枝定界
在對(duì)子集樹進(jìn)行最大收益分枝定界搜索時(shí)，活節(jié)點(diǎn)列表是一個(gè)最大優(yōu)先級(jí)隊(duì)列，其中每個(gè)活節(jié)點(diǎn)x都有一個(gè)相應(yīng)的重量上限（最大收益）。這個(gè)重量上限是節(jié)點(diǎn)x 相應(yīng)的重量加上剩余貨箱的總重量，所有的活節(jié)點(diǎn)按其重量上限的遞減順序變?yōu)镋-節(jié)點(diǎn)。需要注意的是，如果節(jié)點(diǎn)x的重量上限是x . u w e i g h t，則在子樹中不可能存在重量超過(guò)x.uweight 的節(jié)點(diǎn)。另外，當(dāng)葉節(jié)點(diǎn)對(duì)應(yīng)的重量等于它的重量上限時(shí)，可以得出結(jié)論：在最大收益分枝定界算法中，當(dāng)某個(gè)葉節(jié)點(diǎn)成為E-節(jié)點(diǎn)并且其他任何活節(jié)點(diǎn)都不會(huì)幫助我們找到具有更大重量的葉節(jié)點(diǎn)時(shí)，最優(yōu)裝載的搜索終止。
上述策略可以用兩種方法來(lái)實(shí)現(xiàn)。在第一種方法中，最大優(yōu)先級(jí)隊(duì)列中的活節(jié)點(diǎn)都是互相獨(dú)立的，因此每個(gè)活節(jié)點(diǎn)內(nèi)部必須記錄從子集樹的根到此節(jié)點(diǎn)的路徑。一旦找到了最優(yōu)裝載所對(duì)應(yīng)的葉節(jié)點(diǎn)，就利用這些路徑信息來(lái)計(jì)算x 值。在第二種方法中，除了把節(jié)點(diǎn)加入最大優(yōu)先隊(duì)列之外，節(jié)點(diǎn)還必須放在另一個(gè)獨(dú)立的樹結(jié)構(gòu)中，這個(gè)樹結(jié)構(gòu)用來(lái)表示所生成的子集樹的一部分。當(dāng)找到最大裝載之后，就可以沿著路徑從葉節(jié)點(diǎn)一步一步返回到根，從而計(jì)算出x 值。
最大優(yōu)先隊(duì)列可用HeapNode 類型的最大堆來(lái)表示（見程序1 7 - 5）。uweight 是活節(jié)點(diǎn)的重量上限，level 是活節(jié)點(diǎn)所在子集樹的層， ptr 是指向活節(jié)點(diǎn)在子集樹中位置的指針。子集樹中節(jié)點(diǎn)的類型是b b n o d e（見程序1 7 - 5）。節(jié)點(diǎn)按u w e i g h t值從最大堆中取出。
程序17-5 bbnode 和HeapNode 類
class bbnode {
p r i v a t e :
bbnode *parent; // 父節(jié)點(diǎn)指針
bool LChild; // 當(dāng)且僅當(dāng)是父節(jié)點(diǎn)的左孩子時(shí)，取值為t r u e
} ;
template<class T>
class HeapNode {
p u b l i c :
operator T () const {return uweight;}
p r i v a t e :
bbnode *ptr; // 活節(jié)點(diǎn)指針
T uweight; // 活節(jié)點(diǎn)的重量上限
int level; // 活節(jié)點(diǎn)所在層
} ;
程序1 7 - 6中的函數(shù)A d d L i v e N o d e用于把b b n o d e類型的活節(jié)點(diǎn)加到子樹中，并把H e a p N o d e類型的活節(jié)點(diǎn)插入最大堆。A d d L i v e N o d e必須被定義為b b n o d e和H e a p N o d e的友元。
程序17-6
template<class T>
void AddLiveNode(MaxHeap<HeapNode<T> > &H, bbnode *E, T wt, bool ch, int lev)
{// 向最大堆H中增添一個(gè)層為l e v上限重量為w t的活節(jié)點(diǎn)
// 新節(jié)點(diǎn)是E的一個(gè)孩子
// 當(dāng)且僅當(dāng)新節(jié)點(diǎn)是左孩子ch 為t r u e
bbnode *b = new bbnode;
b->parent = E;
b->LChild = ch;
HeapNode<T> N;
N.uweight = wt;
N.level = lev;
N.ptr = b;
H . I n s e r t ( N ) ;
}
template<class T>
T MaxLoading(T w[], T c, int n, int bestx[])
{// 返回最優(yōu)裝載值，最優(yōu)裝載方案保存于b e s t x
// 使用最大收益分枝定界算法
// 定義一個(gè)最多有1 0 0 0個(gè)活節(jié)點(diǎn)的最大堆
MaxHeap<HeapNode<T> > H(1000);
// 第一剩余重量的數(shù)組
// r[j] 為w [ j + 1 : n ]的重量之和
T *r = new T [n+1];
r[n] = 0;
for (int j = n-1; j > 0; j--)
r[j] = r[j+1] + w[j+1];
// 初始化層1
int i = 1; // E-節(jié)點(diǎn)的層
bbnode *E = 0; // 當(dāng)前E-節(jié)點(diǎn)
T Ew = 0; // E-節(jié)點(diǎn)的重量
// 搜索子集空間樹
while (i != n+1) {// 不在葉子上
// 檢查E-節(jié)點(diǎn)的孩子
if (Ew + w[i] <= c) {// 可行的左孩子
AddLiveNode(H, E, Ew+w[i]+r[i], true, i+1);}
// 右孩子
AddLiveNode(H, E, Ew+r[i], false, i+1);
// 取下一個(gè)E-節(jié)點(diǎn)
HeapNode<T> N;
H.DeleteMax(N); // 不能為空
i = N.level;
E = N.ptr;
Ew = N.uweight - r[i-1];
}
// 沿著從E-節(jié)點(diǎn)E到根的路徑構(gòu)造b e s t x [ ]
for (int j = n; j > 0; j--) {
bestx[j] = E->LChild; // 從b o o l轉(zhuǎn)換為i n t
E = E-> p a r e n t ;
}
return Ew;
}
函數(shù)M a x L o a d i n g（見程序1 7 - 6）首先定義了一個(gè)容量為1 0 0 0的最大堆，因此，可以用它來(lái)解決優(yōu)先隊(duì)列中活節(jié)點(diǎn)數(shù)在任何時(shí)候都不超過(guò)1 0 0 0的裝箱問(wèn)題。對(duì)于更大型的問(wèn)題，需要一個(gè)容量更大的最大堆。接著，函數(shù)M a x L o a d i n g初始化剩余重量數(shù)組r。第i + 1層的節(jié)點(diǎn)（即x [ 1 : i ]的值都已確定）對(duì)應(yīng)的剩余容器總重量可以用如下公式求出：
r [i]=n ?j=i + 1w[ j ]。
變量E指向子集樹中的當(dāng)前E-節(jié)點(diǎn)，Ew 是該節(jié)點(diǎn)對(duì)應(yīng)的重量， i 是它所在的層。初始時(shí)，根節(jié)點(diǎn)是E-節(jié)點(diǎn)，因此取i=1, Ew=0。由于沒有明確地存儲(chǔ)根節(jié)點(diǎn)，因此E的初始值取為0。while 循環(huán)用于產(chǎn)生當(dāng)前E-節(jié)點(diǎn)的左、右孩子。如果左孩子是可行的（即它的重量沒有超出容量），則將它加入到子集樹中并作為一個(gè)第i + 1層節(jié)點(diǎn)加入最大堆中。一個(gè)可行的節(jié)點(diǎn)的右孩子也被認(rèn)為是可行的，它總被加入子樹及最大堆中。在完成添加操作后，接著從最大堆中取出下一個(gè)E-節(jié)點(diǎn)。如果沒有下一個(gè)E-節(jié)點(diǎn)，則不存在可行的解。如果下一個(gè)E-節(jié)點(diǎn)是葉節(jié)點(diǎn)（即是一個(gè)層為n + 1的節(jié)點(diǎn)），則它代表著一個(gè)最優(yōu)的裝載，可以沿著從葉到根的路徑來(lái)確定裝載方案。
5. 說(shuō)明
1) 使用最大堆來(lái)表示活節(jié)點(diǎn)的最大優(yōu)先隊(duì)列時(shí)，需要預(yù)測(cè)這個(gè)隊(duì)列的最大長(zhǎng)度（程序1 7 - 6
中是1 0 0 0）。為了避免這種預(yù)測(cè)，可以使用一個(gè)基于指針的最大優(yōu)先隊(duì)列來(lái)取代基于數(shù)組的隊(duì)列，這種表示方法見9 . 4節(jié)的左高樹。
2) bestw表示當(dāng)前所有可行節(jié)點(diǎn)的重量的最大值，而優(yōu)先隊(duì)列中可能有許多其u w e i g h t不超過(guò)b e s t w的活節(jié)點(diǎn)，因此這些節(jié)點(diǎn)不可能幫助我們找到最優(yōu)的葉節(jié)點(diǎn)，這些節(jié)點(diǎn)浪費(fèi)了珍貴的隊(duì)列空間，并且它們的插入/刪除動(dòng)作也浪費(fèi)了時(shí)間，所以可以將這些節(jié)點(diǎn)刪除。有一種策略可以減少這種浪費(fèi)，即在插入某個(gè)節(jié)點(diǎn)之前檢查是否有u w e i g h t < b e s t w。然而，由于b e s t w在算法執(zhí)行過(guò)程中是不斷增大的，所以目前插入的節(jié)點(diǎn)在以后并不能保證u w e i g h t < b e s t w。另一種更好的方法是在每次b e s t w增大時(shí)，刪除隊(duì)列中所有u w e i g h t < b e s e w的節(jié)點(diǎn)。這種策略要求刪除具有最小u w e i g h t的節(jié)點(diǎn)。因此，隊(duì)列必須支持如下的操作：插入、刪除最大節(jié)點(diǎn)、刪除最小節(jié)點(diǎn)。這種優(yōu)先隊(duì)列也被稱作雙端優(yōu)先隊(duì)列（ double-ended priority queue）。這種隊(duì)列的數(shù)據(jù)結(jié)構(gòu)描述見第9章的參考文獻(xiàn)。
5.2.2 0/1背包問(wèn)題
0 / 1背包問(wèn)題的最大收益分枝定界算法可以由程序1 6 - 6發(fā)展而來(lái)。可以使用程序1 6 - 6的B o u n d函數(shù)來(lái)計(jì)算活節(jié)點(diǎn)N的收益上限u p ,使得以N為根的子樹中的任一節(jié)點(diǎn)的收益值都不可能超過(guò)u p r o f i t。活節(jié)點(diǎn)的最大堆使用u p r o f i t作為關(guān)鍵值域，最大堆的每個(gè)入口都以H e a p N o d e作為其類型，H e a p N o d e有如下私有成員：uprofit, profit, weight，l e v e l，p t r，其中l(wèi) e v e l和p t r的定義與裝箱問(wèn)題（見程序1 7 - 5）中的含義相同。對(duì)任一節(jié)點(diǎn)N，N . p r o f i t是N的收益值，N uprofit是它的收益上限， N. weight 是它對(duì)應(yīng)的重量。b b n o d e類型如程序1 7 - 5中的定義，各節(jié)點(diǎn)按其u p r o f i t值從最大堆中取出。
程序1 7 - 7使用了類Knap, 它類似于回溯法中的類K n a p（見程序1 6 - 5）。兩個(gè)K n a p版本中數(shù)據(jù)成員之間的區(qū)別見程序1 7 - 7：1) bestp 不再是一個(gè)成員； 2) bestx 是一個(gè)指向int 的新成員。新增成員的作用是：當(dāng)且僅當(dāng)物品j 包含在最優(yōu)解中時(shí)， b e s t x [ j ] = 1。函數(shù)A d d L i v e N o d e用于將新的b b n o d e類型的活節(jié)點(diǎn)插入子集樹中，同時(shí)將H e a p N o d e類型的活節(jié)點(diǎn)插入到最大堆中。這個(gè)函數(shù)與裝箱問(wèn)題（見程序1 7 - 6）中的對(duì)應(yīng)函數(shù)非常類似，因此相應(yīng)的代碼被省略。
程序17-7 0/1背包問(wèn)題的最大收益分枝定界算法
template<class Tw, class Tp>
Tp Knap<Tw, Tp>::MaxProfitKnapsack()
{// 返回背包最優(yōu)裝載的收益
// bestx[i] = 1 當(dāng)且僅當(dāng)物品i 屬于最優(yōu)裝載
// 使用最大收益分枝定界算法
// 定義一個(gè)最多可容納1 0 0 0個(gè)活節(jié)點(diǎn)的最大堆
H = new MaxHeap<HeapNode<Tp, Tw> > (1000);
// 為b e s t x分配空間
bestx = new int [n+1];
// 初始化層1
int i = 1;
E = 0;
cw = cp = 0;
Tp bestp = 0; // 目前的最優(yōu)收益
Tp up = Bound(1); // 在根為E的子樹中最大可能的收益
// 搜索子集空間樹
while (i != n+1) { // 不是葉子
// 檢查左孩子
Tw wt = cw + w[i];
if (wt <= c) {// 可行的左孩子
if (cp+p[i] > bestp) bestp = cp+p[i];
AddLiveNode(up, cp+p[i], cw+w[i], true, i+1);}
up = Bound(i+1);
// 檢查右孩子
if (up >= bestp) // 右孩子有希望
AddLiveNode(up, cp, cw, false, i+1);
// 取下一個(gè)E-節(jié)點(diǎn)
HeapNode<Tp, Tw> N;
H->DeleteMax(N); // 不能為空
E = N.ptr;
cw = N.weight;
cp = N.profit;
up = N.uprofit;
i = N.level;
}
// 沿著從E-節(jié)點(diǎn)E到根的路徑構(gòu)造bestx[]
for (int j = n; j > 0; j--) {
bestx[j] = E-> L C h i l d ;
E = E-> p a r e n t ;
}
return cp;
}
函數(shù)M a x P r o f i t K n a p s a c k在子集樹中執(zhí)行最大收益分枝定界搜索。函數(shù)假定所有的物品都是按收益密度值的順序排列，可以使用類似于程序1 6 - 9中回溯算法所使用的預(yù)處理代碼來(lái)完成這種排序。函數(shù)M a x P r o f i t K n a p s a c k首先初始化活節(jié)點(diǎn)的最大堆，并使用一個(gè)數(shù)組b e s t x來(lái)記錄最優(yōu)解。由于需要不斷地利用收益密度來(lái)排序，物品的索引值會(huì)隨之變化，因此必須將M a x P r o f i t K n a p s a c k所生成的結(jié)果映射回初始時(shí)的物品索引。可以用Q的I D域來(lái)實(shí)現(xiàn)上述映射（見程序1 6 - 9）。
在函數(shù)M a x P r o f i t K n a p S a c k中，E是當(dāng)前E-節(jié)點(diǎn)，c w是節(jié)點(diǎn)對(duì)應(yīng)的重量， c p是收益值，u p是以E為根的子樹中任一節(jié)點(diǎn)的收益值上限。w h i l e循環(huán)一直執(zhí)行到一個(gè)葉節(jié)點(diǎn)成為E-節(jié)點(diǎn)為止。由于最大堆中的任何剩余節(jié)點(diǎn)都不可能具有超過(guò)當(dāng)前葉節(jié)點(diǎn)的收益值，因此當(dāng)前葉即對(duì)應(yīng)了一個(gè)最優(yōu)解。可以從葉返回到根來(lái)確定這個(gè)最優(yōu)解。
M a x P r o f i t K n a p s a c k中w h i l e循環(huán)的結(jié)構(gòu)很類似于程序1 7 - 6的w h i l e循環(huán)。首先，檢驗(yàn)E-節(jié)點(diǎn)左孩子的可行性，如它是可行的，則將它加入子集樹及活節(jié)點(diǎn)隊(duì)列（即最大堆）；僅當(dāng)節(jié)點(diǎn)右孩子的B o u n d值指明有可能找到一個(gè)最優(yōu)解時(shí)才將右孩子加入子集樹和隊(duì)列中。
5.2.3 最大完備子圖
4 . 2 . 3節(jié)完備子圖問(wèn)題的解空間樹也是一個(gè)子集樹，故可以使用與裝箱問(wèn)題、背包問(wèn)題相同的最大收益分枝定界方法來(lái)求解這種問(wèn)題。解空間樹中的節(jié)點(diǎn)類型為b b n o d e，而最大優(yōu)先隊(duì)列中元素的類型則是C l i q u e N o d e。C l i q u e N o d e有如下域：c n（該節(jié)點(diǎn)對(duì)應(yīng)的完備子圖中的頂點(diǎn)數(shù)目），u n（該節(jié)點(diǎn)的子樹中任意葉節(jié)點(diǎn)所對(duì)應(yīng)的完備子圖的最大尺寸），l e v e l（節(jié)點(diǎn)在解空間樹中的層），c n（當(dāng)且僅當(dāng)該節(jié)點(diǎn)是其父節(jié)點(diǎn)的左孩子時(shí)， c n為1），p t r（指向節(jié)點(diǎn)在解空間樹中的位置）。u n的值等于c n + n - l e v e + 1。因?yàn)楦鶕?jù)un 和c n（或l e v e l）可以求出l e v e l（或c n），所以可以去掉c n或l e v e l域。當(dāng)從最大優(yōu)先隊(duì)列中選取元素時(shí)，選取的是具有最大u n值的元素。在程序1 7 - 8中，C l i q u e N o d e包含了所有的三個(gè)域：c n，un 和l e v e l，這樣便于嘗試為u n賦予不同的含義。函數(shù)A d d C l i q u e N o d e用于向生成的子樹和最大堆中加入節(jié)點(diǎn)，由于其代碼非常類似于裝箱和背包問(wèn)題中的對(duì)應(yīng)函數(shù)，故將它略去。
函數(shù)B B M a x C l i q u e在解空間樹中執(zhí)行最大收益分枝定界搜索，樹的根作為初始的E-節(jié)點(diǎn)，該節(jié)點(diǎn)并沒有在所構(gòu)造的樹中明確存儲(chǔ)。對(duì)于這個(gè)節(jié)點(diǎn)來(lái)說(shuō)，其cn 值（E-節(jié)點(diǎn)對(duì)應(yīng)的完備子圖的大小）為0，因?yàn)檫€沒有任何頂點(diǎn)被加入完備子圖中。E-節(jié)點(diǎn)的層由變量i 指示，它的初值為1，對(duì)應(yīng)于樹的根節(jié)點(diǎn)。當(dāng)前所找到的最大完備子圖的大小保存在b e s t n中。
在while 循環(huán)中，不斷展開E-節(jié)點(diǎn)直到一個(gè)葉節(jié)點(diǎn)變成E-節(jié)點(diǎn)。對(duì)于葉節(jié)點(diǎn)，u n＝c n。由于所有其他節(jié)點(diǎn)的un 值都小于等于當(dāng)前葉節(jié)點(diǎn)對(duì)應(yīng)的un 值，所以它們不可能產(chǎn)生更大的完備子圖，因此最大完備子圖已經(jīng)找到。沿著生成的樹中從葉節(jié)點(diǎn)到根的路徑，即可構(gòu)造出這個(gè)最大完備子圖。
為了展開一個(gè)非葉E-節(jié)點(diǎn)，應(yīng)首先檢查它的左孩子，如果左孩子對(duì)應(yīng)的頂點(diǎn)i與當(dāng)前E-節(jié)點(diǎn)所包含的所有頂點(diǎn)之間都有一條邊，則i 被加入當(dāng)前的完備子圖之中。為了檢查左孩子的可行性，可以沿著從E-節(jié)點(diǎn)到根的路徑，判斷哪些頂點(diǎn)包含在E-節(jié)點(diǎn)之中，同時(shí)檢查這些頂點(diǎn)中每個(gè)頂點(diǎn)是否都存在一條到i 的邊。如果左孩子是可行的，則把它加入到最大優(yōu)先隊(duì)列和正在構(gòu)造的樹中。下一步，如果右孩子的子樹中包含最大完備子圖對(duì)應(yīng)的葉節(jié)點(diǎn)，則把右孩子也加入。
由于每個(gè)圖都有一個(gè)最大完備子圖，因此從堆中刪除節(jié)點(diǎn)時(shí)，不需要檢驗(yàn)堆是否為空。僅當(dāng)?shù)竭_(dá)一個(gè)可行的葉節(jié)點(diǎn)時(shí)，w h i l e循環(huán)終止。
程序17-8 最大完備子圖問(wèn)題的分枝定界算法
int AdjacencyGraph::BBMaxClique(int bestx[])
{// 尋找一個(gè)最大完備子圖的最大收益分枝定界程序
// 定義一個(gè)最多可容納1 0 0 0個(gè)活節(jié)點(diǎn)的最大堆
MaxHeap<CliqueNode> H(1000);
// 初始化層1
bbnode *E = 0; // 當(dāng)前的E-節(jié)點(diǎn)為根
int i = 1, // E-節(jié)點(diǎn)的層
cn = 0, // 完備子圖的大小
bestn = 0; // 目前最大完備子圖的大小
// 搜索子集空間樹
while (i != n+1) {// 不是葉子
// 在當(dāng)前完備子圖中檢查頂點(diǎn)i 是否與其它頂點(diǎn)相連
bool OK = true;
bbnode *B = E;
for (int j = i - 1; j > 0; B = B->parent, j--)
if (B->LChild && a[i][j] == NoEdge) {
OK = false;
b r e a k ; }
if (OK) {// 左孩子可行
if (cn + 1 > bestn) bestn = cn + 1;
AddCliqueNode(H, cn+1, cn+n-i+1, i+1, E, true);}
if (cn + n - i >= bestn)
// 右孩子有希望
AddCliqueNode(H, cn, cn+n-i, i+1, E, false);
// 取下一個(gè)E-節(jié)點(diǎn)
CliqueNode N;
H.DeleteMax(N); // 不能為空
E = N.ptr;
cn = N.cn;
i = N.level;
}
// 沿著從E到根的路徑構(gòu)造bestx[]
for (int j = n; j > 0; j--) {
bestx[j] = E-> L C h i l d ;
E = E-> p a r e n t ;
}
return bestn;
}
5.2.4 旅行商問(wèn)題
旅行商問(wèn)題的介紹見4 . 2 . 4節(jié)，它的解空間是一個(gè)排列樹。與在子集樹中進(jìn)行最大收益和最小耗費(fèi)分枝定界搜索類似，該問(wèn)題有兩種實(shí)現(xiàn)的方法。第一種是只使用一個(gè)優(yōu)先隊(duì)列，隊(duì)列中的每個(gè)元素中都包含到達(dá)根的路徑。另一種是保留一個(gè)部分解空間樹和一個(gè)優(yōu)先隊(duì)列，優(yōu)先隊(duì)列中的元素并不包含到達(dá)根的路徑。本節(jié)只實(shí)現(xiàn)前一種方法。
由于我們要尋找的是最小耗費(fèi)的旅行路徑，因此可以使用最小耗費(fèi)分枝定界法。在實(shí)現(xiàn)過(guò)程中，使用一個(gè)最小優(yōu)先隊(duì)列來(lái)記錄活節(jié)點(diǎn)，隊(duì)列中每個(gè)節(jié)點(diǎn)的類型為M i n H e a p N o d e。每個(gè)節(jié)點(diǎn)包括如下區(qū)域： x（從1到n的整數(shù)排列，其中x [ 0 ] = 1 )，s（一個(gè)整數(shù)，使得從排列樹的根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑定義了旅行路徑的前綴x[0:s], 而剩余待訪問(wèn)的節(jié)點(diǎn)是x [ s + 1 : n - 1 ]），c c（旅行路徑前綴，即解空間樹中從根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的耗費(fèi)），l c o s t（該節(jié)點(diǎn)子樹中任意葉節(jié)點(diǎn)中的最小耗費(fèi)）， r c o s t（從頂點(diǎn)x [ s : n - 1 ]出發(fā)的所有邊的最小耗費(fèi)之和）。當(dāng)類型為M i n H e a p N o d e ( T )的數(shù)據(jù)被轉(zhuǎn)換成為類型T時(shí)，其結(jié)果即為l c o s t的值。分枝定界算法的代碼見程序1 7 - 9。
程序1 7 - 9首先生成一個(gè)容量為1 0 0 0的最小堆，用來(lái)表示活節(jié)點(diǎn)的最小優(yōu)先隊(duì)列。活節(jié)點(diǎn)按其l c o s t值從最小堆中取出。接下來(lái)，計(jì)算有向圖中從每個(gè)頂點(diǎn)出發(fā)的邊中耗費(fèi)最小的邊所具有的耗費(fèi)M i n O u t。如果某些頂點(diǎn)沒有出邊，則有向圖中沒有旅行路徑，搜索終止。如果所有的頂點(diǎn)都有出邊，則可以啟動(dòng)最小耗費(fèi)分枝定界搜索。根的孩子（圖1 6 - 5的節(jié)點(diǎn)B）作為第一個(gè)E-節(jié)點(diǎn)，在此節(jié)點(diǎn)上，所生成的旅行路徑前綴只有一個(gè)頂點(diǎn)1，因此s=0, x[0]=1, x[1:n-1]是剩余的頂點(diǎn)（即頂點(diǎn)2 ， 3 ，.， n ）。旅行路徑前綴1 的開銷為0 ，即c c = 0 ，并且，r c o st=n ?i=1M i n O u t [i]。在程序中，bestc 給出了當(dāng)前能找到的最少的耗費(fèi)值。初始時(shí)，由于沒有找到任何旅行路徑，因此b e s t c的值被設(shè)為N o E d g e。
程序17-9 旅行商問(wèn)題的最小耗費(fèi)分枝定界算法
template<class T>
T AdjacencyWDigraph<T>::BBTSP(int v[])
{// 旅行商問(wèn)題的最小耗費(fèi)分枝定界算法
// 定義一個(gè)最多可容納1 0 0 0個(gè)活節(jié)點(diǎn)的最小堆
MinHeap<MinHeapNode<T> > H(1000);
T *MinOut = new T [n+1];
// 計(jì)算MinOut[i] = 離開頂點(diǎn)i的最小耗費(fèi)邊的耗費(fèi)
T MinSum = 0; // 離開頂點(diǎn)i的最小耗費(fèi)邊的數(shù)目
for (int i = 1; i <= n; i++) {
T Min = NoEdge;
for (int j = 1; j <= n; j++)
if (a[i][j] != NoEdge &&
(a[i][j] < Min || Min == NoEdge))
Min = a[i][j];
if (Min == NoEdge) return NoEdge; // 此路不通
MinOut[i] = Min;
MinSum += Min;
}
// 把E-節(jié)點(diǎn)初始化為樹根
MinHeapNode<T> E;
E.x = new int [n];
for (i = 0; i < n; i++)
E.x[i] = i + 1;
E.s = 0; // 局部旅行路徑為x [ 1 : 0 ]
E.cc = 0; // 其耗費(fèi)為0
E.rcost = MinSum;
T bestc = NoEdge; // 目前沒有找到旅行路徑
// 搜索排列樹
while (E.s < n - 1) {// 不是葉子
if (E.s == n - 2) {// 葉子的父節(jié)點(diǎn)
// 通過(guò)添加兩條邊來(lái)完成旅行
// 檢查新的旅行路徑是不是更好
if (a[E.x[n-2]][E.x[n-1]] != NoEdge && a[E.x[n-1]][1] != NoEdge && (E.cc +
a[E.x[n-2]][E.x[n-1]] + a[E.x[n-1]][1] < bestc || bestc == NoEdge)) {
// 找到更優(yōu)的旅行路徑
bestc = E.cc + a[E.x[n-2]][E.x[n-1]] + a[E.x[n-1]][1];
E.cc = bestc;
E.lcost = bestc;
E . s + + ;
H . I n s e r t ( E ) ; }
else delete [] E.x;}
else {// 產(chǎn)生孩子
for (int i = E.s + 1; i < n; i++)
if (a[E.x[E.s]][E.x[i]] != NoEdge) {
// 可行的孩子, 限定了路徑的耗費(fèi)
T cc = E.cc + a[E.x[E.s]][E.x[i]];
T rcost = E.rcost - MinOut[E.x[E.s]];
T b = cc + rcost; //下限
if (b < bestc || bestc == NoEdge) {
// 子樹可能有更好的葉子
// 把根保存到最大堆中
MinHeapNode<T> N;
N.x = new int [n];
for (int j = 0; j < n; j++)
N.x[j] = E.x[j];
N.x[E.s+1] = E.x[i];
N.x[i] = E.x[E.s+1];
N.cc = cc;
N.s = E.s + 1;
N.lcost = b;
N.rcost = rcost;
H . I n s e r t ( N ) ; }
} // 結(jié)束可行的孩子
delete [] E.x;} // 對(duì)本節(jié)點(diǎn)的處理結(jié)束
try // 取下一個(gè)E-節(jié)點(diǎn)
catch (OutOfBounds) // 沒有未處理的節(jié)點(diǎn)
}
if (bestc == NoEdge) return NoEdge; // 沒有旅行路徑
// 將最優(yōu)路徑復(fù)制到v[1:n] 中
for (i = 0; i < n; i++)
v[i+1] = E.x[i];
while (true) {// 釋放最小堆中的所有節(jié)點(diǎn)
delete [] E.x;
try
catch (OutOfBounds)
}
return bestc;
}
while 循環(huán)不斷地展開E-節(jié)點(diǎn)，直到找到一個(gè)葉節(jié)點(diǎn)。當(dāng)s = n - 1時(shí)即可說(shuō)明找到了一個(gè)葉節(jié)點(diǎn)。旅行路徑前綴是x [ 0 : n - 1 ]，這個(gè)前綴中包含了有向圖中所有的n個(gè)頂點(diǎn)。因此s = n - 1的活節(jié)點(diǎn)即為一個(gè)葉節(jié)點(diǎn)。由于算法本身的性質(zhì)，在葉節(jié)點(diǎn)上lcost 和cc 恰好等于葉節(jié)點(diǎn)對(duì)應(yīng)的旅行路徑的耗費(fèi)。由于所有剩余的活節(jié)點(diǎn)的lcost 值都大于等于從最小堆中取出的第一個(gè)葉節(jié)點(diǎn)的lcost 值，所以它們并不能幫助我們找到更好的葉節(jié)點(diǎn)，因此，當(dāng)某個(gè)葉節(jié)點(diǎn)成為E-節(jié)點(diǎn)后，搜索過(guò)程即終止。
while 循環(huán)體被分別按兩種情況處理，一種是處理s = n - 2的E-節(jié)點(diǎn)，這時(shí)，E-節(jié)點(diǎn)是某個(gè)單獨(dú)葉節(jié)點(diǎn)的父節(jié)點(diǎn)。如果這個(gè)葉節(jié)點(diǎn)對(duì)應(yīng)的是一個(gè)可行的旅行路徑，并且此旅行路徑的耗費(fèi)小于當(dāng)前所能找到的最小耗費(fèi)，則此葉節(jié)點(diǎn)被插入最小堆中，否則葉節(jié)點(diǎn)被刪除，并開始處理下一個(gè)E-節(jié)點(diǎn)。
其余的E-節(jié)點(diǎn)都放在while 循環(huán)的第二種情況中處理。首先，為每個(gè)E-節(jié)點(diǎn)生成它的兩個(gè)子節(jié)點(diǎn)，由于每個(gè)E-節(jié)點(diǎn)代表著一條可行的路徑x [ 0 : s ]，因此當(dāng)且僅當(dāng)< x[s],x[i] > 是有向圖的邊且x [ i ]是路徑x [ s + 1 : n - 1 ]上的頂點(diǎn)時(shí)，它的子節(jié)點(diǎn)可行。對(duì)于每個(gè)可行的孩子節(jié)點(diǎn)，將邊<x[s],x[i] > 的耗費(fèi)加上E.cc 即可得到此孩子節(jié)點(diǎn)的路徑前綴( x [ 0 : s ]，x[i]) 的耗費(fèi)c c。由于每個(gè)包含此前綴的旅行路徑都必須包含離開每個(gè)剩余頂點(diǎn)的出邊，因此任何葉節(jié)點(diǎn)對(duì)應(yīng)的耗費(fèi)都不可能小于cc 加上離開各剩余頂點(diǎn)的出邊耗費(fèi)的最小值之和，因而可以把這個(gè)下限值作為E-節(jié)點(diǎn)所生成孩子的lcost 值。如果新生成孩子的lcost 值小于目前找到的最優(yōu)旅行路徑的耗費(fèi)b e s t c，則把新生成的孩子加入活節(jié)點(diǎn)隊(duì)列（即最小堆）中。
如果有向圖沒有旅行路徑，程序1 7 - 9返回N o E d g e；否則，返回最優(yōu)旅行路徑的耗費(fèi)，而最優(yōu)旅行路徑的頂點(diǎn)序列存儲(chǔ)在數(shù)組v 中。
5.2.5 電路板排列
電路板排列問(wèn)題（ 1 6 . 2 . 5節(jié)）的解空間是一棵排列樹，可以在此樹中進(jìn)行最小耗費(fèi)分枝定界搜索來(lái)找到一個(gè)最小密度的電路板排列。我們使用一個(gè)最小優(yōu)先隊(duì)列，其中元素的類型為B o a r d N o d e，代表活節(jié)點(diǎn)。B o a r d N o d e類型的對(duì)象包含如下域： x（電路板的排列），s（電路板x[1:s]) 依次放置在位置1 到s 上），c d（電路板排列x [ 1 : s ]的密度，其中包括了到達(dá)x[s] 右邊的連線），n o w（now[j] 是排列x[1:s] 中包含j 的電路板的數(shù)目）。當(dāng)一個(gè)BoardNode 類型的對(duì)象轉(zhuǎn)換為整型時(shí)，其結(jié)果即為對(duì)象的cd 值。代碼見程序1 7 - 1 0。
程序17-10 電路板排列問(wèn)題的最小耗費(fèi)分枝定界算法
int BBArrangeBoards(int **B, int n, int m, int* &bestx)
{// 最小耗費(fèi)分枝定界算法, m個(gè)插槽, n塊板
MinHeap<BoardNode> H(1000); // 容納活節(jié)點(diǎn)
// 初始化第一個(gè)E節(jié)點(diǎn)、t o t a l和b e s t d
BoardNode E;
E.x = new int [n+1];
E.s = 0; // 局部排列為E . x [ 1 : s ]
E.cd = 0; // E.x[1:s]的密度
E.now = new int [m+1];
int *total = new int [m+1];
// now[i] = x[1:s]中含插槽i的板的數(shù)目
// total[i] = 含插槽i的板的總數(shù)目
for (int i = 1; i <= m; i++) {
total[i] = 0;
E.now[i] = 0;
}
for (i = 1; i <= n; i++) {
E.x[i] = i; // 排列為1 2 3 4 5 . . . n
for (int j = 1; j <= m; j++)
total[j] += B[i][j]; // 含插槽j的板
}
int bestd = m + 1; / /目前的最優(yōu)密度
bestx = 0; // 空指針
do {// 擴(kuò)展E節(jié)點(diǎn)
if (E.s == n - 1) {// 僅有一個(gè)孩子
int ld = 0; // 最后一塊板的局部密度
for (int j = 1; j <= m; j++)
ld += B[E.x[n]][j];
if (ld < bestd) {// 更優(yōu)的排列
delete [] bestx;
bestx = E.x;
bestd = max(ld, E.cd);
}
else delete [] E.x;
delete [] E.now;}
else {// 生成E-節(jié)點(diǎn)的孩子
for (int i = E.s + 1; i <= n; i++) {
BoardNode N;
N.now = new int [m+1];
for (int j = 1; j <= m; j++)
// 在新板中對(duì)插槽計(jì)數(shù)
N.now[j] = E.now[j] + B[E.x[i]][j];
int ld = 0; // 新板的局部密度
for (j = 1; j <= m; j++)
if (N.now[j] > 0 && total[j] != N.now[j]) ld++;
N.cd = max(ld, E.cd);
if (N.cd < bestd) {// 可能會(huì)引向更好的葉子
N.x = new int [n+1];
N.s = E.s + 1;
for (int j = 1; j <= n; j++)
N.x[j] = E.x[j];
N.x[N.s] = E.x[i];
N.x[i] = E.x[N.s];
H . I n s e r t ( N ) ; }
else delete [] N.now;}
delete [] E.x;} // 處理完當(dāng)前E-節(jié)點(diǎn)
try // 下一個(gè)E-節(jié)點(diǎn)
catch (OutOfBounds) {return bestd;} //沒有E-節(jié)點(diǎn)
} while (E.cd < bestd);
// 釋放最小堆中的所有節(jié)點(diǎn)
do {delete [] E.x;
delete [] E.now;
try
catch (...)
} while (true);
return bestd;
}
程序1 7 - 1 0首先初始化E-節(jié)點(diǎn)為排列樹的根，此節(jié)點(diǎn)中沒有任何電路板，因此有s=0, cd=0,n o w [ i ] = 0（1≤i≤n），x是整數(shù)1到n 的任意排列。接著，程序生成一個(gè)整型數(shù)組t o t a l，其中total[i] 的值為包含i 的電路板的數(shù)目。目前能找到的最優(yōu)的電路板排列記錄在數(shù)組bestx 中，對(duì)應(yīng)的密度存儲(chǔ)在bestd 中。程序中使用一個(gè)do-while 循環(huán)來(lái)檢查每一個(gè)E-節(jié)點(diǎn)，在每次循環(huán)的尾部，將從最小堆中選出具有最小cd 值的節(jié)點(diǎn)作為下一個(gè)E-節(jié)點(diǎn)。如果某個(gè)E-節(jié)點(diǎn)的cd 值大于等于bestd，則任何剩余的活節(jié)點(diǎn)都不能使我們找到密度小于bestd的電路板排列，因此算法終止。
d o - w h i l e循環(huán)分兩種情況處理E-節(jié)點(diǎn)，第一種是處理s = n - 1時(shí)的情況，此種情況下，有n - 1個(gè)電路板被放置好， E-節(jié)點(diǎn)即解空間樹中的某個(gè)葉節(jié)點(diǎn)的父節(jié)點(diǎn)。節(jié)點(diǎn)對(duì)應(yīng)的密度會(huì)被計(jì)算出來(lái)，如果需要，bested 和bestx 將被更新。在第二種情況中，E-節(jié)點(diǎn)有兩個(gè)或更多的孩子。每當(dāng)一個(gè)孩子節(jié)點(diǎn)N生成時(shí)，它對(duì)應(yīng)的部分排列( x [ 1 : s + 1 ] )的密度N . c d就會(huì)被計(jì)算出來(lái)，如果N . c d < b e s t d ,則N被存放在最小優(yōu)先隊(duì)列中；如果N . c d≥b e s t d，則它的子樹中的所有葉節(jié)點(diǎn)對(duì)應(yīng)的密度都滿足d e n s i t y≥b e s t d，這就意味著不會(huì)有優(yōu)于b e s t x的排列。