第6章分枝限界法6.1分枝限界法的基本思想

6.2

0-1背包問題

6.3作業調度問題

習題

6.1分枝限界法的基本思想

如果把回溯法看做深度優先搜索解空間樹的過程，那么分枝限界法則可看做廣度優先或者按照最大價值(或最小成本)搜索解空間樹的過程。它也是一種系統地搜索問題解的方法。按照從活結點表中選擇擴展結點的方法，分枝限界法又可細分為以下兩種：

(1)先進先出(FirstInFirstOut，FIFO)分枝限界法(FIFOBB)。

(2)優先隊列(PriorityQueue，PQ)分枝限界法(PQBB)。我們以0-1背包問題為例，討論這兩種分枝限界法的異同。某商店有n個物品，第i個物品價值為vi，容量(或稱權值)為wi，其中vi和wi為非負數。背包的容量為W，W為一非負數。目標是如何選擇裝入背包的物品，使裝入背包的物品總價值最大。這個問題的形式描述如下：

約束條件為

1．先進先出狀態空間樹

對于0-1背包問題，結點X處的估值函數 定義為 ，其中k表示結點X所在的層。用隊列作為組織活結點表的數據結構，按照結點進入隊列的先后順序選擇下一個擴展結點，得到0-1背包問題先進先出狀態空間樹，如圖6-1所示。圖6-1先進先出狀態空間樹

2．優先隊列狀態空間樹

當用優先隊列作為組織活結點表的數據結構，并按照結點估值函數值的大小選擇下一個擴展結點時，就得到0-1背包問題優先隊列狀態空間樹，如圖6-2所示。圖6-2優先隊列狀態空間樹正如在回溯法中所做的那樣，我們可以設計一個限界函數，以減少解空間的大小，加速搜索的速度。這個限界函數給出每一個可行結點對應子樹可能得到的最小成本(最大價值)的下界(上界)，如果這個下界(上界)不小于(不大于)當前最優解的值，則說明這個結點對應的子樹中不含問題的最優解，因而可以剪掉。此外，我們也可以將限界函數確定的每個結點的下界(上界)值作為優先級，并以該優先級的大小作為選擇當前E結點的原則。這種策略有時可以更快地找到問題的最優解。

6.2

0-1背包問題

1．限界

設T是一棵狀態空間樹，c(*)是T中結點的成本函數。如果X是T中的一個結點，則c(X)是其根為X的子樹中任一答案結點的最小成本。這個c(*)是難于構造的，通常使用一個對c(*)估值的啟發式函數l(*)來代替，這個啟發式函數易于計算：如果X是一個答案結點或一個葉結點，則c(*)=l(*)。搜索問題狀態空間樹的各種分枝限界法都是在生成當前E結點的所有子結點之后再將另一結點變成E結點的。假定每個答案結點X有一個與其相聯系的c(X)，并且假定會找到最小成本的答案結點，利用一個滿足l(X)≤c(X)的成本估值函數l(X)則可以給出任一結點X解的下界。采用下界函數可以減少搜索的盲目性，此外還可通過設置最小成本上界使算法進一步加速。如果Up是最小成本解的成本上界，則滿足l(X)>Up的所有活結點都可以被殺死，這是因為由X到達的

所有答案結點都滿足c(X)≥l(X)>Up。在已經到達一個具有成本Up的答案結點的情況下，那些滿足l(X)>Up的所有活結點都可以被殺死。Up的初始值可以用某種啟發式算法得到,也可以設置成∞。只要Up的初始值不小于最小成本結點的成本，上述殺死活結點的規則就不會殺死可以到達最小成本答案結點的活結點。每當找到一個新的答案結點時，就可以修改Up的值，即如果某個結點的上界u(X)<Up，則用該結點的上界u(X)更新Up。根據上述思想，我們考慮最小值優化問題的分枝限界法。為了找問題的最優解，需要將最優解的搜索表示成對狀態空間樹答案結點的搜索，可將問題最優答案結點的成本函數定義為所有結點成本的最小值。簡單的方法是直接將目標函數作為成本函數c(*)。在這種定義下，可行解結點的c(X)就是那個結點可行解的目標函數值，不可行結點的c(X)為+∞，部分解結點的c(X)是以X為根的子樹中結點的最小成本。

