第8章-回溯法(完)

第8章回溯法2025/2/2第8章回溯法Page28.1概述8.2圖問題中的回溯法8.3組合問題中的回溯法8.4實驗項目——0/1背包問題第8章回溯法

2025/2/2第8章回溯法Page38.1.1問題的解空間8.1.2解空間樹的動態(tài)搜索（1）8.1.3回溯法的求解過程8.1.4回溯法的時間性能8.1概述

2025/2/2第8章回溯法Page4

復(fù)雜問題常常有很多的可能解，這些可能解構(gòu)成了問題的解空間。解空間也就是進行窮舉的搜索空間，所以，解空間中應(yīng)該包括所有的可能解。確定正確的解空間很重要，如果沒有確定正確的解空間就開始搜索，可能會增加很多重復(fù)解，或者根本就搜索不到正確的解。8.1.1問題的解空間2025/2/2第8章回溯法Page5(a)二維搜索空間無解(b)三維搜索空間的解圖8.1錯誤的解空間將不能搜索到正確答案例如：桌子上有6根火柴棒，要求以這6根火柴棒為邊搭建4個等邊三角形。2025/2/2第8章回溯法Page6

對于任何一個問題，可能解的表示方式和它相應(yīng)的解釋隱含了解空間及其大小。例如，對于有n個物品的0/1背包問題，其可能解的表示方式可以有以下兩種：（1）可能解由一個不等長向量組成，當物品i(1≤i≤n)裝入背包時，解向量中包含分量i，否則，解向量中不包含分量i，當n=3時，其解空間是：

{(),(1),(2),(3),(1,2),(1,3),(2,3),(1,2,3)}（2）可能解由一個等長向量{x1,x2,…,xn}組成，其中xi=1(1≤i≤n)表示物品i裝入背包，xi=0表示物品i沒有裝入背包，當n=3時，其解空間是：{(0,0,0),(0,0,1),(0,1,0),(1,0,0),(0,1,1),(1,0,1),(1,1,0),(1,1,1)}2025/2/2第8章回溯法Page7

為了用回溯法求解一個具有n個輸入的問題，一般情況下，將其可能解表示為滿足某個約束條件的等長向量X=(x1,x2,…,xn)，其中分量xi(1≤i≤n)的取值范圍是某個有限集合Si={ai1,ai2,…,airi}，所有可能的解向量構(gòu)成了問題的解空間。

2025/2/2第8章回溯法Page8

問題的解空間一般用解空間樹（SolutionSpaceTrees,也稱狀態(tài)空間樹）的方式組織，樹的根結(jié)點位于第1層，表示搜索的初始狀態(tài)，第2層的結(jié)點表示對解向量的第一個分量做出選擇后到達的狀態(tài)，第1層到第2層的邊上標出對第一個分量選擇的結(jié)果，依此類推，從樹的根結(jié)點到葉子結(jié)點的路徑就構(gòu)成了解空間的一個可能解。2025/2/2第8章回溯法Page9對于n=3的0/1背包問題，其解空間樹如圖8.2所示，樹中的8個葉子結(jié)點分別代表該問題的8個可能解。

對物品1的選擇對物品3的選擇對物品2的選擇111111000000011234578111214151310692025/2/2第8章回溯法Page10

對于n=4的TSP問題，其解空間樹如圖8.3所示，樹中的24個葉子結(jié)點分別代表該問題的24個可能解，例如結(jié)點5代表一個可能解，路徑為1→2→3→4→1，長度為各邊代價之和。

2434223434131424121233121321313123212142414342434123124134圖8.3n=4的TSP問題的解空間樹5710121517212326283133373942444749535558606365469111416202225273032363841434648525457596264381319242935404551566121834501123434∞36712∞2886∞2376∞2025/2/2第8章回溯法Page11

