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

第5章回溯法5.1回溯法的基本原理

5.2

n皇后問(wèn)題

5.3子集和數(shù)問(wèn)題

5.4

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

5.5著色問(wèn)題

習(xí)題 5.1回溯法的基本原理

回溯法(backtracking)是一種系統(tǒng)地搜索問(wèn)題解的方法。為了實(shí)現(xiàn)回溯，首先需要為問(wèn)題定義一個(gè)解空間(solutionspace)，這個(gè)空間必須至少包含問(wèn)題的一個(gè)解(可能是最優(yōu)

的)。在一般的情況下，我們會(huì)將問(wèn)題的解表示成一個(gè)向量X＝(x1,x2,…,xn)，其中元素xi∈Si。通常，需要找出滿足某一約束條件且使某一規(guī)范函數(shù)取最大值(或最小值)的解向量。這樣的一個(gè)向量可能表示一種排列，其中xi表示排列的第i個(gè)元素,或者表示對(duì)于給定集合S，xi為真，當(dāng)且僅當(dāng)?shù)趇個(gè)元素在集合Si中。我們稱滿足問(wèn)題約束條件的解為可行解(feasiblesolution)?；厮菟惴ㄒ淮螖U(kuò)展一個(gè)元素。在回溯算法的每一步中，假定我們已經(jīng)構(gòu)造了問(wèn)題的部分解，如問(wèn)題解向量的前k個(gè)元素，k≤n。通過(guò)這個(gè)部分解(x1,x2,…,xk)，我們要構(gòu)造第k+1個(gè)位置上可能的候選解集合Sk+1，然后通過(guò)在向量最后添加另一元素來(lái)對(duì)當(dāng)前解進(jìn)行擴(kuò)展，以得到更長(zhǎng)的一個(gè)部分解。在對(duì)部分解進(jìn)行擴(kuò)展之后，我們必須檢查到目前為止的解是否是問(wèn)題的一個(gè)解，如果是問(wèn)題的解，則輸出；否則，我們需要檢查這個(gè)部分解是否可以繼續(xù)擴(kuò)展成為問(wèn)題的解。如果可以，則進(jìn)行遞歸調(diào)用并繼續(xù)這一過(guò)程；如果不可以繼續(xù)擴(kuò)展，則從x中刪除最后添加的元素，并再嘗試這個(gè)位置是否存在另一元素。然而，在某些點(diǎn)上，Sk+1可能為空，即不存在合法的方式對(duì)當(dāng)前解進(jìn)行擴(kuò)展。如果是這樣，我們必須進(jìn)行回溯(backtrack)，用Sk中的下一候選解代替xk，即部分解中的最后一項(xiàng)。這就是回溯方法的由來(lái)，過(guò)程BACKTRACKING描述了這一思想。BACKTRACKING(X)

1 計(jì)算解X的第一個(gè)元素的候選集合S1

2 k

1

3 while

k>0do//擴(kuò)展

4

while

Sk

do//第k個(gè)元素的候選解不空

5

xk

Sk中的下一元素

6

Sk

Sk–{xk}

7

ifX=(x1,x2,…,xk)是問(wèn)題的解

8

then輸出

9 k

k+1

10 計(jì)算解X的第k個(gè)元素的候選集合Sk

11

k

k

–1//回溯

12 return回溯法構(gòu)造了問(wèn)題部分解的一棵樹(shù)，樹(shù)中的每個(gè)結(jié)點(diǎn)都是問(wèn)題的一個(gè)部分解。如果結(jié)點(diǎn)y是由結(jié)點(diǎn)x直接擴(kuò)展的，那么x與y之間有一條邊。我們可以從部分解所構(gòu)成的樹(shù)來(lái)更深

刻地理解回溯的本質(zhì)，因?yàn)榻獾臉?gòu)造過(guò)程正好對(duì)應(yīng)于深度優(yōu)先遍歷樹(shù)的過(guò)程。將回溯過(guò)程看做深度優(yōu)先搜索，自然會(huì)產(chǎn)生這個(gè)基本算法的遞歸過(guò)程BACKTRACKING-DFS。BACKTRACKING-DFS(X,k)

1 ifX=(x1,x2,…,xk)是問(wèn)題的解，

