分支定界 (branch and bound) 算法是一種在問題的解空間樹上搜索問題的解的方法。但與回溯算法不同，分支定界算法采用廣度優先或最小耗費優先的方法搜索解空間樹，并且，在分支定界算法中，每一個活結點只有一次機會成為擴展結點。

利用分支定界算法對問題的解空間樹進行搜索，它的搜索策略是：

1 ．產生當前擴展結點的所有孩子結點；

2 ．在產生的孩子結點中，拋棄那些不可能產生可行解（或最優解）的結點；

3 ．將其余的孩子結點加入活結點表；

4 ．從活結點表中選擇下一個活結點作為新的擴展結點。

如此循環，直到找到問題的可行解（最優解）或活結點表為空。

從活結點表中選擇下一個活結點作為新的擴展結點，根據選擇方式的不同，分支定界算法通常可以分為兩種形式：

1 ． FIFO(First In First Out) 分支定界算法：按照先進先出原則選擇下一個活結點作為擴展結點，即從活結點表中取出結點的順序與加入結點的順序相同。

2 ．最小耗費或最大收益分支定界算法：在這種情況下，每個結點都有一個耗費或收益。如果要查找一個具有最小耗費的解，那么要選擇的下一個擴展結點就是活結點表中具有最小耗費的活結點；如果要查找一個具有最大收益的解，那么要選擇的下一個擴展結點就是活結點表中具有最大收益的活結點。

下面通過一個具體實例加深大家對 FIFO 分支定界算法的認識。

例： 裝箱問題 (2001 年全國青少年信息學（計算機）奧林匹克分區聯賽初中組復賽試題第四題 ) 
[ 問題描述 ] 
有一個箱子容量為 v( 正整數， 0≤v≤20000) ，同時有 n 個物品 (0≤n≤30) ，每個物品有一個體積 ( 正整數 ) 。要求從 n 個物品中，任取若干個裝入箱內，使箱子的剩余空間為最小。 
[ 樣例 ]

輸入：

10 一個整數，表示箱子容量

3 一個整數，表示有 n 個物品

4 接下來 n 行，分別表示這 n 個物品的各自體積。

8

5

輸出：

1 一個整數，表示箱子剩余空間。

分析： 根據題目要求，要從 n 個物品中任取若干個裝入箱內，使得箱子的剩余空間最小，換句話說就是要盡可能地裝滿箱子。只要我們找到一種裝載方案，在箱子的容量范圍內，它的裝載值為最大，即裝入箱子的這些物品的體積之和為最大，那么箱子的容量與最優裝載值之差就是問題的答案（最小剩余空間）。

要尋找這樣一個最優裝載值，我們不妨先考察一個簡單的例子。比如：箱子容量 v=10 ，物品個數 n=3 ，第 1 個物品的體積 tiji[1] =4 ，第 2 個物品的體積 tiji[2] =8 ，第 3 個物品的體積 tiji[3] =5 。利用分支定界算法求解，首先要將問題的解空間組織成一棵樹，如圖。對于每一個物品，只有裝入箱子和不裝入箱子兩種可能，我們用結點的兩個孩子分別表示這兩種可能，規定左孩子表示相應的物品裝入箱子，右孩子表示相應的物品不裝入箱子。樹中結點左上角的數字為該結點對應的權值。例如 A 的左孩子 B 表示將第 1 個物品裝入箱子， B 的權值 4 表示在結點 B 處，箱子中已裝入物品的體積之和為 4 ；而 A 的右孩子 C 表示第 1 個物品不被裝入箱子， C 的權值 0 則表示在結點 C 處，箱子中已裝入物品的體積之和為 0 。同樣， D 、 F 都表示將第 2 個物品裝入箱子， D 的權值 12 表示在結點 D 處，箱子中已裝入物品的體積之和為 12 ，……這樣，解空間樹中每一條從根結點到葉子結點的路徑就表示一種可能的裝載方案（暫時不考慮裝載過程中必須滿足的條件）。

javascript:window.open(this.src);" style="cursor:pointer;"/>

在搜索過程中，我們設置變量 best 來保存當前的最優裝載值。搜索從根結點 A 開始， A 是當前的擴展結點，此時活結點表中只有一個元素 -1 （標記本層尾部）， best=0 。按照分支定界算法的搜索策略，首先產生當前擴展結點 A 的孩子結點 B 和 C ；其次，在產生結點 B 和 C 的過程中，根據一定的條件（限界函數），拋棄不可能產生可行解（或最優解）的結點；再次，將剩下的 A 的孩子結點加入活結點表；最后，從當前的活結點表中取出下一個活結點作為新的擴展結點。如此重復，直到活結點表為空。

接下來還有一個問題，在產生當前擴展結點的孩子結點的過程中，孩子結點能否產生可行解（或最優解），怎樣進行判斷？即需要什么樣的限界函數。

仔細分析題目要求，我們很容易發現，題目中隱含著一個基本條件：裝入箱子中的所有物品的體積之和不能超出箱子的容量，即：所裝物品的體積之和 <= 箱子容量。另外，在對解空間樹進行搜索的過程中，如果發現某子樹不可能產生比當前最優解還要優的解，我們就沒有必要對這棵子樹進行搜索。這樣處理可以加快搜索速度，提高程序的性能。令 Z 為解空間樹第 i 層的一個結點， best 的定義如前， ew 為當前所裝物品的體積之和。以 Z 為根的子樹中沒有葉結點的裝載值會超過 ew+r ， 其中 r= 為剩余物品的體積之和

