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

6.2

0-1背包問題

6.3作業(yè)調(diào)度問題

習題

6.1分枝限界法的基本思想

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

(1)先進先出(FirstInFirstOut，F(xiàn)IFO)分枝限界法(FIFOBB)。

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

約束條件為

1．先進先出狀態(tài)空間樹

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

2．優(yōu)先隊列狀態(tài)空間樹

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

6.2

0-1背包問題

1．限界

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

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

2．定義結(jié)點的限界函數(shù)

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

式(6.1)中各量的意義同6.1節(jié)。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背包問題優(yōu)先隊列分枝限界法示例

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

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

0-1背包問題優(yōu)先隊列分枝限界樹

4．算法中使用的主要數(shù)據(jù)結(jié)構及變量

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

1)結(jié)點的結(jié)構

結(jié)點結(jié)構取決于用定長元組表示狀態(tài)空間樹，還是用變長元組表示狀態(tài)空間樹。這里仍然采用定長元組表示?；罱Y(jié)點表中的每一個結(jié)點都有六個域的信息，如圖6-4所示。圖6-4結(jié)點的數(shù)據(jù)結(jié)構

2)擴展給定E結(jié)點的子結(jié)點

利用結(jié)點數(shù)據(jù)結(jié)構中的信息，可以確定任一活結(jié)點X的兩個子結(jié)點。當且僅當CW(X)≥wLevel(X)時，X的左孩子Y是可行結(jié)點，可以生成結(jié)點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)識別答案結(jié)點

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

4)活結(jié)點表的數(shù)據(jù)結(jié)構

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

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

5．0-1背包問題優(yōu)先隊列分枝限界算法

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

的值和最優(yōu)解。算法INIT對可用結(jié)點表和活結(jié)點表初始化。算法GETNODE取一個可用結(jié)點。算法EXTRACT-MAX從活結(jié)點表中摘取一個具有最大UB值的結(jié)點作為E結(jié)點，用最大堆實現(xiàn)時即摘取堆頂結(jié)點。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)//生成一個新結(jié)點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)

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

)

1 INIT//初始化可用結(jié)點及活結(jié)點表

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

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)//葉結(jié)點

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)//右孩子是否成為活結(jié)點

21

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

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

23 Lower

max{Lower,LBB–

}

24

if

不存在活結(jié)點thenbreak//退出do…while

循環(huán)

25

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

26 while(UB(E)>Lower)

27 PRINT(Lower,ans,n)

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

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

0-1FIFO分枝限界樹

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

FIFOBB算法中結(jié)點的數(shù)據(jù)結(jié)構

6.3作業(yè)調(diào)度問題

1．定義結(jié)點的限界函數(shù)

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

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

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

2．作業(yè)調(diào)度問題FIFOBB算法示例

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

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

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

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

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

在結(jié)點5處，有

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

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

結(jié)點7被殺死。

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

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

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

3．作業(yè)調(diào)度問題FIFOBB-JS算法

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

,cost)

1 E

T

2 Parent(E)

0

3 ifT

是解結(jié)點

4

thenUp

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

}

5

ans

T

6

elseUp

u(T)+

7 ans

0

8 Q

//初始化隊列為空

9 while(1)do10

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

11

ifl(X)<Up

12 thenINSERTQ(X)

13

Parent(X)

E

14

if

X

是解結(jié)點&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(“l(fā)eastcost=”,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的結(jié)點，退出第19行的while循環(huán)體第1～8行進行初始化。第10行擴展E的每個子結(jié)點X。第11行，如果l(X)<Up，調(diào)用INSERTQ，將E