2 then輸出

3 else

4

k

k+1

5 計(jì)算解X的第k個(gè)元素的候選集合Sk

6

while

Sk

do//第k個(gè)元素的候選解不空

7 xk

Sk中的下一元素

8 Sk

Sk–{xk}

9 BACKTRACKING-DFS(X,k)

10 return

1.子集樹(shù)的構(gòu)造

當(dāng)所給的問(wèn)題是從n個(gè)元素的集合中找出滿足某種性質(zhì)的子集時(shí)，相應(yīng)的解空間樹(shù)稱為子集樹(shù)(subsettree)。在組合優(yōu)化問(wèn)題求解中，常常用到子集樹(shù)的概念。例如，對(duì)于n個(gè)

元素的整數(shù)集{1,2,…,n}，n=1時(shí)，只有兩個(gè)子集，即{}和{1}；n=2時(shí)，有4個(gè)子集；n=3時(shí)，有8個(gè)子集。每增加一個(gè)新元素，都使子集個(gè)數(shù)加倍，因此對(duì)于n個(gè)元素，有2n個(gè)子集。又例如，0-1背包問(wèn)題對(duì)應(yīng)的解空間就是一棵子集樹(shù),樹(shù)中所有結(jié)點(diǎn)都可能成為問(wèn)題的一個(gè)解。子集樹(shù)中至多有2n個(gè)葉結(jié)點(diǎn)。n=3時(shí),子集樹(shù)如圖5-1所示。因此，任何算法遍歷子集樹(shù)所需的運(yùn)行時(shí)間為Ω(2n)。圖5-1

0-1背包問(wèn)題的子集樹(shù)(n=3)為了構(gòu)造所有2n個(gè)子集，我們可以建立一個(gè)有n個(gè)單元的數(shù)組或向量，其中xi的值或?yàn)檎婊驗(yàn)榧?表明xi是否屬于某個(gè)給定子集。利用回溯算法中候選解的表示可得，Sk=(true,false)。當(dāng)k≥n時(shí)，X是問(wèn)題的解。

利用狀態(tài)空間表示法，回溯算法在構(gòu)造集合{1,2,3}的子集過(guò)程中將產(chǎn)生以下部分解序列：

{1}→{1,2}→{1,2,3}*→{1,2,－}*→{1,－}→{1,－,3}*→{1,－,－}*→{1,－}→{1}→{－}→{－,2}→{－,2,3}*→{－,2,－}*→{－,－}→{－,－,3}*→{－,－,－}*→{－,－)→{－}→{}其中，“*”表示完整子集,部分解中的“－”表示這個(gè)位置不選。第i個(gè)位置為真，則用i自身表示。

通過(guò)這個(gè)例子，我們能夠更好地理解回溯的過(guò)程。集合{1,2,3}的子集樹(shù)如圖5-2所示。圖5-2集合{1,2,3}的子集樹(shù)

2.排列樹(shù)的構(gòu)造

當(dāng)所給的問(wèn)題是從n個(gè)元素的集合中找出滿足某種性質(zhì)的排列時(shí)，相應(yīng)的解空間樹(shù)稱為排列樹(shù)(permutationtree)。

這樣的計(jì)算給出了一種合適的表示方式。為了構(gòu)造出所有n!種排列，可以設(shè)一個(gè)具有n個(gè)元素的數(shù)組。第k個(gè)位置的候選解的集合就是那些不在前k－1個(gè)元素的部分解中出現(xiàn)的元素集合，因此，Sk={1,2,…,n}－X。當(dāng)k=n+1時(shí)，向量X

就是問(wèn)題的解。通過(guò)這種表示方法，將按照如下次序產(chǎn)生{1,2,3}的排列：

{1}→(1,2)→{1,2,3}*→{1,2}→{1}→{1,3}→{1,3,2}*

→{1,3}→{1}→{}→{2}→{2,1}→{2,1,3}*→{2,1}→{2}→{2,3}→{2,3,1}*→{2,3}→{2}→{}→{3}→{3,1}→{3,1,2}*→{3,1}→{3}→{3,2}→{3,2,1}*→{3,2}→{3}→{}

3.搜索樹(shù)的構(gòu)造