回溯法從根結(jié)點出發(fā)，按照深度優(yōu)先策略遍歷解空間樹，搜索滿足約束條件的解。在搜索至樹中任一結(jié)點時，先判斷該結(jié)點對應(yīng)的部分解是否滿足約束條件，或者是否超出目標函數(shù)的界，也就是判斷該結(jié)點是否包含問題的（最優(yōu)）解，如果肯定不包含，則跳過對以該結(jié)點為根的子樹的搜索，即所謂剪枝（Pruning）；否則，進入以該結(jié)點為根的子樹，繼續(xù)按照深度優(yōu)先策略搜索。8.1.2解空間樹的動態(tài)搜索（1）2025/2/2第8章回溯法Page12例如，對于n=3的0/1背包問題，三個物品的重量為{20,15,10}，價值為{20,30,25}，背包容量為25，從圖8.2所示的解空間樹的根結(jié)點開始搜索，搜索過程如下：1不可行解價值=20價值=55價值=30價值=25價值=01111000000112811121415131069不可行解根據(jù)約束函數(shù)剪枝：2025/2/2第8章回溯法Page13

再如，對于n=4的TSP問題，其代價矩陣如圖8.5所示，

C=∞36712∞2886∞2376∞圖8.5TSP問題的代價矩陣根據(jù)目標函數(shù)剪枝：2025/2/2第8章回溯法Page1423442212313213131232121424142434123124134圖8.6TSP問題的搜索空間5475541127464852545938132429354045515661218345012341∞36712∞2886∞2376∞根據(jù)目標函數(shù)剪枝：2025/2/2第8章回溯法Page15

回溯法的搜索過程涉及的結(jié)點（稱為搜索空間）只是整個解空間樹的一部分，在搜索過程中，通常采用兩種策略避免無效搜索：（1）用約束條件剪去得不到可行解的子樹；（2）用目標函數(shù)剪去得不到最優(yōu)解的子樹。這兩類函數(shù)統(tǒng)稱為剪枝函數(shù)（PruningFunction）。需要注意的是，問題的解空間樹是虛擬的，并不需要在算法運行時構(gòu)造一棵真正的樹結(jié)構(gòu)，只需要存儲從根結(jié)點到當前結(jié)點的路徑。2025/2/2第8章回溯法Page16

由于問題的解向量X=(x1,x2,…,xn)中的每個分量xi(1≤i≤n)都屬于一個有限集合Si={ai1,ai2,…,airi}，因此，回溯法可以按某種順序（例如字典序）依次考察笛卡兒積S1×S2×…×Sn中的元素。初始時，令解向量X為空，然后，從根結(jié)點出發(fā)，選擇S1的第一個元素作為解向量X的第一個分量，即x1=a11，如果X=(x1)是問題的部分解，則繼續(xù)擴展解向量X，選擇S2的第一個元素作為解向量X的第2個分量，否則，選擇S1的下一個元素作為解向量X的第一個分量，即x1=a12。依此類推，一般情況下，如果X=(x1,x2,…,xi)是問題的部分解，則選擇Si+1的第一個元素作為解向量X的第i+1個分量時，有下面三種情況：8.1.3回溯法的求解過程(深度優(yōu)先搜索)

