第5章 回溯算法

計算機算法設計與分析

DesignandAnalysisofComputerAlgorithms

第五章回溯算法BacktrackAlgorithm王紅霞理學院2024年2月29日2理解回溯法的深度優(yōu)先搜索策略。掌握用回溯法解題的算法框架（1）遞歸回溯（2）迭代回溯（3）子集樹算法框架（4）排列樹算法框架學習要點2024年2月29日3提綱一、回溯法的算法框架二、裝載問題三、n后問題四、0-1背包問題五、最大團問題六、圖的m著色問題七、旅行售貨員問題2024年2月29日4提綱一、回溯法的算法框架二、裝載問題三、n后問題四、0-1背包問題五、最大團問題六、圖的m著色問題七、旅行售貨員問題2024年2月29日5深度優(yōu)先搜索算法

深度優(yōu)先搜索算法（Depth-First-Search），是搜索算法的一種。是沿著樹的深度遍歷樹的節(jié)點，盡可能深的搜索樹的分支，如果發(fā)現(xiàn)目標，則算法中止，屬于盲目搜索。深度優(yōu)先搜索是圖論中的經典算法，利用深度優(yōu)先搜索算法可以產生目標圖的相應拓撲排序表，利用拓撲排序表可以方便的解決很多相關的圖論問題，如最大路徑問題等等。2024年2月29日6

同時深度優(yōu)先搜索算法的時間復雜度不高（為線性時間復雜度），遍歷圖的效率往往非常高。因此，鑒于深度優(yōu)先搜索算法的強大功能以及高效性往往被研究圖論問題的專家所推崇，他們常建議在遇到未知性質的圖時，先對圖進行深度優(yōu)先遍歷，以了解未知圖的性質。因發(fā)明“深度優(yōu)先搜索算法”，霍普克洛夫特與陶爾揚共同獲得計算機領域的最高獎：圖靈獎2024年2月29日7

搜索與回溯是計算機解題中常用的算法，很多問題無法根據某種確定的計算法則來求解，可以利用搜索與回溯的技術求解。回溯是搜索算法中的一種控制策略。它的基本思想是：為了求得問題的解，先選擇某一種可能情況向前探索，在探索過程中，一旦發(fā)現(xiàn)原來的選擇是錯誤的，就退回一步重新選擇，繼續(xù)向前探索，如此反復進行，直至得到解或證明無解。

2024年2月29日8迷宮游戲2024年2月29日9例：迷宮游戲2024年2月29日10例：N后問題2024年2月29日11引言有許多問題，當需要找出它的解集或者要求回答什么解是滿足某些約束條件的最佳解時，往往要使用回溯法?；厮莘ǖ幕咀龇ㄊ撬阉鳎蚴且环N組織得井井有條的、能避免不必要搜索的窮舉式搜索法。這種方法適用于解一些組合數(shù)相當大的問題。回溯法在問題的解空間樹中，按深度優(yōu)先策略，從根結點出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點時，先判斷該結點是否包含問題的解：如果肯定不包含，則跳過對該結點為根的子樹的搜索，逐層向其祖先結點回溯；否則，進入該子樹，繼續(xù)按深度優(yōu)先策略搜索。2024年2月29日125.1回溯法的算法框架本節(jié)介紹回溯法算法框架的有關問題：一、問題的解空間二、回溯法的基本思想三、遞歸回溯四、迭代回溯五、子集樹與排列樹2024年2月29日135.1.1問題的解空間問題所有可能的解構成了問題的解空間，解空間也就是進行窮舉的搜索空間。確定正確的解空間很重要！例如：桌子上有6根火柴棒，要求以這6根火柴棒為邊搭建4個等邊三角形。(a)二維搜索空間無解(b)三維搜索空間的解錯誤的解空間將不能搜索到正確答案！2024年2月29日145.1.1問題的解空間對于任何一個問題，可能解的表示方式和它相應的解釋隱含了解空間及其大小。例如，對于有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)}2024年2月29日15問題的解向量：回溯法希望一個問題的解能夠表示成一個n元式(x1,x2,…,xn)的形式。顯約束：對分量xi的取值限定。隱約束：為滿足問題的解而對不同分量之間施加的約束。解空間：對于問題的一個實例，解向量滿足顯式約束條件的所有多元組，構成了該實例的一個解空間。注意：同一個問題可以有多種表示，有些表示方法更簡單，所需表示的狀態(tài)空間更?。ù鎯α可?，搜索方法簡單）。2024年2月29日165.1.1問題的解空間

為了用回溯法求解一個具有n個輸入的問題，一般情況下，將其可能解表示為滿足某個約束條件的等長向量X=(x1,x2,…,xn)，其中分量xi(1≤i≤n)的取值范圍是某個有限集合Si={ai1,ai2,…,airi}，所有可能的解向量構成了問題的解空間。問題的解空間一般用解空間樹（SolutionSpaceTrees,也稱狀態(tài)空間樹）的方式組織，樹的根結點位于第1層，表示搜索的初始狀態(tài)，第2層的結點表示對解向量的第一個分量做出選擇后到達的狀態(tài)，第1層到第2層的邊上標出對第一個分量選擇的結果，依此類推，從樹的根結點到葉子結點的路徑就構成了解空間的一個可能解。2024年2月29日175.1.1問題的解空間