枚舉出給定圖中從源點(diǎn)s到t的所有路徑要比列出所有排列或者子集的問(wèn)題更復(fù)雜一些。不像上述的例子，沒(méi)有關(guān)于頂點(diǎn)或者邊個(gè)數(shù)的函數(shù)可用作計(jì)算問(wèn)題解的顯式公式，這是

因?yàn)槁窂降膫€(gè)數(shù)取決于給定圖的結(jié)構(gòu)。

由于到t的所有路徑的開(kāi)始點(diǎn)相同，因此S1={A}。第2個(gè)位置上候選解的集合是那些滿足(A,v)為圖中邊的結(jié)點(diǎn)集合。因此，對(duì)于路徑上的從一結(jié)點(diǎn)到另一結(jié)點(diǎn)的遍歷過(guò)程，可以利用邊定義合法步。一般而言，Sk+1由還未在部分解中出現(xiàn)的相鄰的頂點(diǎn)集組成。當(dāng)xk=t時(shí)，輸出問(wèn)題的解。我們必須設(shè)置解向量X的大小為n，盡管大多數(shù)路徑可能會(huì)比n小。圖5-3所示的搜索樹(shù)(searchingtree)給出了給定圖中從頂點(diǎn)A開(kāi)始的所有路徑。樹(shù)中的結(jié)點(diǎn)按照深度優(yōu)先搜索編號(hào)。圖5-3從頂點(diǎn)A開(kāi)始的所有簡(jiǎn)單路徑的搜索樹(shù) 5.2

n皇后問(wèn)題

1.8皇后問(wèn)題

我們給棋盤(pán)上的行和列從1到8編號(hào)，同時(shí)也給皇后從1到8編號(hào)。由于每一個(gè)皇后應(yīng)放在不同的行上，不失一般性，假設(shè)皇后i放在第i行上，因此8皇后問(wèn)題可以表示成8元組(x1,x2,…,x8)，其中xi(i=1,2,…,8)表示皇后i所放置的列號(hào)。這種表示法的顯式約束條件是Si={1,2,3,4,5,6,7,8}，i=1,2,…,8。在這種情況下，解空間由88個(gè)8元組組成，而隱式約束條件是沒(méi)有兩個(gè)xi相同(即所有皇后必須在不同列上)，且滿足不存在兩個(gè)皇后在同一條對(duì)角線上。加上隱式約束條件，問(wèn)題的解空間可進(jìn)一步減小。此時(shí)，解空間大小為8!，因?yàn)樗薪舛际?元組的一個(gè)置換。圖5-4表示了8皇后問(wèn)題的一個(gè)解。圖5-4

8皇后問(wèn)題的一個(gè)解我們可以用一棵樹(shù)表示8皇后問(wèn)題的解空間。由于8皇后問(wèn)題的解空間為8!種排列，因此我們將要構(gòu)造的這棵樹(shù)實(shí)際上是一棵排列樹(shù)。為了簡(jiǎn)單起見(jiàn)，圖5-5只給出了n=4時(shí)問(wèn)題的一種可能樹(shù)結(jié)構(gòu)。這棵樹(shù)有24個(gè)葉子結(jié)點(diǎn)，樹(shù)中結(jié)點(diǎn)按照深度優(yōu)先搜索編號(hào)，樹(shù)中的邊表示xi可能取的值。假定樹(shù)的根為第1層，樹(shù)中第1層到第2層的邊上的數(shù)字表示x1可能取的值。最左邊的子樹(shù)包含x1=1的所有解，最左子樹(shù)的左子樹(shù)包含x1=1且x2=1的所有解。第i層到第i+1層的邊上表示xi可能取的值。因此，從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的所有路徑定義了問(wèn)題的解空間。圖5-5

4皇后問(wèn)題解空間的樹(shù)結(jié)構(gòu)圖5-6表示4皇后問(wèn)題回溯時(shí)的部分狀態(tài)空間樹(shù)。圖中一個(gè)結(jié)點(diǎn)一旦被限界函數(shù)殺死，則用B做上記號(hào)。圖5-6具有限界函數(shù)的4皇后問(wèn)題的部分狀態(tài)空間樹(shù)

2.n皇后問(wèn)題及回溯算法