2025/2/2第8章回溯法Page17（1）如果X=(x1,x2,…,xi＋1)是問題的最終解，則輸出這個解。如果問題只希望得到一個解，則結(jié)束搜索，否則繼續(xù)搜索其他解；（2）如果X=(x1,x2,…,xi＋1)是問題的部分解，則繼續(xù)構(gòu)造解向量的下一個分量；（3）如果X=(x1,x2,…,xi＋1)既不是問題的部分解也不是問題的最終解，則存在下面兩種情況：①如果xi+1=ai＋1k不是集合Si＋1的最后一個元素，則令xi+1=ai＋1k＋1，即選擇Si+1的下一個元素作為解向量X的第i+1個分量；②如果xi+1=ai＋1k是集合Si＋1的最后一個元素，就回溯到X=(x1,x2,…,xi)，選擇Si的下一個元素作為解向量X的第i個分量，假設(shè)xi=aik，如果aik不是集合Si的最后一個元素，則令xi=aik＋1；否則，就繼續(xù)回溯到X=(x1,x2,…,xi－1)；2025/2/2第8章回溯法Page1823442212313213131232121424142434123124134圖8.6TSP問題的搜索空間5475541127464852545938132429354045515661218345012341∞36712∞2886∞2376∞S1={1,2,3,4}S2={1,2,3,4}S3={1,2,3,4}S4={1,2,3,4}2025/2/2第8章回溯法Page19回溯法的一般框架——遞歸形式advance(intk)1.對每一個x∈Sk循環(huán)執(zhí)行下列操作

1.1xk=x;1.2將xk加入X;1.3if(X是最終解)flag=true;return;1.4elseif(X是部分解)advance(k+1);主算法1.X={};2.flag=false;3.advance(1);4.if(flag)輸出解X;else輸出“無解”;回溯法的遞歸形式的一般框架如下：2025/2/2第8章回溯法Page20回溯法的一般框架——迭代形式1．X={};2．flag=false;3．k=1;4．while(k>=1)4.1當(Sk沒有被窮舉)循環(huán)執(zhí)行下列操作

4.1.1xk=Sk中的下一個元素;4.1.2將xk加入X;4.1.3if(X為最終解)flag=true;轉(zhuǎn)步驟5;4.1.4elseif(X為部分解)k=k+1;轉(zhuǎn)步驟4;4.2重置Sk，使得下一個元素排在第1位;4.3k=k-1;//回溯5．ifflag輸出解X;else輸出“無解”;

回溯算法的非遞歸迭代形式的一般框架如下：2025/2/2第8章回溯法Page21

一般情況下，在問題的解向量X=(x1,x2,…,xn)中，分量xi(1≤i≤n)的取值范圍為某個有限集合Si={ai1,ai2,…,airi}，因此，問題的解空間由笛卡兒積A=S1×S2×…×Sn構(gòu)成，并且第1層的根結(jié)點有|S1|棵子樹，則第2層共有|S1|個結(jié)點，第2層的每個結(jié)點有|S2|棵子樹，則第3層共有|S1|×|S2|個結(jié)點，依此類推，第n+1層共有|S1|×|S2|×…×|Sn|個結(jié)點，他們都是葉子結(jié)點，代表問題的所有可能解。8.1.3回溯法的求解過程2025/2/2第8章回溯法Page22在用回溯法求解問題時，常常遇到兩種典型的解空間樹：（1）子集樹（SubsetTrees）：當所給問題是從n個元素的集合中找出滿足某種性質(zhì)的子集時，相應(yīng)的解空間樹稱為子集樹。在子集樹中，|S1|=|S2|=…=|Sn|=c，即每個結(jié)點有相同數(shù)目的子樹，通常情況下c=2，所以，子集樹中共有2n個葉子結(jié)點，因此，遍歷子集樹需要Ω(2n)時間。（如：0/1背包問題）（2）排列樹（PermutationTrees）：當所給問題是確定n個元素滿足某種性質(zhì)的排列時，相應(yīng)的解空間樹稱為排列樹。在排列樹中，通常情況下，|S1|=n，|S2|=n-1，…，|Sn|=1，所以，排列樹中共有n!個葉子結(jié)點，因此，遍歷排列樹需要Ω(n!)時間。（如：TSP問題）2025/2/2第8章回溯法Page23對于n=3的0/1背包問題，其解空間樹如圖8.2所示，樹中的8個葉子結(jié)點分別代表該問題的8個可能解。

對物品1的選擇對物品3的選擇對物品2的選擇11111100000001123457811121415131069子集樹2025/2/2第8章回溯法Page24

