《數(shù)據(jù)結(jié)構(gòu)與算法分析》課件第9章

第9章搜索算法9.1回溯法9.2分支界限法

9.1回溯法

9.1.1回溯法的算法框架

1．問題的解空間

應(yīng)用回溯法求解問題時，首先應(yīng)明確定義問題的解空間，該解空間應(yīng)至少包含問題的一個最優(yōu)解。例如，對于有n種物品的0-1背包問題，其解空間由長度為n的0-1向量組成，該解空間包含了對變量的所有可能的0-1賦值。當(dāng)n=3時，其解空間是

{(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),

(1,1,0),(1,1,1)}在定義了問題的解空間后，還需要將解空間有效地組織起來，使得回溯法能方便地搜索整個解空間，通常將解空間組織成樹或圖的形式。例如，對于n=3的0-1背包問題，其解空間可以用一棵完全二叉樹表示，如圖9-1所示。從樹根到葉子結(jié)點的任意一條路徑可表示解空間中的一個元素，如從根結(jié)點A到結(jié)點J的路徑對應(yīng)于解空間中的一個元素(1,0,1)。圖9-10-1背包問題的解空間樹

2．回溯法的基本思想

確定了問題的解空間結(jié)構(gòu)后，回溯法將從開始結(jié)點(根結(jié)點)出發(fā)，以深度優(yōu)先的方式搜索整個解空間。開始結(jié)點成為活結(jié)點，同時也成為擴展結(jié)點。在當(dāng)前的擴展結(jié)點處，向縱深方向搜索并移至一個新結(jié)點，這個新結(jié)點就成為一個新的活結(jié)點，并成為當(dāng)前的擴展結(jié)點。如果在當(dāng)前的擴展結(jié)點處不能再向縱深方向移動，則當(dāng)前的擴展結(jié)點就成為死結(jié)點。此時應(yīng)往回移動(回溯)至最近的一個活結(jié)點處，并使其成為當(dāng)前的擴展結(jié)點?；厮莘ㄒ陨鲜龉ぷ鞣绞竭f歸地在解空間中搜索，直至找到所要求的解或解空間中已無活結(jié)點時為止。圖9-2四個頂點的無向帶權(quán)圖

圖9-3旅行售貨員問題的解空間樹綜上所述，運用回溯法解題的關(guān)鍵要素有以下三點：

(1)針對給定的問題，定義問題的解空間；

(2)確定易于搜索的解空間結(jié)構(gòu)；

(3)以深度優(yōu)先方式搜索解空間，并且在搜索過程中用剪枝函數(shù)避免無效搜索。

3．遞歸和迭代回溯

一般情況下可以用遞歸函數(shù)實現(xiàn)回溯法，遞歸函數(shù)模板如下：采用迭代的方式也可實現(xiàn)回溯算法，迭代回溯算法的模板如下：

4．子集樹與排列樹

圖9-1和圖9-3中的兩棵解空間樹是回溯法解題時常用的兩類典型解空間樹。

當(dāng)給定的問題是從n個元素的集合S中找出滿足某種性質(zhì)的子集時，相應(yīng)的解空間樹稱為子集樹。例如，n個物品的0-1背包問題所對應(yīng)的解空間樹是一棵子集樹，該類樹通常有2n個葉子結(jié)點，總結(jié)點數(shù)為2n+1-1，遍歷子集樹的任何算法需要的計算時間復(fù)雜度均為O(2n)。9.1.2最大團問題

1．問題描述

給定一個無向圖G=(V,E)，如果U

V，且對任意u,v∈U有(u,v)∈E，則稱U是G的一個完全子圖。G的完全子圖U是G的一個團當(dāng)且僅當(dāng)U不包含在G的更大的完全子圖中；G的最大團是指G中所含頂點數(shù)最多的團。(注：完全圖是全連通圖)。

在圖9-4中，子集?{1,2}?是G的一個大小為2的完全子圖，它不是一個團，原因是它包含于G的更大完全子圖?{1,2,5}?中；而?{1,2,5}?是G的一個最大團。同理，完全子圖?

{1,4,5}和?{2,3,5}?也是G的最大團。圖9-4無向圖G及其補圖G'

2．算法設(shè)計

無向圖G的最大團和最大獨立集問題都可以用回溯法在時間復(fù)雜度為O(n2n)以內(nèi)解決，且都可以看做圖G的頂點集

V的子集選取問題，因此可以用子集樹表示問題的解空間。9.1.3圖的m著色問題

1．問題描述

給定一個無向連通圖G和m種不同的顏色，用這些顏色為圖G的各頂點著色，每個頂點染一種顏色，那么是否存在一種著色方案使得相鄰頂點不重色。若一個圖至少需要m種顏色才能使圖中任何相鄰頂點不重色，則m稱為該圖的色數(shù)。求一個圖的色數(shù)m的問題稱為圖的m可著色優(yōu)化問題。