我們可以很容易地將8皇后問(wèn)題推廣到n皇后問(wèn)題(n-queenproblem)，即找出n×n的棋盤(pán)上放置n個(gè)皇后并使其不能互相攻擊的所有解。設(shè)X=(x1,x2,…,xn)表示問(wèn)題的解，其中xi表示第i個(gè)皇后放在第i行所在的列數(shù)。由于不存在兩個(gè)皇后位于同一列上，因此xi互不相同。設(shè)有兩個(gè)皇后分別位于棋盤(pán)(i,j)和(k,l)處，如果兩個(gè)皇后位于同一對(duì)角線上，則

表明它們所在的位置應(yīng)該滿足：i－j=k－l或i+j=k+l。綜合這兩個(gè)等式可得，如果兩個(gè)皇后位于同一對(duì)角線上，那么它們的位置關(guān)系一定滿足|j－l|=|i－k|。下面的算法N-QUEEN給出n皇后問(wèn)題的所有解。N-QUEEN(n)

1 x[1]

0 //第1個(gè)皇后的列位置初始化

2 k

1 //當(dāng)前行

3 whilek>0do

4

x[k]

x[k]+1 //到下一列

5

while

x[k]

n¬PLACE(k)do

6 x[k]

x[k]+1

7

if

x[k]

n //找到一個(gè)位置

8 thenif

k=n //測(cè)試是否為問(wèn)題的解

9

thenoutput(X)//輸出解

10

elsek

k+1//轉(zhuǎn)下一行，即給下一個(gè)皇后找位置

11 x[k]

0 //初始化當(dāng)前皇后列取值

12 elsek

k–1 //回溯

13 return第1～2行進(jìn)行初始化。第3行的while循環(huán)表示對(duì)所有行執(zhí)行循環(huán)體，計(jì)算xk值。在第5～6行的while循環(huán)中，對(duì)于每一個(gè)xk值，調(diào)用PLACE過(guò)程測(cè)試它的合法性,即尋找滿足約束條件的xk值。第7行中，如果找到一個(gè)放置位置，則進(jìn)一步測(cè)試所求(x1,x2,…,xk)是否為問(wèn)題的解，這只需判斷k是否等于n即可。如果是問(wèn)題的解，則輸出(第9行),否則通過(guò)賦值語(yǔ)句將k值增加1,繼續(xù)外層while循環(huán)。如果第7行的條件為假，則表明不存在合法的xk值，此時(shí)將k值減1(第12行)，進(jìn)行回溯。

PLACE過(guò)程如下：

PLACE(k)

1 i

1

2 whilei<k

do

3