對于n=4的TSP問題，其解空間樹如圖8.3所示，樹中的24個葉子結(jié)點分別代表該問題的24個可能解，例如結(jié)點5代表一個可能解，路徑為1→2→3→4→1，長度為各邊代價之和。

2434223434131424121233121321313123212142414342434123124134圖8.3n=4的TSP問題的解空間樹5710121517212326283133373942444749535558606365469111416202225273032363841434648525457596264381319242935404551566121834501123434∞36712∞2886∞2376∞排列樹2025/2/2第8章回溯法Page258.2.1圖的m著色問題

8.2.2哈密頓回路問題8.2圖問題中的回溯法2025/2/2第8章回溯法Page26

圖的m著色問題描述為：給定無向連通圖G=(V,E)和正整數(shù)m，判斷能否用m種顏色對G中的頂點著色，使得任意兩個相鄰頂點著色不同。

8.2.1圖的m著色問題2025/2/2第8章回溯法Page27

由于用m種顏色為無向圖G=(V,E)著色，其中，V的頂點個數(shù)為n，可以用一個n元組C=(c1,c2,…,cn)來描述圖的一種可能著色，其中，ci∈{1,2,…,m}(1≤i≤n)表示賦予頂點i的顏色。例如，5元組(1,2,2,3,1)表示對具有5個頂點的無向圖的一種著色，頂點1著顏色1，頂點2著顏色2，頂點3著顏色2，如此等等。

如果在n元組C中，所有相鄰頂點都不會著相同顏色，就稱此n元組為可行解，否則為無效解。2025/2/2第8章回溯法Page28回溯法求解圖著色問題：首先把所有頂點的顏色初始化為0；在圖著色問題的解空間樹中，如果從根結(jié)點到當前結(jié)點對應(yīng)一個部分解，也就是所有的顏色指派都沒有沖突，則在當前結(jié)點處選擇第一棵子樹繼續(xù)搜索，也就是為下一個頂點著顏色1，否則，對當前子樹的兄弟子樹繼續(xù)搜索，也就是為當前頂點著下一個顏色；如果所有m種顏色都已嘗試過并且都發(fā)生沖突，則回溯到當前結(jié)點的父結(jié)點處，上一個頂點的顏色被改變，依此類推。

2025/2/2第8章回溯法Page29D=1ACBDE1234567891011121314A=1B=2C=3D=3E=1(a)一個無向圖(b)回溯法搜索空間圖8.8回溯法求解圖著色問題示例2025/2/2第8章回溯法Page30

設(shè)數(shù)組color[n]表示頂點的著色情況，回溯法求解m著色問題的算法如下：算法8.1——圖的m著色問題

1.將數(shù)組color[n]初始化為0；

2.k=1;3.while(k>=1)3.1依次考察每一種顏色，若頂點k的著色與其他頂點的著色不發(fā)生沖突，則轉(zhuǎn)步驟3.2；否則，搜索下一個顏色；

3.2若頂點已全部著色，則輸出數(shù)組color[n]，返回；

3.3否則，

3.3.1若頂點k是一個合法著色，則k=k+1，轉(zhuǎn)步驟3處理下一個頂點;

3.3.2否則，重置頂點k的著色情況，k=k-1，轉(zhuǎn)步驟3回溯；偽代碼2025/2/2第8章回溯法Page31算法8.2——圖的m著色問題

voidGraphColor(intn,intc[][],intm)//所有數(shù)組下標從1開始

{for(i=1;i<=n;i++)//將數(shù)組color[n]初始化為0color[i]=0;k=1;while(k>=1){color[k]=color[k]+1;while(color[k]<=m)ifOk(k)break;//判斷頂點k的著色是否發(fā)生沖突elsecolor[k]=color[k]+1;//搜索下一個顏色

if(color[k]<=m&&k==n)//求解完畢，輸出解

{for(i=1;i<=n;i++)cout<<color[i];return;}C++描述2025/2/2第8章回溯法Page32elseif(color[k]<=m&&k<n)k=k+1;//處理下一個頂點

else{color[k]=0;k=k-1;//回溯

}}}boolOk(intk)//判斷頂點k的著色是否發(fā)生沖突