2．定義結點的限界函數

通過構造和設計結點處的限界函數，可以減小問題的狀態搜索空間。為了討論方便起見，我們將最大值優化問題轉變成最小值優化問題。如果用目標函數－ 替代目標函數 ，就使背包問題從一個最大值優化問題變成最小值優化問題。顯然， 取最小即 取最大。重新定義了目標函數之后，背包問題描述如下：(6.1)約束條件為

式(6.1)中各量的意義同6.1節。UPBOUND(cv,cw,k-1,W)

1 b

cv

2 c

cw

3 for

i

k

to

n

do

4

ifc+w[i]

W

5

then

c

c+w[i]

6 b

b–v[i]

7 return(b)

3．0-1背包問題優先隊列分枝限界法示例

對于上述構造的限界函數l(X)和u(X)，再次考慮6.1節的0-1背包問題實例。用優先隊列作為組織活結點表的數據結構，并按照結點l(X)值的大小選擇下一個擴展結點，得到0-1

背包問題優先隊列分枝限界樹，如圖6-3所示。圖6-3

0-1背包問題優先隊列分枝限界樹

4．算法中使用的主要數據結構及變量

由此可見，通過限界函數，大大減小了問題的搜索空間，提高了算法的效率。但另一方面，僅從路徑10,7,4,2,1不能確定哪些物品裝入背包，使得－∑vixi=Up,即不能確定裝入背包中物品xi的取值情況。因此，在實現中，需通過設置一些變量來記錄xi的取值信息。一種辦法是在每一個結點上增設一個標志域Tag，由答案結點到根結點的這些標志域給出xi的取值信息。

1)結點的結構

結點結構取決于用定長元組表示狀態空間樹，還是用變長元組表示狀態空間樹。這里仍然采用定長元組表示。活結點表中的每一個結點都有六個域的信息，如圖6-4所示。圖6-4結點的數據結構

2)擴展給定E結點的子結點

利用結點數據結構中的信息，可以確定任一活結點X的兩個子結點。當且僅當CW(X)≥wLevel(X)時，X的左孩子Y是可行結點，可以生成結點Y，在這種情況下，有

Parent(Y)=X，Level(Y)=Level(X)+1

CW(Y)=CW(X)–wLevel(X)，CV(Y)=CV(X)+vLevel(X)

Tag(Y)=1，UB(Y)=UB(X)

當CW(X)<wLevel(X)時，生成X的右孩子Y，在這種情況下，有

Parent(Y)=X，Level(Y)=Level(X)+1

CW(Y)=CW(X)，CV(Y)=CV(X)，Tag(Y)=0

3)識別答案結點

答案結點的識別比較容易，當且僅當Level(X)=n+1時，X是答案結點。

4)活結點表的數據結構

采用優先隊列作為組織活結點表的數據結構。需要在優先隊列上執行三個操作：判定優先隊列是否為空、向優先隊列中插入結點(類似于過程INSERT，見4.4節)和從優先隊列中摘取具有最小l(X)值的結點(類似于過程EXTRACT-MIN，見4.4節)。我們用最小堆實現優先隊列數據結構，如果堆中有n個結點，則判斷優先隊列是否為空的操作可在常數時間

O(1)內完成，插入操作和摘取操作的運行時間為O(lbn)，因為這兩個操作不會超過樹的深度O(lbn)。詳細的分析見4.4節。

5．0-1背包問題優先隊列分枝限界算法

