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