{for(i=1;i<k;i++)if(c[k][i]==1&&color[i]==color[k])returnfalse;returntrue;}2025/2/2第8章回溯法Page33假定圖G=(V,E)的頂點集為V={1,2,…,n}，則哈密頓回路的可能解表示為n元組X=(x1,x2,…,xn)，其中，xi∈{1,2,…,n}，并有如下約束條件：(xi,xi+1)∈E(1≤i≤n－1)

(xn,x1)∈E

xi≠xj(1≤i,j≤n，i≠j)8.2.2哈密頓回路問題2025/2/2第8章回溯法Page3412435(a)一個無向圖(b)哈密頓回路的搜索空間x4=4x3=3x2=221x1=147111716x5=5x4=535108961213141521201819x5=42025/2/2第8章回溯法Page35算法8.3——哈密頓回路問題

1．將頂點數(shù)組x[n]初始化為0，標志數(shù)組visited[n]初始化為0；

2．k=1;visited[1]=1;x[1]=1;從頂點1出發(fā)構(gòu)造哈密頓回路；

3．while(k>=1)3.1x[k]=x[k]+1，搜索下一個頂點;3.2若(n個頂點沒有被窮舉)執(zhí)行下列操作

3.2.1若(頂點x[k]不在哈密頓回路上&&(x[k-1],x[k])∈E)，轉(zhuǎn)步驟3.3;3.2.2否則，x[k]=x[k]+1，搜索下一個頂點；

3.3若數(shù)組x[n]已形成哈密頓路徑，則輸出數(shù)組x[n]，算法結(jié)束；

3.4否則，

3.4.1若數(shù)組x[n]構(gòu)成哈密頓路徑的部分解，則k=k+1，轉(zhuǎn)步驟3；

3.4.2否則，重置x[k]，k=k-1，取消頂點x[k]的訪問標志，轉(zhuǎn)步驟3；偽代碼2025/2/2第8章回溯法Page36算法8.4——哈密頓回路問題

voidHamiton(intn,intx[],intc[][])//所有數(shù)組下標從1開始

{for(i=1;i<=n;i++)//初始化頂點數(shù)組和標志數(shù)組

{x[i]=0;visited[i]=0;}visited[1]=1;x[1]=1;//從頂點1出發(fā)k=1;

while(k>=1){x[k]=x[k]+1;//搜索下一頂點

while(x[k]<=n)if(visited[x[k]]==0&&c[x[k-1]][x[k]]==1)break;elsex[k]=x[k]+1;

C++描述2025/2/2第8章回溯法Page37if(x[k]<=n&&k==n&&c[x[k]][1]==1){for(k=1;k<=n;k++)cout<<x[k];return;}elseif(x[k]<=n&&k<n){visited[x[k]]=1;k=k+1;}else{//回溯

x[k]=0;visited[x[k]]=0;k=k-1;}}}2025/2/2第8章回溯法Page388.3.1八皇后問題8.3.2批處理作業(yè)調(diào)度問題8.3組合問題中的回溯法2025/2/2第8章回溯法Page39

八皇后問題是十九世紀著名的數(shù)學(xué)家高斯于1850年提出的。問題是：在8×8的棋盤上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上。可以把八皇后問題擴展到n皇后問題，即在n×n的棋盤上擺放n個皇后，使任意兩個皇后都不能處于同一行、同一列或同一斜線上。8.3.1八皇后問題2025/2/2第8章回溯法Page40