1.背包問題對于n=3的0/1背包問題，其解空間樹如下圖所示，樹中的8個葉子結點分別代表該問題的8個可能解。對物品1的選擇對物品3的選擇對物品2的選擇11111100000001123457811121415310692024年2月29日182旅行售貨員問題問題描述：某售貨員要到若干城市去推銷商品，已知各城市之間的路程，他要選定一條從駐地出發(fā)，經過每個城市一遍，最后回到住地的路線，使總的路程最短。該問題是一個NP完全問題，有(n-1)!條可選路線最優(yōu)解(1,3,2,4,1)，最優(yōu)值251234206305410ABCDEFGHIJKLMNOPQ12343443423224232024年2月29日195.1.2回溯法的基本思想

回溯法從根結點出發(fā)，按照深度優(yōu)先策略搜索（遍歷）解空間樹，搜索滿足約束條件的解。初始時，根結點成為一個活結點，同時也稱為當前的擴展結點。在當前擴展結點處，搜索向縱深方向移至一個新結點。這個新結點成為一個新的活結點，并成為當前的擴展結點。如果在當前的擴展結點處不能再向縱深方向移動，則當前的擴展結點就成為一個死結點（即不再是一個活節(jié)點）。此時，應往回移動（回溯）至最近的一個活結點處，并使這個活結點成為當前的擴展結點。20死結點擴展結點活結點擴展結點:一個正在產生兒子的結點稱為擴展結點?；罱Y點:一個自身已生成但其兒子還沒有全部生成的節(jié)點稱做活結點。死結點:一個所有兒子已經產生的結點稱做死結點。2024年2月29日215.1.2回溯法的基本思想在搜索至樹中任一結點時，先判斷該結點對應的部分解是否滿足約束條件，或者是否超出限界函數(shù)的界，也就是判斷該結點是否包含問題的（最優(yōu)）解，如果肯定不包含，則跳過對以該結點為根的子樹的搜索，即所謂剪枝（Pruning）；否則，進入以該結點為根的子樹，繼續(xù)按照深度優(yōu)先策略搜索。在搜索過程中，通常采用兩種策略避免無效搜索：（1）用約束條件剪去得不到可行解的子樹；（2）用限界函數(shù)剪去得不到最優(yōu)解的子樹。這兩類函數(shù)統(tǒng)稱為剪枝函數(shù)（PruningFunction）。2024年2月29日225.1.2回溯法的基本思想

例如，對于n=3的0/1背包問題，三個物品的重量為{16,15,15}，價值為{45,25,25}，背包容量為30，從其解空間樹的根結點開始搜索，搜索過程如下：ACr=C=30，V=0HIw1=16，v1=45Cr=14，V=45B1DCr<w2不可行解1JCr<w3不可行解1Fw2=15，v2=25Cr=15，V=251CCr=30，V=00Cr=14V=45E0Lw3=15，v3=25Cr=0，V=5050>45x=(0,1,1)1KCr=14V=45x=(1,0,0)0M25<50不是最優(yōu)解0NOGV<=25不包含最優(yōu)解02024年2月29日235.1.2回溯法的基本思想回溯法是一種通用性解法，可以將回溯法看作是帶優(yōu)化的窮舉法?；厮莘ǖ幕舅枷胧窃谝豢煤袉栴}全部可能解的狀態(tài)空間樹上進行深度優(yōu)先搜索，解為葉子結點，搜索過程中，每到達一個結點時，則判斷該結點為根的子樹是否含有問題的解，如果不含有問題的解，則放棄對該子樹的搜索，退回到上層父結點，繼續(xù)下一步深度優(yōu)先搜索過程。在回溯法中，并不是先構造出整棵狀態(tài)空間樹，再進行搜索，而是在搜索過程，逐步構造出狀態(tài)空間樹，即邊搜索，邊構造；2024年2月29日245.1.3遞歸回溯voidbacktrack(intt)//t表示遞歸深度，即對解空間樹的第t層節(jié)點進行深度優(yōu)先搜索；{

if(t>n)output(x);//n表示解空間樹的高度；

elsefor(inti=f(n,t);i<=g(n,t);i++){//f(n,t)和g(n,t)分別表示在當前擴展結點處未搜索過的子樹的起始編號和終止編號；

x[t]=h(i);//h(i)表示在當前擴展結點處x[t]的第i個可選值；

if(constraint(t)&&bound(t))backtrack(t+1);//constraint(t)和bound(t)分別表示在當前擴展結點處的約束函數(shù)和限界函數(shù)；

}}2024年2月29日255.1.4迭代回溯voidIterativeBacktrack(){intt=1;

while(t>0){

if(f(n,t)<=g(n,t))for(inti=f(n,t);i<=g(n,t);i++){x[t]=h(i);

if(constraint(t)&&bound(t)){//函數(shù)solution(t)判斷在當前擴展結點處是否找到問題的一個可行解；

if(solution(t))output(x);

elset++;}}

elset--;}}2024年2月29日265.1.5子集樹與排列樹當所給問題是從n個元素的集合S中找出滿足某種性質的子集時，解空間為子集樹。

