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

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

6.2

0-1背包問(wèn)題

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

習(xí)題

6.1分枝限界法的基本思想

如果把回溯法看做深度優(yōu)先搜索解空間樹(shù)的過(guò)程，那么分枝限界法則可看做廣度優(yōu)先或者按照最大價(jià)值(或最小成本)搜索解空間樹(shù)的過(guò)程。它也是一種系統(tǒng)地搜索問(wèn)題解的方法。按照從活結(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背包問(wèn)題為例，討論這兩種分枝限界法的異同。某商店有n個(gè)物品，第i個(gè)物品價(jià)值為vi，容量(或稱權(quán)值)為wi，其中vi和wi為非負(fù)數(shù)。背包的容量為W，W為一非負(fù)數(shù)。目標(biāo)是如何選擇裝入背包的物品，使裝入背包的物品總價(jià)值最大。這個(gè)問(wèn)題的形式描述如下：

約束條件為

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

對(duì)于0-1背包問(wèn)題，結(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ì)列的先后順序選擇下一個(gè)擴(kuò)展結(jié)點(diǎn)，得到0-1背包問(wèn)題先進(jìn)先出狀態(tài)空間樹(shù)，如圖6-1所示。圖6-1先進(jìn)先出狀態(tài)空間樹(shù)

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

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

6.2

0-1背包問(wèn)題

1．限界

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

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

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

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

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

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

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

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

由此可見(jiàn)，通過(guò)限界函數(shù)，大大減小了問(wèn)題的搜索空間，提高了算法的效率。但另一方面，僅從路徑10,7,4,2,1不能確定哪些物品裝入背包，使得－∑vixi=Up,即不能確定裝入背包中物品xi的取值情況。因此，在實(shí)現(xiàn)中，需通過(guò)設(shè)置一些變量來(lái)記錄xi的取值信息。一種辦法是在每一個(gè)結(jié)點(diǎn)上增設(shè)一個(gè)標(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)取決于用定長(zhǎng)元組表示狀態(tài)空間樹(shù)，還是用變長(zhǎng)元組表示狀態(tài)空間樹(shù)。這里仍然采用定長(zhǎng)元組表示。活結(jié)點(diǎn)表中的每一個(gè)結(jié)點(diǎn)都有六個(gè)域的信息，如圖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的兩個(gè)子結(jié)點(diǎn)。當(dāng)且僅當(dāng)CW(X)≥wLevel(X)時(shí)，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)時(shí)，生成X的右孩子Y，在這種情況下，有

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

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

3)識(shí)別答案結(jié)點(diǎn)

答案結(jié)點(diǎn)的識(shí)別比較容易，當(dāng)且僅當(dāng)Level(X)=n+1時(shí)，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í)行三個(gè)操作：判定優(yōu)先隊(duì)列是否為空、向優(yōu)先隊(duì)列中插入結(jié)點(diǎn)(類似于過(guò)程INSERT，見(jiàn)4.4節(jié))和從優(yōu)先隊(duì)列中摘取具有最小l(X)值的結(jié)點(diǎn)(類似于過(guò)程EXTRACT-MIN，見(jiàn)4.4節(jié))。我們用最小堆實(shí)現(xiàn)優(yōu)先隊(duì)列數(shù)據(jù)結(jié)構(gòu)，如果堆中有n個(gè)結(jié)點(diǎn)，則判斷優(yōu)先隊(duì)列是否為空的操作可在常數(shù)時(shí)間

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

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

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

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

n,k,LBB,UBB)

//cw表示背包可用權(quán)值，cv表示已得價(jià)值，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)//生成一個(gè)新結(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中使用了一個(gè)小的正參數(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)//下一個(gè)E結(jié)點(diǎn)是UB中最大的結(jié)點(diǎn)

26 while(UB(E)>Lower)

27 PRINT(Lower,ans,n)

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

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

0-1FIFO分枝限界樹(shù)

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

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

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

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

圖6-7表示變長(zhǎng)元組表示的狀態(tài)空間樹(shù)，結(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是問(wèn)題的最優(yōu)解，它是惟一的最小成本答案結(jié)點(diǎn)，此時(shí)，最優(yōu)解為J={2,3}，罰金為16，即最小成本。對(duì)于這棵樹(shù)中的結(jié)點(diǎn)，定義成本函數(shù)c(*)如下：對(duì)于不可行結(jié)點(diǎn)(陰影結(jié)點(diǎn))，c(X)=+∞；對(duì)于其他結(jié)點(diǎn)，c(X)定義為根為X的子樹(shù)中結(jié)點(diǎn)的最小罰金。在圖6-7中，c(1)=16，c(2)=18，c(3)=16。圖6-7變長(zhǎng)元組對(duì)應(yīng)的狀態(tài)空間樹(shù)

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

我們利用FIFOBB求解作業(yè)調(diào)度問(wèn)題，假設(shè)利用圖6-7中的變長(zhǎng)元組表示法。初始時(shí)，設(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成為下一個(gè)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成為下一個(gè)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成為下一個(gè)E結(jié)點(diǎn)，生成它的子結(jié)點(diǎn)11和12。結(jié)點(diǎn)11和12都為不可行結(jié)點(diǎn)，均被殺死。結(jié)點(diǎn)9成為下一個(gè)E結(jié)點(diǎn)，生成它的子結(jié)點(diǎn)13。結(jié)點(diǎn)13為不可行結(jié)點(diǎn)，被殺死。因此，結(jié)點(diǎn)9為最小成本答案結(jié)點(diǎn)，成本為16，問(wèn)題的解J={2,3}。

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

過(guò)程FIFOBB-JS描述了找最小成本答案結(jié)點(diǎn)的作業(yè)調(diào)度問(wèn)題的算法。過(guò)程中調(diào)用了兩個(gè)子過(guò)程，它們是INSERTQ(X)和EXTRACTQ(X)，分別表示向隊(duì)列插入一個(gè)結(jié)點(diǎn)和從隊(duì)列中刪除一個(gè)結(jié)點(diǎn)。對(duì)于狀態(tài)空間樹(shù)中的每個(gè)答案結(jié)點(diǎn)X，cost(X)是結(jié)點(diǎn)X對(duì)應(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的每個(gè)子結(jié)點(diǎn)Xdo//對(duì)當(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的每個(gè)子結(jié)點(diǎn)X。第11行，如果l(X)<Up，調(diào)用INSERTQ，將E