第10章

回溯算法10.1知識簡介

回溯算法是在包含問題的所有解的解空間樹中，按照深度優先的策略，從根結點出發搜索解空間樹。算法搜索至解空間樹的任一結點時，總是先判斷該結點是否包含問題的解，如果肯定不包含問題的解，則不再對以該結點為根的子樹進行搜索，而是逐層向其祖先結點回溯；否則，進入該子樹，繼續按照深度優先的策略進行搜索。回溯法就是一種基于深度優先搜索和約束函數的問題求解方法，它適用于解一些組合數較大的問題。10.1.1回溯算法

回溯法在用來求問題的所有解時，要回溯到根，且根結點的所有子樹都已被搜索才結束。而回溯法在用來求問題的任一解時，只要搜索到問題的一個解即可結束。10.1知識簡介

回溯法求解問題的基本步驟如下：

①

針對所給問題，定義問題的解空間；

②

確定易于搜索的解空間結構；

③以深度優先方式搜索解空間，并在搜索過程中用剪枝函數避免無效搜索。10.1.1回溯算法

常用剪枝函數：

①

用約束函數在擴展結點處剪去不滿足約束的子樹；

②

用限界函數剪去得不到最優解的子樹。

回溯法中的解空間樹是在搜索過程中動態生成的，即邊搜索邊擴展分支。這和數據結構中樹的深度遍歷不同，數據結構中樹的遍歷需先建立樹，然后再遍歷。10.1知識簡介

用回溯法解題經常會遇到的兩類經典的解空間樹：子集樹和排列樹。10.1.2解空間樹1）子集樹

從n個元素的集合S中找出滿足某種性質的子集，相應的解空間稱為子集樹。這種樹中通常有2n個葉結點，結點總數為2n+1-1。需Ω(2n)計算時間。

如裝載問題的解空間是一棵子集樹。例如n=3，c1=50，c2=50，且集裝箱重量w={10,40,40}的裝載問題，問是否能將所有集裝箱裝到兩艘輪船。該問題的解決策略是將第一艘船盡可能裝滿，然后將剩余的集裝箱裝到第二艘船。這時原問題就轉變為將第一艘船盡可能裝滿，等價于選取全體集裝箱的一個子集，使得該子集中集裝箱重量之和最接近或等于c1。10.1知識簡介

用回溯法解題經常會遇到的兩類經典的解空間樹：子集樹和排列樹。10.1.2解空間樹1）子集樹

上述裝載問題的子集樹如下：該子集樹中，所有分支表示某個集裝箱是否裝入第一艘輪船。分支A-B，值為1，表示將第一個集裝箱裝入輪船，分支A-C，值為0，表示第一個集裝箱不裝入輪船。10.1知識簡介

用回溯法解題經常會遇到的兩類經典的解空間樹：子集樹和排列樹。10.1.2解空間樹2）排列樹當所給問題的n個元素滿足某種性質的排列時，相應的解空間樹稱為排列樹。排列樹通常有n!個葉結點。因此，遍歷排列樹需要Ω(n!)計算時間。TSP(旅行售貨員問題)的解空間是一棵排列樹。如有四個城市，城市之間的道路以及路程如右圖所示。求從城市1開始，將每個城市走一遍，最后又回到城市1的總路程最短的路線。10.1知識簡介

用回溯法解題經常會遇到的兩類經典的解空間樹：子集樹和排列樹。10.1.2解空間樹2）排列樹

TSP(旅行售貨員問題)的排列樹如下：用深度優先方式從根結點開始，通過搜索解空間樹發現一個最小耗費的旅行。10.1知識簡介

回溯算法的實現有兩種：遞歸實現和迭代實現。10.1.3算法的實現

1）遞歸回溯

回溯法是對解空間作深度優先搜索，因此，在一般情況下用遞歸方法實現，t表示搜索深度。遞歸回溯的過程如下：