當所給問題是從n個元素的集合S中找出滿足某種性質的排列時，解空間為排列樹。2024年2月29日27遍歷子集樹需O(2n)計算時間遍歷排列樹需要O(n!)計算時間voidbacktrack(intt){if(t>n)output(x);elsefor(inti=0;i<=1;i++){x[t]=i;if(constraint(t)&&bound(t))backtrack(t+1);}}voidbacktrack(intt){if(t>n)output(x);elsefor(inti=t;i<=n;i++){swap(x[t],x[i]);if(constraint(t)&&bound(t))

backtrack(t+1);swap(x[t],x[i]);}}5.1.5子集樹與排列樹//更換排列順序

當前的第一個元素和下面的交換

//搜索完畢后恢復

2024年2月29日28對于n=4的旅行售貨員問題（TSP），其解空間樹如下圖所示。葉子結點代表該問題的可能解，例如結點5代表一個可能解，路徑為1→2→3→4→1，長度為各邊代價之和。243422343413142412123312134131312321214241434322434123124134n=4的TSP問題的解空間樹57101215172123262831333739424447495254575962644691114162022252730323638414346485153565861633813192429354045505560218342411234342024年2月29日295.1.6回溯法的求解過程(1)針對所給問題，定義問題的解空間；(2)確定易于搜索的解空間結構；(3)深度優(yōu)先搜索解空間，并在搜索中用剪枝函數(shù)避免無效搜索。常用剪枝函數(shù)：用約束函數(shù)在擴展結點處剪去不滿足約束的子樹；用限界函數(shù)剪去得不到最優(yōu)解的子樹。需要注意的是，問題的解空間樹是虛擬的，并不需要在算法運行時構造一棵真正的樹結構。在任何時刻，算法只保存從根結點到當前擴展結點的路徑。如果解空間樹中從根結點到葉結點的最長路徑的長度為h(n)，則回溯法所需的計算空間通常為O(h(n))。而顯式地存儲整個解空間則需要O(2h(n))或O(h(n)!)內存空間。2024年2月29日30提綱一、回溯法的算法框架二、裝載問題三、n后問題四、0-1背包問題五、最大團問題六、圖的m著色問題七、旅行售貨員問題2024年2月29日315.2.1裝載問題問題定義有一批共n個集裝箱要裝上2艘載重量分別為c1和c2的輪船，其中集裝箱i的重量為wi，且∑wi≤c1+c2裝載問題要求確定是否有一個合理的裝載方案可將這n個集裝箱裝上這2艘輪船。如果有，找出一種裝載方案。例如：當n=3，c1=c2=50，w=[10,40,40]，可以將集裝箱1和2裝到第一艘輪船上，將集裝箱3裝到第二艘輪船上。如果w=[20,40,40]，則無法將這3個集裝箱都裝上輪船。2024年2月29日325.2.2問題分析如果一個給定裝載問題有解，則采用下面的策略可得到最優(yōu)裝載方案：(1)首先將第一艘輪船盡可能裝滿；(2)將剩余的集裝箱裝上第二艘輪船。將第一艘輪船盡可能裝滿等價于選取全體集裝箱的一個子集，使該子集中集裝箱重量之和最接近c1

。由此可知，裝載問題等價于以下特殊的0-1背包問題。2024年2月29日335.2.3算法設計解空間：子集樹可行性約束函數(shù)(選擇當前元素)：上界函數(shù)(不選擇當前元素)：當前載重量cw+剩余集裝箱的重量r>當前最優(yōu)載重量bestw101111000不滿足約束函數(shù)1不滿足上界函數(shù)00134例w={16,15,15},c=3001603100031163001615151510000000111113131用子集樹表示其解空間，用可行性約束函數(shù)可剪去不滿足條件的子樹。在子集樹的第j+1層的結點Z處，用cw記當前的裝載重量，即cw=，則當cw>c1時，以結點Z為根的子樹中所有結點都不滿足約束條件，因而該子樹中的解均為不可行解，故可將該子樹剪去。355.2.4裝載問題算法描述template<classType>classLoading{friendTypeMaxLoading(Type[],Type,int);private:voidBacktrack(inti);intn;//集裝箱數(shù)Type*w,//集裝箱重量數(shù)組

c,//第一艘輪船的載重量

cw,//當前載重量

bestw;//當前最優(yōu)載重量};函數(shù)MaxLoading負責該類成員的初始化，返回不超過c的最大子集和，但未給出達到這個最大子集和的相應子集Backtrack實現(xiàn)回溯搜索，Backtrack(1)實現(xiàn)對整個解空間的回溯搜索，Backtrack(i)搜索子集樹中第i層子樹。36template<classType>TypeMaxLoading(Typew[],Typec,intn){//返回最優(yōu)載重量Loading<Type>x;x.w=w;x.c=c;x.n=n;x.bestw=0;x.cw=0;

//計算最優(yōu)載重量

x.Backtrack(1);returnx.bestw;}

裝載問題37Backtrack(inti){//搜索第i層結點

如果到達葉結點，則判斷當前的cw，如果比前面得到的最優(yōu)解bestw好，則替換原最優(yōu)解。

//搜索左子樹如果當前剩余空間可以放下當前物品，也就是，cw+w[i]<=c，則把當前載重cw+=w[i]，遞歸訪問其左子樹，Backtrack(i+1)，訪問結束，回到調用點，cw-=w[i]//搜索右子樹Backtrack(i+1);}裝載問題38template<classType>voidLoading<Type>::Backtrack(inti){//搜索第i層結點if(i>n){//到達葉結點

if(cw>bestw)bestw=cw;return;}