在過程PQBB中，調用6個子過程，分別是LUBOUND、INSERTNODE、PRINT、INIT、GETNODE和EXTRACT-MAX。過程LUBOUND用于計算－l(X)和－u(X)。INSERTNODE生成一個6個數據域的結點，并對各個域進行賦值，最后插入到活結點表中。算法PRINT輸出問題最優解

的值和最優解。算法INIT對可用結點表和活結點表初始化。算法GETNODE取一個可用結點。算法EXTRACT-MAX從活結點表中摘取一個具有最大UB值的結點作為E結點，用最大堆實現時即摘取堆頂結點。LUBOUND(v,w,cw,cv,

n,k,LBB,UBB)

//cw表示背包可用權值，cv表示已得價值，LBB=–u(X)，UBB=–l(X)

1 LBB

cv

2 c

cw

3 fori

k

to

n

do

4

ifc<w[i]

5

thenUBB

LBB+c

v[i]/w[i]

6

forj

i+1tondo

7

if

c

w[j]

8

then

c

c–w[i]

9

LBB

LBB+v[j]

10

return

11 c

c–w[i]

12

LBB

LBB+v[i]

13 UBB

LBBINSERTNODE(par,lev,t,cap,valu,ub)

1 GETNODE(Node)//生成一個新結點Node

2 Parent(Node)

par

3 Level(Node)

lev

4 Tag(Node)

t

5 CW(Node)

cap

6 CV(Node)

valu

7 ADD(Node) PRINT(Lower,ans,n)

1 print(''valueofoptimalsolutionis'',Lower)

2 forj

n

downto1do

3

ifTag(ans)=1

4

thenprint(j)

5

ans

Parent(ans)

假設物品已經按照每單位權值非增排序，即v［i］/w［i］≥v［i+1］/w［i+1］。算法LCBB中使用了一個小的正參數ε，算法如下：LCBB(v,w,W,n,

)

1 INIT//初始化可用結點及活結點表

2 INSERT-NODE(E)//根結點

3 Parent(E)

0

4 Level(E)

1

5 CW(E)

W

6 CV(E)

0

7 LUBOUND(v,w,W,n,0,1,LBB,UBB)

8 Lower

LBB–

9 UB(E)

UBB

10 do11 i

Level(E)

12 cap

CW(E)

13 valu

CV(E)

14 if(i=n+1)//葉結點

15

if

valu>Lower

16 thenLower

valu

17

ans

E

18 elseif

cap

w[i]//左孩子可行

19

thenINSERTNODE(E,i+1,1,cap–w[i],valu+v[E],UB[E])20

LUBOUND(v,w,cap,valu,n,i+1,LBB,UBB)//右孩子是否成為活結點

21

ifUBB>Lower//判斷右孩子是否成為活結點

22 thenINSERTNODE(E,i+1,0,cap,valu,UBB)

23 Lower

max{Lower,LBB–

}

24

if

不存在活結點thenbreak//退出do…while

循環

25

EXTRACT-MAX(E)//下一個E結點是UB中最大的結點

26 while(UB(E)>Lower)

27 PRINT(Lower,ans,n)

6．0-1背包問題先進先出分枝限界算法

考慮6.1節的0-1背包問題實例，限界函數l(X)和u(X)的定義如前所述。用先進先出隊列作為組織活結點表的數據結構，并按照結點l(X)值的大小選擇下一個擴展結點，得到0-1背包問題先進先出分枝限界樹，如圖6-5所示。圖6-5

0-1FIFO分枝限界樹

0-1背包問題FIFOBB的算法中，結點的生成和E結點的選擇是逐層進行的。因此，無需為每個結點專門設置一個Level域，只需要在隊列中加上一個符號“＃”，作為層結束標志。狀態空間樹中每個結點可用五個域表示，如圖6-6所示。對LCBB算法做適當修改，就可得到0-1背包問題的FIFOBB算法，在此從略。圖6-6