voidBacktrack(intt){//t表示搜索深度if(t>n)//搜索到葉子結點Output(x);//記錄或輸出得到的可行解xelsefor(inti=f(n,t);i<=g(n,t);i++){//從t的編號為f(n,t)到g(n,t)未搜索的子樹一一搜索x[t]=h(i);//第t步的選擇值h(i)

if(Constrain(t)&&Bound(t))//滿足約束條件且目標函數未越界Backtrack(t+1);//進一步搜索}}10.1知識簡介

回溯算法的實現有兩種：遞歸實現和迭代實現。10.1.3算法的實現2）迭代回溯

采用樹的非遞歸深度優先遍歷算法，可將回溯法表示為一個非遞歸迭代過程。迭代回溯的過程如下：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);//第t步的選擇值h(i)if(Constrain(t)&&Bound(t)){//如果滿足約束條件且目標函數未越界

10.1知識簡介

回溯算法的實現有兩種：遞歸實現和迭代實現。10.1.3算法的實現2）迭代回溯

采用樹的非遞歸深度優先遍歷算法，可將回溯法表示為一個非遞歸迭代過程。迭代回溯的過程如下：if(Solution(t))//判斷是否已得到問題的可行解Output(x);//記錄或輸出得到的可行解x

elset++;//未得到問題的可行解，繼續向縱深方向搜索}//如果該結點不滿足約束條件或目標函數越界，則選下一個結點}

elset--;}}10.2實驗目的

通過解決0-1背包問題、旅行售貨員問題和n皇后問題，讓學生能夠深入理解和熟練運用回溯法解決各類組合優化問題，培養良好的邏輯思維能力和高效的問題解決技能。通過編程實現回溯算法，培養算法設計和調試技能，積累解決實際問題的經驗。10.3實驗范例

在n×n格的棋盤上放置彼此不受攻擊的n個皇后，按照國際象棋的規則，皇后可以攻擊與之在同一行或同一列或同一斜線上的棋子，n后問題等價于在n×n格的棋盤上放置n個皇后，任何2個皇后不放在同一行或同一列或同一斜線上。求有多少種放置方法。10.3.1n皇后問題1、問題描述10.3實驗范例

如下所示的為4皇后問題的兩個可行解。10.3.1n皇后問題1、問題描述10.3實驗范例10.3.1n皇后問題2、問題分析

可以用一個數組x[1…n]表示n皇后的解，x[i]表示皇后i放在棋盤的第i行的第x[i]列。1）問題的解空間樹

對于第i行的皇后，x[i]取值有n種情況，所以解空間是一顆完全n叉樹。如4皇后的解空間樹是一顆完全4叉樹，4叉樹的葉子個數為45-1=256。10.3實驗范例10.3.1n皇后問題2、問題分析從根結點到某個葉子結點的路徑就是問題的一個可能解，需從這256個可能的解中找出滿足條件的解。4皇后的解空間樹如下圖所示：10.3實驗范例10.3.1n皇后問題2、問題分析

在求解過程中用問題的約束條件將那些不滿足條件的分支剪去，從而避免無效搜索，從而提高搜索效率。2）剪枝函數

該問題中放置皇后有3個約束條件：不在同一行、不在同一列、不在同一斜線上。用x[1…n]表示n皇后的解可以保證任何兩個皇后不在同一行。每一行有n種放置方法，要保證任何兩個皇后不在同一列，則任何兩個皇后放置的列號應不相同。即解向量中的x[i]互不相同。10.3實驗范例10.3.1n皇后問題2、問題分析

利用此條件可以對解空間樹進行剪枝，如剪枝后的4皇后問題的解空間樹如下圖所示：2）剪枝函數10.3實驗范例10.3.1n皇后問題2、問題分析

2）剪枝函數

10.3實驗范例10.3.1n皇后問題2、問題分析

2）剪枝函數

黃色結點表示該位置不符合條件，從根結點到綠色結點（16號和22號結點）為可行解。4皇后問題的可行解為：(2、4、1、3)和(3、1、4、2)。10.3實驗范例10.3.1n皇后問題2、問題分析