if(x[i]=x[k]or

abs(x[i]

–x[k])=abs(i–k)//同一列或同一對(duì)角線有兩個(gè)皇后

4

thenreturnfalse

5

i

i+1

6 returntrue

PLACE過(guò)程檢測(cè)到目前為止的第k個(gè)皇后所在的列數(shù)xk,是否與前k－1個(gè)皇后所在列xi(1≤i≤k－1)在同一列或在同一對(duì)角線上(第3行)。如果這些條件都不違反，則返回true，否則返回false。

5.3子集和數(shù)問(wèn)題

1.子集和數(shù)問(wèn)題及回溯算法

子集和數(shù)問(wèn)題(subset-sumproblem)是指給定n個(gè)互不相同的正整數(shù)pi(1≤i≤n)及一個(gè)正數(shù)S,要求找出∑pi為S的所有子集。我們稱這種表示法為變長(zhǎng)元組表示法，如圖5-7所示。圖中結(jié)點(diǎn)按照廣度優(yōu)先搜索編號(hào)。在第i層與第i+1層的邊上表示pi被選中時(shí)的下標(biāo)，最左邊的子樹(shù)表示選中p1的所有子集，根的第2棵子樹(shù)則確定了選中p2但不選p1的所有子集，其中黑色結(jié)點(diǎn)表示答案結(jié)點(diǎn)。圖5-7子集和數(shù)問(wèn)題變長(zhǎng)元組表示法的子集樹(shù)結(jié)構(gòu)我們可以用另一種形式表示子集和數(shù)問(wèn)題。解的子集用n元組(x1,x2,…,xn)表示，其中每個(gè)xi∈{0,1}，1≤i≤n。如果pi未被選中，則xi為0，否則xi為1。這種表示法稱為定長(zhǎng)元組表示法。利用這種表示法，上述解又可表示為(1,1,0,0,1,0)、(1,0,1,1,0,0)和(0,0,1,0,0,1)。圖5-8表示了子集和數(shù)定長(zhǎng)元組表示法的子集樹(shù)結(jié)構(gòu)。圖中結(jié)點(diǎn)按照深度優(yōu)先搜索編號(hào)。在第i層與第i+1層的邊上表示pi被選中時(shí)的下標(biāo)，最左邊的子樹(shù)表示選中p1的所有子集，根的第2棵子樹(shù)則確定了選中p2但不選p1的所有子集，黑色結(jié)點(diǎn)表示答案結(jié)點(diǎn)。圖5-8子集和數(shù)問(wèn)題定長(zhǎng)元組表示法的子集樹(shù)結(jié)構(gòu)對(duì)于子集和數(shù)問(wèn)題定長(zhǎng)元組表示法，產(chǎn)生它的任一子結(jié)點(diǎn)是較容易的。對(duì)于第i層上的一個(gè)結(jié)點(diǎn)，它的左孩子為xi=1，右孩子為xi=0。假定pi按照非降次序排列，限界函數(shù)可設(shè)計(jì)為

這兩個(gè)條件保證算法SUBSET-SUM可以找到問(wèn)題的解。SUBSET-SUM(S,p,s,k,r) //前k－1個(gè)xi值已確定

1 x[k]

1 //生成左孩子

2 ifs+p[k]=S //如果條件為真，表明找到解

3 thenoutputx1,x2,…,xk,0,…,0//輸出問(wèn)題解

4 elseifs+p[k]

+p[k+1]

S //測(cè)試遞歸調(diào)用的條件

5 thenSUBSET-SUM(S,p,s+p[k],k+1,r－p[k]) //前k個(gè)xi值已確定,且xk

1

6 ifs+r–p[k]

Sands+p[k+1]

S //生成右孩子

7 then

x[k]

0

8

SUBSET-SUM(S,p,s,k+1,r－p[k])//前k個(gè)xi值已確定，且xk

0

9 return

2.子集和數(shù)問(wèn)題算法示例

圖5-9顯示本小節(jié)例子n=6，(p1,p2,p3,p4,p5,p6)=(5,10,12,13,15,18)，S=30，運(yùn)行算法SUBSET-SUM后，所生成狀態(tài)空間樹(shù)的部分結(jié)果。初始時(shí)，s=0，k=1，r= 圖5-9算法SUBSET-SUM所生成狀態(tài)空間樹(shù)的一部分回溯法的一般執(zhí)行步驟如下：

(1)定義一個(gè)解空間，它包含問(wèn)題的解。

(2)用適于搜索的方式組織該空間。

(3)用深度優(yōu)先法搜索該空間，利用限界函數(shù)來(lái)避免移動(dòng)到不可能產(chǎn)生解的子空間。

5.4

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

1.0-1背包問(wèn)題及回溯算法示例

再次考慮0-1背包問(wèn)題(0-1knapsackproblem)。某商店有n個(gè)物品，第i個(gè)物品價(jià)值為vi，重量(或稱權(quán)值)為wi，其中vi和wi為非負(fù)數(shù)。背包的容量為W，W為一非負(fù)數(shù)。目標(biāo)是如何選擇裝入背包的物品，使裝入背包的物品總價(jià)值最大?？蓪⑦@個(gè)問(wèn)題形式描述為

約束條件為我們使用定長(zhǎng)元組表示法。如果在結(jié)點(diǎn)Z處，已經(jīng)確定了xi的值，1≤i≤k,則可在條件0≤xi≤1下，用第4章中的貪心算法求解結(jié)點(diǎn)Z處的解作為限界函數(shù)BOUND，k+1≤i≤n。

BOUND(cv,cw,k,W)//k:上次去掉的物品

1 b

cv//cv:當(dāng)前價(jià)值總量

2 c

cw//cw:當(dāng)前背包占用權(quán)值

3 fori

k+1to

n

4

doc

c+w[k]

5

if

c<W

6 then

b

b+v[i]

7 elsereturn(b+(1–(c–W)/w[i])v[i])第1～2行進(jìn)行初始化。第3～7行的while循環(huán)計(jì)算背包獲得的價(jià)值。第7行中1－(c－W)/wi表示最后放入背包的物品比例。

由算法BT-KNAPSACK可見(jiàn)，只有在經(jīng)過(guò)一系列左孩子結(jié)點(diǎn)之后，才需要調(diào)用限界過(guò)程BOUND。

BT-KNAPSACK(W,n,w,v,fw,fv,X)

1 cw

cv

0//cw：背包當(dāng)前已用權(quán)值，cv：背包當(dāng)前總價(jià)值

2 k

1

3 fv

–1//fv：背包的最大值，初始化為–1

4 do

5

while

k

nandcw+w[k]

W

do//測(cè)試物品k是否可以放入背包

6 cw

cw+w[k]//修改當(dāng)前背包已用權(quán)值cw

7 cv

cv+v[k]//修改當(dāng)前背包總價(jià)值cv

8 y[k]

1//做左孩子結(jié)點(diǎn)的移動(dòng)

9 k

k+1//繼續(xù)考慮下一個(gè)物品

10

if

k>n//如果所有物品考慮過(guò)(退出循環(huán)后)

11

then

fv

cv//復(fù)制這個(gè)解產(chǎn)生的總價(jià)值

12 fw

cw//復(fù)制這個(gè)解所占背包權(quán)值

13 k

n

14 X

Y//更新解

15

else

y[k]

0//最后放入背包中的物品k不合適，去掉

16

whileBOUND(cv,cw,k,W)

fvdo17

while

k

0andy[k]

1do

18

k

k–1//找最后放入背包的物品

19

if

k=0

20

thenreturn//算法返回

21

y[k]

0//做右孩子結(jié)點(diǎn)的移動(dòng)

22

cw

cw–w[k]//修改當(dāng)前背包占用權(quán)值

23

cv

cv–v[k]//修改當(dāng)前背包總價(jià)值

24

k

k+1

25 whiletrue圖5-10顯示了由算法BT-KNAPSACK所生成的狀態(tài)空間樹(shù)。這棵樹(shù)的第i層和第i+1層之間的邊上表示yi的取值，1表示沿左孩子結(jié)點(diǎn)的移動(dòng)，0表示沿右孩子結(jié)點(diǎn)移動(dòng)。結(jié)點(diǎn)內(nèi)的數(shù)值分別表示權(quán)值cw和價(jià)值cv。注意，右孩子結(jié)點(diǎn)的權(quán)值和價(jià)值與其父結(jié)點(diǎn)相同，在此略去。根及右孩子結(jié)點(diǎn)外的值為該處結(jié)點(diǎn)的上界。左孩子結(jié)點(diǎn)的上界與父結(jié)點(diǎn)相同。算法BT-KNAPSACK中的變量fv在結(jié)點(diǎn)A、B、C以及D處被更新，在對(duì)fv更新的同時(shí)更新解X。算法返回時(shí)，fv=159，X=(1,1,1,0,1,1,0,0)。圖5-10由算法BT-KNAPSACK所生成的狀態(tài)空間樹(shù)

2.改進(jìn)算法

我們可以對(duì)算法BT-KNAPSACK做進(jìn)一步改進(jìn)。由于vi(1≤i≤n)是整數(shù)，因此BOUND值向下取整是一個(gè)更好的限界函數(shù)，如果這樣，圖5-10中的結(jié)點(diǎn)E和F就不需要擴(kuò)展，從而進(jìn)一步減少生成結(jié)點(diǎn)數(shù)。對(duì)BOUND算法也可進(jìn)行改進(jìn)，使得算法BOUND不必重復(fù)算法BT-KNAPSACK中第5～9行的工作。改進(jìn)的算法如下：IMPROVED-BOUND(cv,cw,k,W,vcv,wcw,i)

1 vcv

cv//cv:當(dāng)前價(jià)值總量

2 wcw

cw//cw:背包剩余可用量

3 fori

k+1to

n

4

do

if

wcw+w[i]

W

5

thenwcw

wcw+w[i]

6 vcv

vcv+v[i]

7 y[k]

1

8

elsereturn(vcv+(W–wcw)(v[i]

/w[i]))IMPROVED-BT-KNAPSACK(W,n,w,v,fw,fv,X)

1 cw

cv

0 //cw：背包當(dāng)前權(quán)值，cv：背包當(dāng)前總價(jià)值

2 k

0

3 fv

–1 //fv：背包的最大值，初始化為–1

4 do

5

whileIMPROVED-BOUND(ccv,ccw,k,W,vcv,wcw,i)

fp

do

6

while

k

0andy[k]

1do

7

k

k–1//找最后放入背包的物品

8

if

k=0

9 thenreturn//算法返回

10

y[k]

0 //做右孩子結(jié)點(diǎn)的移動(dòng)

11

cw

cw–w[k] //修改當(dāng)前背包權(quán)值12

cv

cv–v[k] //修改當(dāng)前背包總價(jià)值

13

ccv

vcv

14

ccw

wcw

15

k

j

16

if

k>n//如果所有物品考慮過(guò)(退出第5行的循環(huán)后)

17 then

fv

cv//復(fù)制這個(gè)解產(chǎn)生的總價(jià)值

18

fw

cw//復(fù)制這個(gè)解所占背包權(quán)值

19

k

n

20

X

Y//更新解

21 else

y[k]

0//最后放入背包中的物品k不合適，去掉

22 while(1)

5.5著色問(wèn)題

若一個(gè)圖已經(jīng)畫(huà)在曲面S上而任何兩條邊都不相交，則稱該圖被嵌入(embedded)曲面S內(nèi)。如果一個(gè)圖被嵌入一個(gè)平面內(nèi)，則稱它是可平面的。嵌入到平面內(nèi)的圖稱為平面圖(planargraph)。例如，圖5-11為一個(gè)可平面圖和它的一種嵌入。圖5-11一個(gè)可平面圖和它的一種嵌入給定圖G=(V,E)和k種顏色，設(shè)計(jì)算法來(lái)給出這個(gè)圖的所有k可著色方案，否則輸出該圖不是k可著色的。假定用鄰接矩陣Adj［1..n,1..n］表示圖G。如果(i,j)是圖G中的一條邊，那么Adj［i,j］=1；否則，Adj［i,j］=0。因?yàn)榻獾臉?gòu)造過(guò)程正好對(duì)應(yīng)深度優(yōu)先遍歷樹(shù)的過(guò)程，因此可把回溯過(guò)程看做深度優(yōu)先搜索，對(duì)5.1節(jié)描述的BACKTRACKING-DFS稍作修改，就可得圖的k著色算法K-COLORING。其中，顏色用正整數(shù)1,2,…,k表示，(x1,x2,…,xn)表示解向量。算法產(chǎn)生的狀態(tài)空間樹(shù)中，除根所在層之外，每一層有k個(gè)結(jié)點(diǎn)，表示xi有k種顏色可用。樹(shù)的高度為n+1。第i層與第i+1層之間的邊上表示xi可用的顏色。算法K-COLORING產(chǎn)生一個(gè)圖的所有k著色解。K-COLORING(i,k)