FIFOBB算法中結點的數據結構

6.3作業調度問題

1．定義結點的限界函數

圖6-7表示變長元組表示的狀態空間樹，結點左邊值表示結點的l(X)值，結點右邊值表示當前最好上界Up值，一旦找到滿足l(X)>Up

的結點，該結點就被殺死。標有“×”的結點表示該結點被殺死，其中標有“×”的陰影結點表示由于是

不可行結點而被殺死，除陰影結點之外的所有結點都是答案結點。結點9是問題的最優解，它是惟一的最小成本答案結點，此時，最優解為J={2,3}，罰金為16，即最小成本。對于這棵樹中的結點，定義成本函數c(*)如下：對于不可行結點(陰影結點)，c(X)=+∞；對于其他結點，c(X)定義為根為X的子樹中結點的最小罰金。在圖6-7中，c(1)=16，c(2)=18，c(3)=16。圖6-7變長元組對應的狀態空間樹

2．作業調度問題FIFOBB算法示例

我們利用FIFOBB求解作業調度問題，假設利用圖6-7中的變長元組表示法。初始時，設置最小成本答案結點的成本上界為

結點1作為E結點，依次生成結點2、3、4和5。在結點2處，有

由于u(2)=38<Up，Up被修改為38。在結點3處，有

由于u(3)=28<Up，Up被修改為28。在結點4處，有

由于l(4)=30>Up，結點4被殺死。

在結點5處，有

由于l(5)=42>Up，結點5也被殺死。基于FIFO原則，結點2成為下一個E結點，生成它的子結點6、7和8。在結點6處，有

由于u(2)=18<Up=28，Up被修改為18。在結點7處，有

結點7被殺死。

結點8是不可行結點，也被殺死。結點3成為下一個E結點，生成它的子結點9和10。在結點9處，有

由于u(9)=16<Up=18，Up被修改為16。在結點10處，有

由于l(10)=22>Up，結點10被殺死。結點6成為下一個E結點，生成它的子結點11和12。結點11和12都為不可行結點，均被殺死。結點9成為下一個E結點，生成它的子結點13。結點13為不可行結點，被殺死。因此，結點9為最小成本答案結點，成本為16，問題的解J={2,3}。

3．作業調度問題FIFOBB-JS算法

過程FIFOBB-JS描述了找最小成本答案結點的作業調度問題的算法。過程中調用了兩個子過程，它們是INSERTQ(X)和EXTRACTQ(X)，分別表示向隊列插入一個結點和從隊列中刪除一個結點。對于狀態空間樹中的每個答案結點X，cost(X)是結點X對應的解的成本。在FIFOBB-JS中，假設不可行結點的估值l(X)=+∞,可行結點的估值l(X)≤c(X)≤u(X)。FIFOBB-JS(T,l,u,

,cost)

1 E

T

2 Parent(E)

0

3 ifT

是解結點

4

thenUp

min{cost(T),u(T)+

}

5

ans

T

6

elseUp

u(T)+

7 ans

0

8 Q

//初始化隊列為空

9 while(1)do10

forE的每個子結點Xdo//對當前E結點進行擴展

11

ifl(X)<Up

12 thenINSERTQ(X)

13

Parent(X)

E

14

if

X

是解結點&cost(X)<Up

15

thenUp

min{cost(X),u(X)+

}

16

ans

X

17

if

u(X)+

<Up

18

thenUp

u(X)+

19

while(1)do

20 ifEmpty(Q)//如果隊列Q為空

21

thenprint(“leastcost=”,Up)

22

while

ans

0do

23

print(ans)

24

ans

Parent(ans)

25

return//返回

26 EXTRACTQ(X)

27 ifl(X)<Up

28

then

exit//殺死l(X)

Up的結點，退出第19行的while循環體第1～8行進行初始化。第10行擴展E的每個子結點X。第11行，如果l(X)<Up，調用INSERTQ，將E