若兩個皇后擺放的位置分別是(i,xi)和(j,xj)，在棋盤上斜率為-1的斜線上，滿足條件i－j=xi－xj，在棋盤上斜率為1的斜線上，滿足條件i＋j=xi＋xj，綜合兩種情況，由于兩個皇后不能位于同一斜線上，所以，解向量X必須滿足約束條件：

|i－xi|≠|(zhì)j－xj|（式8.2）

顯然，棋盤的每一行上可以而且必須擺放一個皇后，所以，n皇后問題的可能解用一個n元向量X=(x1,x2,…,xn)表示，其中，1≤i≤n并且1≤xi≤n，即第i個皇后放在第i行第xi列上。由于兩個皇后不能位于同一列上，所以，解向量X必須滿足約束條件：

xi≠xj（式8.1）2025/2/2第8章回溯法Page4112341234皇后1皇后2皇后3皇后4圖8.11四皇后問題

為了簡化問題，下面討論四皇后問題。四皇后問題的解空間樹是一個完全4叉樹，樹的根結(jié)點表示搜索的初始狀態(tài)，從根結(jié)點到第2層結(jié)點對應(yīng)皇后1在棋盤中第1行的可能擺放位置，從第2層結(jié)點到第3層結(jié)點對應(yīng)皇后2在棋盤中第2行的可能擺放位置，依此類推。2025/2/2第8章回溯法Page42QQ××QQ×Q×××××QQQQ×Q××××QQ×××QQQQQQQ××Q(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)QQ×Q回溯法求解4皇后問題的搜索過程2025/2/2第8章回溯法Page43算法8.5——n皇后問題

voidQueue(intn){for(i=1;i<=n;i++)//初始化

x[i]=0;k=1;while(k>=1){x[k]=x[k]+1;//在下一列放置第k個皇后

while(x[k]<=n&&!Place(k))//若有沖突x[k]=x[k]+1;//搜索下一列

if(x[k]<=n&&k==n){//得到一個解，輸出

for(i=1;i<=n;i++)cout<<x[i];return;}

C++描述2025/2/2第8章回溯法Page44elseif(x[k]<=n&&k<n)k=k+1;//放置下一個皇后

else{x[k]=0;//重置x[k]，回溯

k=k-1;}}}

boolPlace(intk)//考察皇后k放置在x[k]列是否發(fā)生沖突

{for(i=1;i<k;i++)if(x[k]==x[i]||abs(k-i)==abs(x[k]-x[i]))returnfalse;returntrue;}2025/2/2第8章回溯法Page45

n個作業(yè){1,2,…,n}要在兩臺機器上處理，每個作業(yè)必須先由機器1處理，然后再由機器2處理，機器1處理作業(yè)i所需時間為ai，機器2處理作業(yè)i所需時間為bi（1≤i≤n），批處理作業(yè)調(diào)度問題要求確定這n個作業(yè)的最優(yōu)處理順序，使得從第1個作業(yè)在機器1上處理開始，到最后一個作業(yè)在機器2上處理結(jié)束所需時間最少。

8.3.2批處理作業(yè)調(diào)度問題2025/2/2第8章回溯法Page46顯然，批處理作業(yè)的一個最優(yōu)調(diào)度應(yīng)使機器1沒有空閑時間，且機器2的空閑時間最小?？梢宰C明，存在一個最優(yōu)作業(yè)調(diào)度使得在機器1和機器2上作業(yè)以相同次序完成。例：三個作業(yè){1,2,3}，這三個作業(yè)在機器1上所需的處理時間為(2,3,2)，在機器2上所需的處理時間為(1,1,3)，則存在6種可能的調(diào)度方案，最佳調(diào)度方案是(1,3,2)、(3,1,2)和(3,2,1)，其完成時間為8。作業(yè)1:2作業(yè)2:3作業(yè)3:2空閑:2作業(yè)1:1機器1機器2作業(yè)2:1作業(yè)3:3(a)調(diào)度方案(1,2,3)，最后完成時間為10作業(yè)1:2作業(yè)2:3