1 fori

1to

n

do

2 x[i]

0//初始化

3 do

4 GENERATE-COLOR(i,k)

5 if

x[i]=0thenbreak//退出dowhile循環(huán)

6 if

i=n

7 thenoutput(X)

8 elseGENERATE-COLOR(i+1,k)

9 whiletrue

10 return//算法返回GENERATE-COLOR(i,k)

1 do

2 x[i]

(x[i]+1)mod(k+1)//已用掉i-1種顏色

3 ifx[i]=0return//未找到顏色，算法返回

4 for

j

1to

n

do

5 ifAdj[i,j]&x[i]=x[j]

6 thenbreak//退出for循環(huán)

7 ifj=n+1

8 thenreturn//為x[i]找到一種顏色，算法返回

9 while(1)//試圖找另一種顏色圖5-12(a)給出了4個(gè)頂點(diǎn)的平面圖，圖5-12(b)給出了由算法K-COLORING(1,3)生成的所有可能的3著色。圖5-12算法K-COLORING示例

習(xí)題

5-1解釋術(shù)語(yǔ)：狀態(tài)空間、答案狀態(tài)、活結(jié)點(diǎn)、E結(jié)點(diǎn)、死結(jié)點(diǎn)和限界函數(shù)。

5-2旅行商問(wèn)題(travellingsalesmanproblem)。旅行商問(wèn)題的基本描述為：某旅行商要到若干村莊售貨，各村莊之間的路程是給定的。為了提高效率，旅行商決定從所在商店