2．算法設(shè)計

對于任意一個圖G=(V,E)和m種顏色，如果這個圖不是m可著色的，則給出不能著色；如果這個圖是m可著色的，則找出所有不同的著色方案。圖9-5n=3和m=3時的解空間樹示意圖9.1.4旅行售貨員問題

設(shè)某旅行售貨員要到多個城市推銷商品，已知各城市之間的路程(旅費)，現(xiàn)在為其設(shè)計一條售貨路線，要求從某駐地出發(fā)經(jīng)過每個城市一遍，最后又回到駐地，且使總的路程(旅費)最小。

9.2分?支?界?限?法

9.2.1分支界限法的基本思想

分支界限法以廣度優(yōu)先或最小耗費(最大效益)優(yōu)先的方式搜索問題的解空間樹。常見的解空間樹有子集樹和排列樹。從活結(jié)點表中選擇下一個擴展結(jié)點作為當(dāng)前擴展結(jié)點，常用的方法有兩種：

(1)一般隊列方法。一般隊列方法是將活結(jié)點表組織成一般隊列，并按隊列中結(jié)點先進先出的原則選取下一個結(jié)點作為當(dāng)前擴展結(jié)點。

(2)優(yōu)先級隊列方法。優(yōu)先級隊列方法是將活結(jié)點表組織成一個優(yōu)先級隊列，并按優(yōu)先級隊列中規(guī)定的結(jié)點優(yōu)先級來選取優(yōu)先級最高的下一個結(jié)點作為當(dāng)前擴展結(jié)點。9.2.2裝載問題

設(shè)有n個集裝箱，計劃將其裝上兩艘載重量分別為c1和c2的輪船，其中集裝箱i的重量為wi，且wi≤c1+c2。那么是否有一個合理的裝載方案，可將n個集裝箱裝上這兩艘輪船。

當(dāng)wi=c1+c2時，裝載問題就等價于子集和問題；當(dāng)c1=c2，且wi=2c1時，裝載問題就等價于劃分問題。如果給定的裝載問題有解，則采用下面的策略可以得到一個最優(yōu)裝載方案：

(1)將第一艘輪船盡可能地裝滿；

(2)將剩余的集裝箱裝到第二艘輪船上。

第一艘輪船盡可能地裝滿等價于選取全體集裝箱的一個子集，使該子集中的集裝箱重量之和最接近c1。由此可知，裝載問題等價于以下特殊的0-1背包問題：

1．一般隊列分支界限法

求解裝載問題的一般隊列分支界限法只求出所要求的最優(yōu)值，最優(yōu)解將在后續(xù)內(nèi)容介紹。

2．算法改進

設(shè)bestw是當(dāng)前最優(yōu)解，Ew是當(dāng)前擴展結(jié)點對應(yīng)的重量，r是剩余集裝箱的重量。若Ew+r≤bestw，則可以將擴展結(jié)點所對應(yīng)的子樹剪去。

函數(shù)MaxLoading將bestw初始化為0，直至搜索到葉子結(jié)點時才更新bestw，因此在算法搜索到第一個葉子結(jié)點之前bestw=0，且r＞0，故Ew+r＞bestw總成立，即此時右子樹測試不起作用。

3．構(gòu)造最優(yōu)解

為了在算法結(jié)束后能方便地構(gòu)造出與最優(yōu)值相對應(yīng)的最優(yōu)解，算法必須記錄相應(yīng)子集樹中從活結(jié)點到根的路徑，為此，必須設(shè)置指向其雙親結(jié)點的指針，并設(shè)置左右孩子標志。9.2.3布線問題

印刷電路板將布線區(qū)域劃分成n?m個方格陣列，如圖

9-6(a)所示。電路布線問題要求確定連接方格a的中點和方格b的中點的最短布線方案。在布線時，電路只能沿直線或直角布線，并且要求所布線路不能相交，如圖9-6(b)所示。圖9-6印制電路板布線方格陣列在實現(xiàn)上述算法中，首先考慮記錄電路板上某方格的位置：用結(jié)構(gòu)體表示，結(jié)構(gòu)體中有row和col兩個成員。其次需要表示布線前進的方向：布線可沿右、下、左、上四個方向移動，分別用0、1、2、3表示。再用offset[i].row和offset[i].col(i=0,1,2,3)表示沿著四個方向移動一步時對于當(dāng)前方格的相對位移，如表9-1所示。在一個7×7方格陣列中布線的例子如圖9-7所示，其中，起始位置a=(3,2)；目標位置b=(4,6)；陰影方格表示被封鎖的