《算法設(shè)計與分析》課件第6章

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

6.2

0-1背包問題

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

習(xí)題

6.1分枝限界法的基本思想

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

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

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

約束條件為

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

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

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

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

6.2

0-1背包問題

1．限界

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

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

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

通過構(gòu)造和設(shè)計結(jié)點(diǎn)處的限界函數(shù)，可以減小問題的狀態(tài)搜索空間。為了討論方便起見，我們將最大值優(yōu)化問題轉(zhuǎn)變成最小值優(yōu)化問題。如果用目標(biāo)函數(shù)－ 替代目標(biāo)函數(shù) ，就使背包問題從一個最大值優(yōu)化問題變成最小值優(yōu)化問題。顯然， 取最小即 取最大。重新定義了目標(biāo)函數(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)先隊(duì)列分枝限界法示例

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

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

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

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

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

1)結(jié)點(diǎn)的結(jié)構(gòu)

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

2)擴(kuò)展給定E結(jié)點(diǎn)的子結(jié)點(diǎn)

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

當(dāng)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é)點(diǎn)

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

4)活結(jié)點(diǎn)表的數(shù)據(jù)結(jié)構(gòu)

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

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

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

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

的值和最優(yōu)解。算法INIT對可用結(jié)點(diǎn)表和活結(jié)點(diǎn)表初始化。算法GETNODE取一個可用結(jié)點(diǎn)。算法EXTRACT-MAX從活結(jié)點(diǎn)表中摘取一個具有最大UB值的結(jié)點(diǎn)作為E結(jié)點(diǎn)，用最大堆實(shí)現(xiàn)時即摘取堆頂結(jié)點(diǎn)。LUBOUND(v,w,cw,cv,

n,k,LBB,UBB)

//cw表示背包可用權(quán)值，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é)點(diǎn)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)

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

)

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

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

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é)點(diǎn)

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é)點(diǎn)

21

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

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

23 Lower

max{Lower,LBB–

}

24

if

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

循環(huán)

25

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

26 while(UB(E)>Lower)

27 PRINT(Lower,ans,n)

6．0-1背包問題先進(jìn)先出分枝限界算法

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

0-1FIFO分枝限界樹

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

FIFOBB算法中結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)

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

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

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

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

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

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

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

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

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

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

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

在結(jié)點(diǎn)5處，有

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

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

結(jié)點(diǎn)7被殺死。

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

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

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

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

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

,cost)

1 E

T

2 Parent(E)

0

3 ifT

是解結(jié)點(diǎn)

4

thenUp

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

}

5

ans

T

6

elseUp

u(T)+

7 ans

0

8 Q

//初始化隊(duì)列為空

9 while(1)do10

forE的每個子結(jié)點(diǎn)Xdo//對當(dāng)前E結(jié)點(diǎn)進(jìn)行擴(kuò)展

11

ifl(X)<Up

12 thenINSERTQ(X)

13

Parent(X)

E

14

if

X

是解結(jié)點(diǎn)&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)//如果隊(duì)列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é)點(diǎn)，退出第19行的while循環(huán)體第1～8行進(jìn)行初始化。第10行擴(kuò)展E的每個子結(jié)點(diǎn)X。第11行，如果l(X)<Up，調(diào)用INSERTQ，將E