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

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

9.1回溯法

9.1.1回溯法的算法框架

1．問(wèn)題的解空間

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

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

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

2．回溯法的基本思想

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

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

(1)針對(duì)給定的問(wèn)題，定義問(wèn)題的解空間；

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

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

3．遞歸和迭代回溯

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

4．子集樹(shù)與排列樹(shù)

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

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

1．問(wèn)題描述

給定一個(gè)無(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)。(注：完全圖是全連通圖)。

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

{1,4,5}和?{2,3,5}?也是G的最大團(tuán)。圖9-4無(wú)向圖G及其補(bǔ)圖G'

2．算法設(shè)計(jì)

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

V的子集選取問(wèn)題，因此可以用子集樹(shù)表示問(wèn)題的解空間。9.1.3圖的m著色問(wèn)題

1．問(wèn)題描述

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

2．算法設(shè)計(jì)

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

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

9.2分?支?界?限?法

9.2.1分支界限法的基本思想

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

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

(2)優(yōu)先級(jí)隊(duì)列方法。優(yōu)先級(jí)隊(duì)列方法是將活結(jié)點(diǎn)表組織成一個(gè)優(yōu)先級(jí)隊(duì)列，并按優(yōu)先級(jí)隊(duì)列中規(guī)定的結(jié)點(diǎn)優(yōu)先級(jí)來(lái)選取優(yōu)先級(jí)最高的下一個(gè)結(jié)點(diǎn)作為當(dāng)前擴(kuò)展結(jié)點(diǎn)。9.2.2裝載問(wèn)題

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

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

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

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

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

1．一般隊(duì)列分支界限法

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

2．算法改進(jìn)

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

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

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

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

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

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