出發(fā)，到每個(gè)村莊售一次貨，然后返回村商店。問(wèn)他應(yīng)選擇一條什么路線才能使所走的總路程最短。形式描述為：給定有向圖G=(V,E)，邊成本為cij，且如果(i,j)∈E，則cij>0，否則cij=∞。令|V|=n，假定n>1。G的一條周游路線包含V中每個(gè)頂點(diǎn)的一個(gè)有向環(huán)。周游路線的成本是此路線上所有邊上的成本和。求旅行商問(wèn)題的具有最小成本的周游路線。

(1)將旅行商問(wèn)題的解空間組織成一棵樹(shù)。

(2)編寫(xiě)一個(gè)回溯算法，搜索旅行商問(wèn)題的所有解(可行排列)。

5-3裝箱問(wèn)題(binpacking)。有一批共n個(gè)集裝箱要裝上兩艘載重量分別為c1和c2的輪船，其中集裝箱i的重量為wi，且滿足 。裝箱問(wèn)題要求確定，是否有一個(gè)合理的裝載方案可將這n個(gè)集裝箱裝上這兩艘輪船。試設(shè)計(jì)該問(wèn)題的回溯算法，并分析問(wèn)題的復(fù)雜度。

5-4給定無(wú)向圖G=(V,E)，如果U