用函數Place判斷第i行將皇后放到x[i]的位置是否可行，函數可以定義如下：2）剪枝函數boolIsPlace(inti){for(intk=1;k<=i;k++){//會相互攻擊if(x[i]==x[k]||abs(i-k)==abs(x[i]-x[k]))returnfalse;}returntrue;//不會相互攻擊}10.3實驗范例10.3.1n皇后問題3、算法描述用迭代回溯求n皇后問題，輸出可行解，并返回可行解個數，函數可以定義如下：intNQueen_Iteration(intn){intsolutionNum=0;//可行解個數intk=1;//從第一行開始while(k>0){//如果k等于0，說明第一行全部試探完，退回到第一行前面x[k]=x[k]+1;//從上次搜索的下一位置開始for(;x[k]<=n;x[k]++){if(IsPlace(k)){//如果可以放if(k==n){//得到問題的可行解Print(n);//輸出得到的可行解solutionNum++;//可行解個數加1}10.3實驗范例10.3.1n皇后問題3、算法描述用迭代回溯求n皇后問題，輸出可行解，并返回可行解個數，函數可以定義如下：else{//未得到問題的可行解，繼續向縱深方向搜索k++;x[k]=0;}}}k--;//回溯到上一行}returnsolutionNum;}10.3實驗范例10.3.1n皇后問題3、算法描述用遞歸回溯求n皇后問題，輸出可行解，并返回可行解個數，函數可以定義如下：intNQueen_Recursion(intk,intn){intsolutionNum=0;//可行解個數if(k>n){//找到一個可行解Print(n);//輸出可行解return1;}

elsefor(inti=1;i<=n;i++){x[k]=i;//將皇后放置到位置iif(IsPlace(k))//該位置可行，則繼續放下一行的皇后solutionNum+=NQueen_Recursion(k+1,n);

}returnsolutionNum;//返回可行解數}10.3實驗范例10.3.1n皇后問題3、算法描述

輸出可行解函數Print定義如下：voidPrint(intn)//輸出可行解{inti;printf("\n(");for(i=1;i<n;i++){printf("%d,",x[i]);}printf("%d)\n",x[i]);}10.3實驗范例10.3.1n皇后問題4、算法分析

回溯法的時間復雜度通常表示為

O(N!)

或者

O(N^N)，但實際上，由于剪枝的存在，實際運行時生成的有效節點數遠小于這些理論上限。對于較小的N值（如N≤30），回溯法通常能夠在可接受的時間內找到所有解或至少一個解。隨著N增大，盡管復雜度理論上限很高，但由于大量無效狀態被提前排除，實際性能往往比理論復雜度要好。

對于實際應用，尤其是對于中小規模的N（如N≤30），回溯法及其優化版本通常是有效且實用的解決方案。對于大規模N，可能需要采用更高級的算法或專門設計的高效數據結構來處理。10.4實驗任務完成下列任務，并分析各算法的時間復雜度。任務1：利用回溯算法求解0-1背包問題。

給定n種物品和一個背包。第i種物品重量為wi，其價值為vi，其中i=1、2、3、…、n。背包的容量為c。問如何選擇放入背包的物品，使得放入背包的物品的總價值最大。

10.4實驗任務完成下列任務，并分析各算法的時間復雜度。任務1：利用回溯算法求解0-1背包問題。0-1背包問題是一個特殊的整數規劃問題：

10.4實驗任務完成下列任務，并分析各算法的時間復雜度。任務2：利用回溯算法求解旅行售貨員問題。

某售貨員要到n個城市去推銷商品，已知各城市之間的路程(或旅行所需的費用)。要選定一條從駐地出發，經過每個城市一遍，最后回到駐地的路線，使總的路程(或總旅費)最小。10.5任務提示1、問題分析任務1提示

用回溯法求解此問題，先需要分析問題的解空間以及在搜索過程中使用的剪枝函數。1）問題的解空間0-1背包問題的解空間樹是一棵子集樹。樹中每個結點有兩個分支，分別表示該物品裝入（值為1）背包和不裝入背包（值為0）。10.5任務提示1、問題分析任務1提示1）問題的解空間

該子集樹中，所有分支表示某個物品選還是不選。分支A-B，值為1，表示選擇第一個物品，分支A-C，值為0，表示不選擇第一個物品。

例如3個物品的0-1背包問題，物品個數n=3，背包容量c=30，每個物品重量w={16,15,15}，每個物品的價值v={45,25,24}。該問題的子集樹如下：10.5任務提示1、問題分析任務1提示1）問題的解空間

該樹的葉子結點總共有23=8，從根結點到某個葉子結點就是問題的一個可能的解，需從這8個可能的解中找出滿足條件的解。

例如3個物品的0-1背包問題，物品個數n=3，背包容量c=30，每個物品重量w={16,15,15}，每個物品的價值v={45,25,24}。該問題的子集樹如下：10.5任務提示1、問題分析任務1提示2）剪枝函數

在求解過程中用問題的可行性約束條件和限界函數將那些不滿足條件的分支剪去，從而避免無效搜索，從而提高搜索效率。可行性約束條件為下一個物品能裝入背包中。限界函數是將剩下的物品裝滿背包剩余空間得到的最大值，與已放入背包中物品的價值之和比當前最大值更大。為了能方便計算背包剩余空間裝入的物品價值最大，先將所有物品按單位價值從大到小排序。10.5任務提示1、問題分析任務1提示2）剪枝函數

如上述案例中3個物品單位價值從大到小為{16,15,15}，順序和原有順序一致。可行性約束條件

10.5任務提示1、問題分析任務1提示2）剪枝函數

如上述案例利用約束函數剪枝之后的解空間樹如下：

其中r=14表示背包剩余容量為14，（16，45）表示背包中已裝入物品的重量為16，裝入背包中物品的總價值為45。分支A-B表示裝入物品1，在頂點B處，背包中裝入物品的重量為16，總價值為45，剩余容量14。接著搜索分支B-D，選擇物品2，但物品2的重量是15，大于14，物品2裝不進背包中，將以D為根結點的子樹剪去。10.5任務提示1、問題分析任務1提示2）剪枝函數限界函數

該問題是求可行解中背包中物品價值最大的解，在搜索過程中存儲當前最優解，每得到一個可行解，將其和當前最優解比較，如果該可行解比當前最優解值更大，則替換當前最優解。在搜索過程中，當進入右子樹時，可以計算背包剩余容量能裝入的物品的最大值，再加上當前背包中物品的總價值。如果這個值比當前得到的最優解小，說明搜索這個右子樹不能得到更優解，將該右子樹剪去。這樣可以排除那些比當前最優值更小的可行解，所以只要得到一個可行解，則此可行解一定是當前最優解。10.5任務提示1、問題分析任務1提示2）剪枝函數

如上述案例利用限界剪枝之后的解空間樹如下：

在結點G處，由于剩余物品只有物品3沒有裝入，此時背包中物品的價值為0，剩余容量為30。如果將剩余的物品裝入背包后，背包中物品的最大價值為24，比當前最優值49小，可以搜將以該結點為根結點的子樹不可能得到更優的結點，將該子樹剪去。10.5任務提示1、問題分析任務1提示2）剪枝函數

用Bound函數來計算將背包剩余容量裝滿（可能有某個物品只能裝部分）能裝入的物品最大值和已裝入物品的總價值之和，偽代碼描述如下：TypePBound(inti){//計算上界，TypeP為價值的類型TypeWcleft=c-cw;//背包剩余容量，cw為背包已放物品重量TypePb=cp;//cp為已放入背包中物品的總價值while(i<=n&&w[i]<=cleft){//以物品單位重量價值遞減的順序裝入物品cleft-=w[i];b+=p[i];i++;

}10.5任務提示1、問題分析任務1提示2）剪枝函數

用Bound函數來計算將背包剩余容量裝滿（可能有某個物品只能裝部分）能裝入的物品最大值和已裝入物品的總價值之和，偽代碼描述如下：TypePBound(inti){//計算上界，TypeP為價值的類型//如果背包沒裝滿，且還有物品，將剩余物品中單位價值最大的物品裝入部分，將背包裝滿if(i<=n)b+=p[i]*cleft/w[i];returnb;}10.5任務提示2、算法描述任務1提示

遞歸回溯求0-1背包問題偽代碼描述如下：voidKnapsack__Recursion(inti){if(i>=n){//已達到葉子結點bestP=cp;//得到當前最優解return;}//判斷可行性約束條件if(cw+w[i]<=c){//進入左子樹cw=cw+w[i];cp=cp+p[i];Knapsack__Recursion(i+1);cw=cw-w[i];cp=cp-p[i];

}//判斷限界條件if(Bound(i+1)>bestP)//進入右子樹Knapsack__Recursion(i+1);}10.5任務提示任務1提示3、算法分析

計算上界需要O(n)時間，在最壞情況下有O(2n)個右孩子需要計算上界，故0-1背包問題的回溯算法所需的計算時間為O(n*2n)。10.5任務提示1、問題分析任務2提示

可以把該問題模型化為一個具有n個頂點（表示n個城市）帶權圖，邊表示兩個城市之間有路，邊的權值表示城市之間的路程或者旅行所需的費用。例如有4個城市以及各城市之間的路程用帶權圖表示如下：

從城市1出發，每個城市經歷一次，最后回到城市1路程最短的路徑是（1，3，2，4，1），總路程是25。10.5任務提示1、問題分析任務2提示

用鄰接矩陣來存儲帶權圖，城市之間的路程（或者費用）用鄰接矩陣A表示。如上例的鄰接矩陣如下：

10.5任務提示1、問題分析任務2提示1）問題的解空間

10.5任務提示1、問題分析任務2提示1）問題的解空間

上述案例的排列樹如下：

樹中分支表示選擇哪個城市，從城市1出發，接著可以選擇城市2、城市3或城市4。如果選擇城市2，接著可以選擇城市3或者城市4，如果選擇城市3，最后只能選擇城市4。樹中每一條從根結點到葉子結點的路徑代表一種排列的順序，從根結點A到葉子結點L的路徑代表的排列順序為（1，2，3，4）。10.5任務提示1、問題分析任務2提示1）問題的解空間

在對解空間樹進行遞歸搜索過程中，選擇第n-1個城市后選擇第n個城市，第n個城市只有一種選擇，此時只需檢測頂點k[n-1]到頂點k[n]以及頂點x[n]到頂點x[1]是否有邊。如果兩條邊都存在，則找到了一條可行的回路。如果這條回路的路程（或者費用）比當前找到的最優解更小，則需更新當前最優解為當前找到的解。10.5任務提示1、問題分析任務2提示2）剪枝函數

對于n個城市的問題，排列樹中結點是逐層減少的，樹中總共有（n-1）!個葉子結點。在求解過程中用問題的可行性約束條件和限界函數將那些不滿足條件的分支剪去，避免無效搜索，從而提高搜索效率。10.5任務提示1、問題分析任務2提示2）剪枝函數可行性約束條件

在選擇第i個城市時，所選擇的城市和已選的第i-1個城市之間必須有邊，否則剪去相應的子樹。選兩個城市之間有邊，即對應鄰接矩陣中元素的值不為無邊標志(用NoEdge表示，在鄰接矩陣中用無窮來表示)，該條件描述如下：d[k[i-1]][k[i]]!=NoEdge10.5任務提示1、問題分析任務2提示2）剪枝函數限界函數

當選擇第i個城市時，當前所需的總路程（或者總旅費）需比當前最優解小，否則剪去相應的子樹。假設用cc表示當前路程或者費用，用bestC表示當前最優解，則該條件描述如下：cc+d[k[i-1]][k[i]]<bestC

或者還沒有得到一個可行解，即bestC==NoEdge。

當這兩個條件都滿足，可以選擇下一個城市；否則，剪去相應的子樹。10.5任務提示2、算法描述任務2提示

遞歸回溯求旅行售貨員問題偽代碼描述如下：#defineMAXN20ValueTypebestC;//最優路程或者費用，初始值為無窮ValueTypecc;//當前路徑的路程或者費用，初始值為0