。因此，當 ew+r<=best 時，沒有必要去搜索 Z 的右子樹。

根據上面分析，可歸納算法程序如下：

1 ．輸入基本數據；

2 ．建立活結點表；

3 ．基本變量初始化；

4 ．搜索解空間樹。

其中，第 4 步需要進一步求精。

While true do

{ 檢查左孩子 }

if 左孩子的權值 <= 箱子容量 then

if 當前裝載體積 > 最優裝載值 (best) then

best= 當前裝載體積

endif

if 不是葉子結點 then

將左孩子結點加入活結點表中

endif

{ 檢查右孩子 }

if 可以有一個更好的葉子結點 then

將右孩子結點加入活結點表中

endif

endif

從當前活結點表中取下一個結點作為新的擴展結點

if 到達層的尾部 then

if 活結點表為空 then

輸出問題的解

結束對解空間樹的搜索

endif

添加尾部標記

從當前活結點表中取下一個結點作為新的擴展結點

產生新的層號 i

產生新的 r （剩余物品的體積之和）

endif

end{while}

第 2 步活結點表的建立，可以使用隊列來實現。分支定界算法的解空間比回溯算法大得多，因此在建立隊列的時候，最好使用鏈隊列，這樣可以提高程序的性能。 QBASIC 語言不支持指針這種數據類型，如果用 QBASIC 語言進行編程，鏈隊列的建立將會變得比較困難。所以，下面的參考程序，我們將以 PASCAL 語言給出。

PASCAL 語言參考程序如下：

program c2001_4(input,output);

type{ 鏈隊列抽象數據類型說明 }

queueptr=^queuenode;

queuenode=record

data:integer;{ 數據域 }

next:queueptr{ 指針域 }

end;

linkedquetp=record

front,rear:queueptr

{front 為隊頭指針， rear 為隊尾指針 }

end;

var

v,n,i,j,x,ew,wt,best,r:integer;

p,s:queueptr;

q:linkedquetp;

tiji:array[1..30]of integer;

flag:boolean;

procedure init_linkedqueue(var q:linkedquetp);

{ 設置一個空的鏈隊列 }

begin

new(q.front);q.rear:=q.front

q.front^.next:=nil

end;

procedure add(var q:linkedquetp;x:integer);

{ 在已知鏈隊列 q 中插入隊尾元素 x}

begin

new(p);p^.data:=x;p^.next:=nil;

q.rear^.next:=p;q.rear:=p

end;

function delete(var q:linkedquetp):integer;

{ 若鏈隊列 q 不空，則刪除隊尾元素并返回該元素，否則返回 -2}

begin

if q.front=q.rear

then delete:=-2

else begin

s:=q.front^.next;

q.front^.next:=s^.next;

if s^.next=nil then q.rear:=q.front;

x:=s^.data;

dispose(s);

delete:=x

end

end;

function empty(q:linkedquetp):boolean;

{ 若鏈隊列 q 為空隊列，則返回函數值“ true ”，否則返回函數值“ false ” }

begin

if q.rear=q.front

then empty:=true

else empty:=false

end;

begin

{ 輸入 }

write('Please input V:');readln(v);

write('Please input N:');readln(n);

writeln('Please input tiji:');

for i:=1 to n do

readln(tiji[i]);

init_linkedqueue(q);{ 建立活結點表（表中記錄著各活結點對應的權值） }

add(q,-1);{ 向活結點表添加元素 -1 ，標記本層尾部 }

i:=1;ew:=0;best:=0;r:=0;flag:=true;{i ：擴展結點的層； ew ：擴展結點的權值； best ：目前最優裝載值； r ：剩余物品的體積之和； flag ：循環控制變量（用來標識是否結束循環，若活結點表為空，則 flag=false ，退出循環） }

for j:=2 to n do

r:=r+tiji[j];

while flag do

{ 搜索解空間樹 }

begin

wt:=ew+tiji[i];{ 產生左孩子的權值 }

if wt<=v{ 可行的左孩子 }

then begin

if wt>best

then best:=wt;

if i<n

{ 若不是葉子結點，則添加到活結點表中 }

then add(q,wt)

end;

{ 檢查右孩子 }

if (ew+r>best) and (i<n)

{ 可以有一個更好的葉子 }

then add(q,ew);

{ 將右孩子添加到活結點表中 }

ew:=delete(q);{ 從活結點表中取下一個活結點作為新的擴展結點 }

if ew=-1{ 到達層的尾部 }

then begin

if empty(q){ 活結點表為空 }

then begin

writeln('best=',v-best);

{ 輸出最優剩余空間值 }

flag:=false

{ 結束循環的條件成立 }

end;

add(q,-1);{ 添加尾部標記 }

ew:=delete(q);{ 從活結點表中取下一個活結點作為新的擴展結點 }

i:=i+1;{ 改變層號 }

r:=r-tiji[i]

{ 改變剩余物品的體積之和 }

end

end

end.

結束語： 分支定界算法和回溯算法是在問題的解空間上搜索問題的解的兩種基本方法，回溯算法通常采用深度優先的方法搜索解空間樹，而分支定界算法則采用廣度優先或最小耗費優先的方法搜索解空間樹。很多能夠使用分支定界算法解決的問題，都可以使用回溯算法加以解決。大家在學習的時候，對同一個問題要多嘗試不同的方法，將它們加以比較，這樣不但可以找到較好的解決方案，還可以加深大家對不同算法思想的理解。