V，且對(duì)任意u，v∈U，有(u,v)∈E，則稱U是G的一個(gè)完全子圖。G的完全子圖U是G的一個(gè)團(tuán)，當(dāng)且僅當(dāng)U不包含G的更大完全子圖。G的最大團(tuán)是指G中所含頂點(diǎn)數(shù)最多的團(tuán)。試設(shè)計(jì)求最大團(tuán)問(wèn)題的回溯算法。

5-5最小頂點(diǎn)覆蓋問(wèn)題(minimumvertex-coverproblem)。給定無(wú)向圖G＝(V,E)，當(dāng)且僅當(dāng)對(duì)于G中的每一條邊(u,v)∈E，u或v在U中時(shí)，G的頂點(diǎn)子集U是一個(gè)頂點(diǎn)覆蓋

(vertexcover),U中頂點(diǎn)的個(gè)數(shù)是覆蓋的大小,U中頂點(diǎn)個(gè)數(shù)最少的覆蓋為最小覆蓋。在圖5-12(a)中，{1,3}是大小為2的一個(gè)頂點(diǎn)覆蓋。試設(shè)計(jì)求最小覆蓋問(wèn)題的回溯算法，并分析算法的運(yùn)行時(shí)間。

5-6機(jī)器設(shè)計(jì)問(wèn)題。某機(jī)器由n個(gè)部件組成，每一個(gè)部件可從m個(gè)供應(yīng)商那里購(gòu)得。設(shè)wij是從供應(yīng)商j那里購(gòu)得的零件i的重量，cij為該零件的成本。試設(shè)計(jì)一個(gè)回溯算法，給出總成本不超過(guò)c的最小重量機(jī)器設(shè)計(jì)，并分析算法的復(fù)雜度。

5-7網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題。輸油網(wǎng)絡(luò)問(wèn)題可表示為一個(gè)加權(quán)有向無(wú)環(huán)圖G,G中有一個(gè)稱為源點(diǎn)的頂點(diǎn)s。從s出發(fā)，汽油被輸送到圖中的其他頂點(diǎn)。s的入度為0，每一條邊上的權(quán)給出了它所連接的兩點(diǎn)間的距離。網(wǎng)絡(luò)中的油壓是距離的函數(shù)，隨著距離的增大而減小。為了保證整個(gè)輸油網(wǎng)絡(luò)正常工作，需要維持網(wǎng)絡(luò)中的最低油壓Pmin，為此