//搜索子樹

if(cw+w[i]<=c){//x[i]=1cw+=w[i];Backtrack(i+1);cw-=w[i];}Backtrack(i+1);//x[i]=0}0160030016151515100000011i=1i=2i=316i=41w={16,15,15},c=30即使把剩余物品都裝里也不會得到比當前的最優(yōu)解更好裝載問題右子樹永遠可行！390160030016151515100000011i=1i=2i=316i=41引入一個上界函數(shù)，用于剪去不含最優(yōu)解的子樹，設Z是解空間樹第i層上的當前擴展結點。cw是當前載重量；bestw是當前最優(yōu)載重量；r是剩余集裝箱的重量和；定義上界函數(shù)為cw+r。在以Z為根的子樹中任一結點所相應的載重量均不超過cw+r。因此，當cw+r<=bestw時，可將Z的右子樹剪去。

裝載問題403.上界函數(shù)在改進算法中，引入類Loading的一個私有變量r，用于計算上界函數(shù)，引入上界函數(shù)后，在達到一個葉結點時就不必再檢查該葉結點是否優(yōu)于當前最優(yōu)解。因為上界函數(shù)使算法搜索到的每個葉結點都是迄今為止找到的最優(yōu)解，時間復雜性沒有變化，但在平均情況下改進后的算法檢查的結點數(shù)較少。

裝載問題41Template<classType>classLoading{friendTypeMaxLoading(Type[],Type,int);private:voidBacktrack(inti);intn;//集裝箱數(shù)Type*w,//集裝箱重量數(shù)組

c,//第一艘輪船的載重量

cw,//當前載重量

bestw，//當前最優(yōu)載重量

r;//剩余集裝箱重量};

裝載問題42template<classType>TypeMaxLoading(Typew[],Typec,intn){//返回最優(yōu)載重量Loading<Type>x;x.w=w;x.c=c;x.n=n;x.bestw=0;x.cw=0;

x.r=0;for(inti=1;i<=n;i++)x.r+=w[i];//初始時r為全體物品的重量和

//計算最優(yōu)載重量

x.Backtrack(1);returnx.bestw;}5.2裝載問題43Backtrack(inti){//搜索第i層結點

如果到達葉結點，bestw=cw。

//修改剩余重量rr=r-w[i]

//搜索左子樹如果當前剩余空間可以放下當前物品也就是，cw+w[i]<=c，則把當前載重cw+=w[i]，遞歸訪問其左子樹，Backtrack(i+1)，訪問結束，回到調用點，cw-=w[i]。//搜索右子樹

如果剩余重量加上當前載重大于最優(yōu)值，遞歸訪問右子樹，Backtrack(i+1)。

//回到上一層調用點

r=r+w[i]}

裝載問題44template<classType>voidLoading<Type>::Backtrack(inti){//搜索第i層結點if(i>n){//到達葉結點bestw=cw;return;}

//搜索子樹

r-=w[i];

if(cw+w[i]<=c){//x[i]=1cw+=w[i];Backtrack(i+1);cw-=w[i];}if(cw+r>bestw)//x[i]=0Backtrack(i+1);r+=w[i];}i=1cw=0bestw=0r=46cw=0bestw=0r=30i=2cw=16bestw=0r=15i=3cw=16bestw=0r=0i=4cw=16bestw=161000cw=0bestw=16r=151cw=15bestw=16r=0cw=0bestw=16r=301cw=30bestw=30cw=15bestw=30r=0cw=0bestw=30r=15cw=0bestw=30r=30cw=16bestw=16r=0cw=16bestw=16r=15w={16,15,15},c=3045Template<classType>classLoading{friendTypeMaxLoading(Type[],Type,int,int[]);private:voidBacktrack(inti);intn;//集裝箱數(shù)

*x,//當前解

*bestx;//當前最優(yōu)解Type*w,//集裝箱重量數(shù)組

c,//第一艘輪船的載重量

cw,//當前載重量

bestw，//當前最優(yōu)載重量

r;//剩余集裝箱重量};裝載問題46template<classType>TypeMaxLoading(Typew[],Typec,intn,intbestx[]){//返回最優(yōu)載重量Loading<Type>X;X.x=newint[n+1];X.w=w;X.c=c;X.n=n;X.bestx=bestx;X.bestw=0;X.cw=0;

X.r=0;for(inti=1;i<=n;i++)X.r+=w[i];//初始時r為全體物品的重量和

//計算最優(yōu)載重量

X.Backtrack(1);delete[]X.x;returnx.bestw;}

裝載問題47template<classType>voidLoading<Type>::Backtrack(inti){//搜索第i層結點if(i>n){//到達葉結點

for(j=1;j<=n;j++)bestx[j]=x[j];bestw=cw;return;}

//搜索子樹

r-=w[i];

if(cw+w[i]<=c){

x[i]=1;cw+=w[i];Backtrack(i+1);cw-=w[i];}if(cw+r>bestw){x[i]=0;Backtrack(i+1);}r+=w[i];}裝載問題48bestx可能被更新O(2n)次，算法計算時間復雜性為O(n2n)。采用兩種策略之一改進算法使其復雜度減至O(2n)（1）首先運算只計算最優(yōu)值的算法，計算出最優(yōu)裝載量W，所需計算時間為O(2n)，然后再運行改進后的backtrack，并在算法中將bestw置為W。（2）動態(tài)地更新bsetx，在第i層的當前結點處，當前最優(yōu)解由x[j],j<i，和bestx[j]，i<=j組成，每當算法回溯一層時，將x[i]存入bestx[i],這樣一來，在每個結點處更新bestx只需O(1)時間，從而算法中跟新bestx所需的時間為O(2n)。

裝載問題49迭代回溯非遞歸的方式可以省去O(n)的遞歸棧空間template<classType>TypeMaxLoading(Typew[],Typec,intn,intbestx[]){//迭代回溯

inti=1;//當前層

//x[1:i-1]為當前路徑

int*x=newint[n+1];Typebestw=0,//當前最優(yōu)裝載重量cw=0;//當前載重量r=0;//剩余集裝箱重量for(intj=1;j<=n;j++)r+=w[j];

裝載問題50//搜索子樹while(true){while(i<=n&&cw+w[i]<=c){

//進入左子樹

r-=w[i];cw+=w[i];x[i]=1;i++;}if(i>n){//到達葉結點for(intj=1;j<=n;j++)bestx[j]=x[j];bestw=cw;}else{//進入右子樹

r-=w[i];x[i]=0;i++;}while(cw+r<=bestw){

//剪枝回溯

i--;

while(i>0&&!x[i]){

//從右子樹返回r+=w[i];i--;}if(i==0){delete[]x;returnbestw;}

//進入右子樹x[i]=0;cw-=w[i];i++;}}}51//搜索子樹while(true){while(i<=n&&cw+w[i]<=c){

//進入左子樹

r-=w[i];cw+=w[i];x[i]=1;i++;}if(i>n){//到達葉結點for(intj=1;j<=n;j++)bestx[j]=x[j];bestw=cw;}else{//進入右子樹

r-=w[i];x[i]=0;i++;}i=1cw=0bestw=0r=46cw=0bestw=0r=30i=2cw=16bestw=0r=15i=3cw=16bestw=0r=0i=4cw=16bestw=16100裝載問題w={16,15,15},c=3052i=1cw=0bestw=0r=46cw=0bestw=0r=30i=2cw=16bestw=0r=15i=3cw=16bestw=0r=0i=4cw=16bestw=161000cw=0bestw=16r=151cw=15bestw=16r=0cw=0bestw=16r=301cw=30bestw=30cw=15bestw=30r=0cw=0bestw=30r=15cw=0bestw=30r=30cw=16bestw=16r=0cw=16bestw=16r=15while(cw+r<=bestw){

//剪枝回溯

i--;

while(i>0&&!x[i]){

//從右子樹返回r+=w[i];i--;}if(i==0){delete[]x;returnbestw;}

//進入右子樹x[i]=0;cw-=w[i];i++;}}}

裝載問題w={16,15,15},c=302024年2月29日53習題5-12024年2月29日542024年2月29日55習題5-22024年2月29日562024年2月29日572024年2月29日58提綱一、回溯法的算法框架二、裝載問題三、n后問題四、0-1背包問題五、最大團問題六、圖的m著色問題七、旅行售貨員問題2024年2月29日59N皇后問題是在N×N的國際象棋棋盤上,放置N個皇后,使任何兩個皇后都不能相互攻擊。也就是說,任何兩個皇后,都不在同一行、同一列或同一斜線上。N皇后問題是由八皇后問題演化而來的。八皇后問題于1848年由國際象棋棋手MaxBazzel提出。八皇后問題自從提出之后,吸引了許多著名數(shù)學家的關注,其中包括CarlGauss。近年來,N皇后問題成為計算機應用領域內的一個經典問題,不但成為測試算法的一個工具,還成為檢驗并行計算系統(tǒng)效率的一個有效工具。引言2024年2月29日603.1問題定義八皇后問題是一個非常著名的問題，最初是由著名數(shù)學家高斯提出的。問題的描述是這樣的：在一個8×8的棋盤上，擺放8個皇后，任意兩個皇后不能處在同一行、同一列和同一斜線上。該問題也可以被擴展為在一個n×n的棋盤上擺放n個皇后的問題。在n×n格的棋盤上放置彼此不受攻擊的n個皇后。按照國際象棋的規(guī)則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。n后問題等價于在n×n格的棋盤上放置n個皇后，任何2個皇后不放在同一行或同一列或同一斜線上。2024年2月29日613.1問題定義4皇后問題：********8皇后問題：1Q2Q3Q4Q5Q6Q7Q8Q123456782024年2月29日62例：N后問題2024年2月29日63經典的回溯算法，該算法的思路如下：?

依次在棋盤的每一行上擺放一個皇后。

?

每次擺放都要檢查當前擺放是否可行。如果當前的擺放引發(fā)沖突，則把當前皇后擺放到當前行的下一列上，并重新檢查沖突。

?

如果當前皇后在當前行的每一列上都不可擺放，則回溯到上一個皇后并且將其擺放到下一列上，并重新檢查沖突。

?

如果所有皇后都被擺放成功，則表明成功找到一個解，記錄下該解并且回溯到上一個皇后。

2024年2月29日64求解N后問題中的數(shù)據表示654321123456i+j=k+l2024年2月29日65求解N后問題中的數(shù)據表示i-j=k-l6543211234562024年2月29日663.2問題分析解向量：(x1,x2,…,xn)，x[i]表示皇后i放在棋盤的第i行的第x[i]列。顯約束：xi=1,2,…,n隱約束：

1)不同列：xi≠xj(i≠j)

2)不處于同一正、反對角線：|i-j|≠|xi-xj|解空間：排列樹約束函數(shù)：xi≠xj(i≠j)and|i-j|≠|xi-xj|2024年2月29日67

為了用回溯法求解4皇后問題，算法嘗試生成并以深度優(yōu)先方式搜索一棵完全四叉有根樹，樹的根對應于沒有放置皇后的情況。第一層的節(jié)點對應于皇后在第一行的可能放置情況，第二層的節(jié)點對應于皇后在第二行的可能放置情況，依次類推。2024年2月29日683.3算法描述//place函數(shù)測試若將皇后k放在x[k]列是否與前面已放置的k-1個皇后都不在同一列，而且都不在同一斜線上。boolQueen::Place(intk){for(intj=1;j<k;j++)if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k]))returnfalse;returntrue;}//遞歸函數(shù)backtrack(1)實現(xiàn)對整個解空間的回溯搜索。voidQueen::Backtrack(intt){if(t>n)sum++;//sum記錄當前已找到的可行方案數(shù)。

elsefor(inti=1;i<=n;i++){x[t]=i;if(Place(t))Backtrack(t+1);}}backtrack(i)搜索解空間中的第i層子樹。當t即i>n時，表示算法已搜索至一個葉結點，得到一個新的皇后互不攻擊方案，因此當前已找到的可行方案sum加1。當i<=n時，當前擴展結點是解空間的一個內部結點。該結點有x[i]=1,2,…n共n個兒子結點。對當前擴展結點的每一個兒子結點，由函數(shù)place檢查其可行性，并以深度優(yōu)先的方式遞歸地對可行子樹進行搜索，或者剪去不可行子樹。2024年2月29日692024年2月29日70N后問題的時間復雜性如果只要找出N后問題的一個解，那么這是一個求路徑的問題。求路徑：只需要找到一條路徑便可以得到解。設每個狀態(tài)有k個后繼，其搜索樹為K叉樹，其結點總數(shù)為kn+1–1，遍歷的時間為O(kn)，這里n為找到解的路徑長度。N后問題的路徑深度為n，可選擇的后繼有n個，所以時間復雜性為O(nn)。2024年2月29日71VoidQueen::Backtrack(void){X[i]=0;Intk=1;While(k>0){x[k]+=1;while((x[k]<=n)&&!(place(k)))x[k]+=1;if(x[k]<=n)if(k==n)sum++;else{k++;x[k]=0;}elsek--;}}迭代回溯2024年2月29日72提綱一、回溯法的算法框架二、裝載問題三、n后問題四、0-1背包問題五、最大團問題六、圖的m著色問題七、旅行售貨員問題2024年2月29日734.1問題定義給定n種物品和一個背包，物品i的重量是wi，價值pi,背包容量為C，問如何選擇裝入背包的物品，使裝入背包中的物品的總價值最大？對于每種物品只能選擇完全裝入或不裝入，一個物品至多裝入一次。2024年2月29日744.2問題分析解空間：子集樹可行性約束函數(shù)：或：cw+wi<=c75例n=4,c=7,w={3,5,2,1},p={9,10,7,4}0,03,90,086,205,163,97,173,95,101000001111用子集樹表示其解空間，左兒子如果可行，進入左子樹，只有右子樹中有可能包含最優(yōu)解時才進入右子樹搜索，否則將右子樹剪去。上界函數(shù)：cp+r≤bestp當前獲得價值+剩余價值≤當前最優(yōu)價值。13,9010

0-1背包問題76有時即使?jié)M足了cp+r≤bestp，但實際上背包并不能裝下所有剩余物品，也就是上界cp+r大了?？s小上界可以提供另一個更好的上界函數(shù)。計算右子樹中解的上界時，將剩余物品依其單位重量價值排序，然后依次裝入物品，直至裝不下時，再裝入該物品的一部分而裝滿背包，由此得到的價值是右子樹的上界，如果這個上界不能達到當前得到的最優(yōu)值，則不搜索該子樹。5.30-1背包問題77以物品單位重量價值的遞減序裝入物品。n=4,c=7,p={9,10,7,4},w={3,5,2,1}單位價值量{3,2,3.5,4}。先裝入物品4，然后3，1，物品2最多裝0.2，得到一個解{1,0.2,1,1}，相應的上界為22。5.30-1背包問題78將物品按單位價值量排序。在解空間樹的當前擴展結點處，僅當要進入右子樹時才計算上界函數(shù)Bound，判斷是否可以將右子樹剪去。進入左子樹時，不需要計算上界。5.30-1背包問題79template<classTypew,classTypep>TypepKnap<Typew,Typep>::Bound(inti){//計算上界Typewcleft=c–cw;//剩余容量

Typepb=cp;

//以物品單位重量價值遞減序裝入物品while(i<=n&&w[i]<=cleft){cleft-=w[i];b+=p[i];i++;}//裝滿背包if(i<=n)b+=p[i]/w[i]*cleft;returnb;}

0-1背包問題80例n=4,c=7,w={1，2，3，5},p={4，7，9，10}0,01,43,11116,2016,20019<2019<2020=205.30-1背包問題814.3算法描述template<classTypew,classTypep>classKnap{//背包描述friendTypepKnapsack(Typep*,Typew*,Type,int);private:TypepBound(inti);voidBacktrack(inti);Typewc;//背包容量intn;//物品數(shù)Typew*w,//物品重量數(shù)組Typep*p,//物品價值數(shù)組

Typewcw;//當前重量

Typepcp;//當前價值Typepbestp;//當前最優(yōu)價值};Backtrack實現(xiàn)回溯搜索，Backtrack(1)實現(xiàn)對整個解空間的回溯搜索，Backtrack(i)搜索子集樹中第i層子樹。計算第i層結點的上界5.30-1背包問題82classObject{//物品friendintKnapsack(int*,int*,int,int);public:intoperator<=(Objecta)const{return(d>=a.d);}private:intID;floatd;//單位重量價值};

0-1背包問題83template<classTypew,classTypep>TypepKnapsack(Typepp[],Typeww[],Typewc,intn){//為Knap::Backtrack初始化

TypewW=0;TypepP=0;Object*Q=newObject[n];for(inti=1;i<=n;i++){Q[i-1].ID=i;Q[i-1].d=1.0*p[i]/w[i];P+=p[i];W+=w[i];}if(W<=c)returnP;//裝入所有物品

//依物品單位重量價值排序

Sort(Q,n);Knap<Typew,Typep>K;K.p=newTypep[n+1];K.w=newTypew[n+1];

for(inti=1;i<=n;i++){K.p[i]=p[Q[i-1].ID];K.w[i]=w[Q[i-1].ID];}K.cp=0;K.cw=0;K.c=c;K.n=n;K.bestp=0;//回溯搜索K.Backtrack(1);delete[]Q;delete[]K.w;delete[]K.p;returnK.bestp;}5.30-1背包問題84template<classTypew,classTypep>TypepKnap<Typew,Typep>::Backtrack(inti){if(i>n){bestp=cp;return;}if(cw+w[i]<=c){//x[i]=1cw+=w[i];cp+=p[i];Backtrack(i+1);cw-=w[i];cp-=p[i];}if(Bound(i+1)>bestp)//x[i]=0Backtrack(i+1);}

0-1背包問題如何計算？85算法效率

由于計算上界函數(shù)Bound需要O(n)時間，在最壞情況下有O(2n)個右兒子結點需要計算上界函數(shù)，故解0-1背包問題的回溯算法Backtrack所需的計算時間為O(n2n)。

0-1背包問題2024年2月29日86提綱一、回溯法的算法框架二、裝載問題三、n后問題四、0-1背包問題五、最大團問題六、圖的m著色問題七、旅行售貨員問題2024年2月29日875.1問題定義完全子圖：給定無向圖G=(V，E)。如果U

V，且對任意u，v

U有(u，v)

E，則稱U是G的完全子圖。團：G的完全子圖U是G的團當且僅當U不包含在G的更大的完全子圖中。G的最大團：是指G中所含頂點數(shù)最多的團。124532024年2月29日885.1問題定義空子圖：如果U

V且對任意u，v

U有(u，v)

E，則稱U是G的空子圖。獨立集：G的空子圖U是G的獨立集當且僅當U不包含在G的更大的空子圖中。G的最大獨立集：是G中所含頂點數(shù)最多的獨立集。補圖：對于任一無向圖G=(V，E)其補圖G=(V1，E1)定義為：V1=V，且(u，v)

E1當且僅當(u，v)

E。U是G的最大團當且僅當U是G的最大獨立集。12453124532024年2月29日895.2問題分析解空間：子集樹可行性約束函數(shù)：頂點i到已選入的頂點集中每一個頂點都有邊相連。上界函數(shù)：有足夠多的可選擇頂點使得算法有可能在右子樹中找到更大的團。2024年2月29日905.3算法描述voidClique::Backtrack(inti)//計算最大團{if(i>n){//到達葉結點

for(intj=1;j<=n;j++)bestx[j]=x[j];bestn=cn;return;}

intOK=1;//檢查頂點i與當前團的連接

for(intj=1;j<i;j++)if(x[j]&&a[i][j]==0){//i與j不相連

OK=0;break;}if(OK){//進入左子樹

x[i]=1;cn++;Backtrack(i+1);x[i]=0;cn--;}if(cn+n-i>bestn){//進入右子樹

x[i]=0;Backtrack(i+1);}}復雜度分析最大團問題的回溯算法backtrack所需的計算時間為O(n2n)。2024年2月29日91提綱一、回溯法的算法框架二、裝載問題三、n后問題四、0-1背包問題五、最大團問題六、圖的m著色問題七、旅行售貨員問題2024年2月29日926.1問題定義給定無向連通圖G和m種不同的顏色。用這些顏色為圖G的各頂點著色，每個頂點著一種顏色。是否有一種著色法使G中每條邊的2個頂點著不同顏色。這個問題是圖的m可著色判定問題。若一個圖最少需要m種顏色才能使圖中每條邊連接的2個頂點著不同顏色，則稱這個數(shù)m為該圖的色數(shù)。求一個圖的色數(shù)m的問題稱為圖的m可著色優(yōu)化問題。2024年2月29日936.1問題定義可平面圖：如果一個圖的所有頂點和邊都能用某種方式畫在一個平面上且沒有任何兩邊相交，則稱這個圖是可平面圖。四色定理：任何平面圖都是可以4著色的。2024年2月29日946.1問題定義圖的m著色問題：

給定一個一般連通圖G=(V,E)和m種顏色，如果這個圖不是m可著色的就給出否定回答，如果這個圖是m可著色的，則要找出所有不同的著色方案。2024年2月29日956.2問題分析解向量：(x1,x2,…,xn)表示頂點i所著顏色x[i]。解空間：完全m叉樹可行性約束函數(shù)：頂點i與已著色的相鄰頂點顏色不重復。2024年2月29日966.3算法描述voidColor::Backtrack(intt){if(t>n){sum++;//當前已找到的可m著色方案數(shù)加1；

for(inti=1;i<=n;i++)cout<<x[i]<<'';cout<<endl;}elsefor(inti=1;i<=m;i++){x[t]=i;if(Ok(t))Backtrack(t+1);}}boolColor::Ok(intk)//檢查第k個頂點當前所選顏色x[k]的可用性；{for(intj=1;j<=n;j++)if((a[k][j]==1)&&(x[j]==x[k]))returnfalse;returntrue;}2024年2月29日976.4復雜性分析圖m可著色問題的解空間樹中內結點個數(shù)是∑mi(0≤i≤n-1)。對于每一個內結點，在最壞情況下，用ok檢查當前擴展結點的每一個兒子所相應的顏色可用性需耗時O(mn)。因此，回溯法總的時間耗費是∑mi(mn)=nm(mn-1)/(m-1)=O(nmn)(0≤i≤n-1)2024年2月29日98提綱一、回溯法的算法框架二、裝載問題三、n后問題四、0-1背包問題五、最大團問題六、圖的m著色問題七、旅行售貨員問題2024年2月29日99

旅行商問題是一個經典的組合優(yōu)化問題。經典./-可以描述為：一個商品推銷員要去若干個城市推銷商品，該推銷員從一個城市出發(fā)，需要經過所有城市后，回到出發(fā)地。應如何選擇行進路線，以使總的行程最短。從圖論的角度來看，該問題實質是在一個帶權完全無向圖中，找一個權值最小的Hamilton

回路。由于該問題的可行解是所有頂點的全排列，隨著頂點數(shù)的增加，會產生組合爆炸，它是一個NP

完全問題。由于其在交通運輸、電路板線路設計以及物流配送等領域內有著廣泛的應用，國內外學者對其進行了大量的研究。2024年2月29日100哈密頓回路天文學家哈密頓(WilliamRowanHamilton)提出，在一個有多個城市的地圖網絡中，尋找一條從給定的起點到給定的終點沿途恰好經過所有其他城市一次的路徑。

這個問題和著名的過橋問題的不同之處在于，某些城市之間的旅行不一定是雙向的。比如A→B,但B→A是不允許的。換一種說法，對于一個給定的網絡，確定起點和終點后，如果存在一條路徑，穿過這個網絡，我們就說這個網絡存在哈密頓路徑。哈密頓路徑問題在上世紀七十年代初，終于被證明是“NP完備”的。據說具有這樣性質的問題，難于找到一個有效的算法。實際上對于某些頂點數(shù)不到100的網絡，利用現(xiàn)有最好的算法和計算機也需要比較荒唐的時間（比如幾百年）才能確定其是否存在一條這樣的路徑。

2024年2月29日101從圖中的任意一點出發(fā)，路途中經過圖中每一個結點當且僅當一次，則成為哈密頓回路。

要滿足兩個條件：

1.封閉的環(huán)

2.是一個連通圖，且圖中任意兩點可達

經過圖（有向圖或無向圖）中所有頂點一次且僅一次的通路稱為哈密頓通路。

經過圖中所有頂點一次且僅一次的回路稱為哈密頓回路。

具有哈密頓回路的圖稱為哈密頓圖，具有哈密頓通路但不具有哈密頓回路的圖稱為半哈密頓圖。

平凡圖是哈密頓圖。

2024年2月29日102哈密頓

哈密頓，W．R．(Hamilton，WilliamRowan)

1805年8月4日生于愛爾蘭都柏林；1865年9月2日卒于都柏林．力學、數(shù)學、光學．

2024年2月29日103哈密頓的父親阿其巴德(ArchibaldRowanHamilton)為都柏林市的一個初級律師．哈密頓自幼聰明，被稱為神童．他三歲能讀英語，會算術；五歲能譯拉丁語、希臘語和希伯來語，并能背誦荷馬史詩；九歲便熟悉了波斯語，阿拉伯語和印地語．14歲時，因在都柏林歡迎波斯大使宴會上用波斯語與大使交談而出盡風頭．

哈密頓自幼喜歡算術，計算很快．1818年遇到美國“計算神童”