方法概述

回溯法是一個既帶有系統性又帶有跳躍性的搜索算法；

• **系統性：**它在包含問題的所有解的解空間樹中，按照深度優先的策略，從根結點出發搜索解空間樹。
  跳躍性：算法搜索至解空間樹的任一結點時，判斷該結點為根的子樹是否包含問題的解，如果肯定不包含，則跳過以該結點為根的子樹的搜索，逐層向其祖先結點回溯。否則，進入該子樹，繼續深度優先的策略進行搜索。

這種以深度優先的方式系統地搜索問題的解得算法稱為回溯法，它適用于解一些組合數較大的問題。

• 問題的解向量：回溯法希望一個問題的解能表示成一個𝑛元組$(x_1,x_2,\dots ,x_n)$的形式；
• 顯約束：對分量$x_i$的取值限定；
• 隱約束：為滿足問題的解而對不同分量之間施加的約束；
• 解空間：對于問題的一個實例，解向量滿足顯式約束條件的所有多元組， 構成了該實
  例的一個解空間。

搜索從開始結點（根結點）出發，以深度優先搜索整個解空間。

這個開始結點成為活結點，同時也成為當前的擴展結點。在當前的擴展結點處，搜索向縱深方向移至一個新結點。這個新結點就成為新的活結點，并成為當前擴展結點。

如果在當前的擴展結點處不能再向縱深方向擴展，則當前擴展結點就成為死結點。

此時，應往回移動（回溯）至最近的一個活結點處，并使這個活結點成為當前的擴展結點；直到找到一個解或全部解。

基本步驟：

① 針對所給問題，定義問題的解空間；
② 確定易于搜索的解空間結構；
③ 以深度優先方式搜索解空間，并在搜索過程中用剪枝函數避免無效搜索。

常用剪枝函數：

① 用約束函數在擴展結點處剪去不滿足約束的子樹；
② 用限界函數剪去得不到最優解的子樹。

二類常見的解空間樹

① 子集樹：當所給的問題是從𝑛個元素的集合𝑆中找出滿足某種性質的子集時，相應的解空間樹稱為子集樹。子集樹通常有$2^n$個葉子結點，其總結點個數為$2^{n+1}?1$，遍歷子集樹時間為$\Omega (2^n)$ 。如0-1背包問題，葉結點數為$2^n$，總結點數$2^{n+1}$；
② 排列樹：當所給問題是確定𝑛個元素滿足某種性質的排列時，相應的解空間樹稱為排列樹。排列樹通常有𝑛!個葉子結點，因此，遍歷排列樹需要$\Omega (n!)$的計算時間。如TSP問題，葉結點數為𝑛!，遍歷時間為$\Omega (n!)$。

算法框架

回溯法對解空間作深度優先搜索，因此在一般情況下可用遞歸函數來實現回溯法：

子集樹回溯算法的偽代碼為：

Backtrack( int 𝑡 ) //搜索到樹的第𝑡層
{ //由第𝑡層向第𝑡 + 1層擴展，確定𝑥[𝑡]的值if 𝑡 > 𝑛 then output( 𝑥 ); //葉子結點是可行解else while( all Xt) do //𝑋𝑡為當前擴展結點的所有可能取值集合{𝑿[𝑡] = 𝑋𝑡中的第𝑖個值；if( Constraint(𝑡) and Bound( 𝑡 ) )	Backtrack(𝑡 + 1);}
}

排列樹回溯算法的偽代碼為：

Backtrack( int 𝑡 ) //搜索到樹的第𝑡層
{ //由第𝑡層向第𝑡 + 1層擴展，確定𝑥[𝑡]的值if 𝑡 > 𝑛 then output( 𝑥 ); //葉子結點是可行解else for i=t to n do{swap(X[t],X[i]);if( Constraint(𝑡) and Bound( 𝑡 ) )	Backtrack(𝑡 + 1);swap(X[t],X[i]);}
}

問題實例

TSP 問題

旅行商問題。

旅行商從起點出發，遍歷圖中全部節點后回到原點，求最小代價。

一般的深度優先搜索如下所示：

1. 定義解空間：𝑋 = {12341, 12431, 13241, 13421, 14231, 14321}
2. 構造解空間樹；
3. 從A出發按DFS搜索整棵樹。

最優解：13241，14231
成本：25

回溯法基本思想：利用排列生成問題的回溯算法Backtrack(2)，對𝑥[] = {1, 2, … , 𝑛}的𝑥[2. . 𝑛]進行全排列，則 (𝑥[1] , 𝑥[2]),(𝑥[2], 𝑥[3]) , … , (𝑥[𝑛], 𝑥[1])構成一個回路。在全排列算法的基礎上，進行路徑計算保存以及進行限界剪枝。

偽代碼如下：

main( int n )
{
𝑎[𝑛][𝑛]; 𝑥[𝑛] = {1,2, … , 𝑛}; 
𝑏𝑒𝑠𝑡𝑥[]; cc=0;
𝑏𝑒𝑠𝑡𝑣 = ∞;//bestx保存當前最佳路徑，bestv保存當前最優值
input(𝑎); //輸入鄰接矩陣
TSPBacktrack(2);
output( 𝑏𝑒𝑠𝑡𝑣, 𝑏𝑒𝑠𝑡𝑥[]);
}TSPBacktrack(int i)
{// 𝑐𝑐記錄(𝑥[1], 𝑥[2]), … , (𝑥[𝑖 ? 1], 𝑥[𝑖])的距離和if(i>n){// 搜索到葉結點，輸出可行解與當前解比較if(cc +a[x[n]][1] < bestv or bestv = ∞){bestv = cc+a[x[n]][1];for(j=1;j<= n; j++) bestx[j]= x[j];}
}
else{for(j=i;j<=n;j++)if(cc+a[x[i-1]][x[j]]<bestv or bestv = ∞)// 限界裁剪子樹}swap(x[i],x[j]);cc += a[x[i-1]][x[i]];TSPBackstrack(i+1);cc -= a[x[i-1]][x[i]];swap(x[i],x[j]);
}

n皇后問題

為了便于分析，我們取n=4.

問題描述：在4 × 4棋盤上放上4個皇后，使皇后彼此不受攻擊。不受攻擊的條件是彼此不在同行（列）、斜線上。求出全部的放法。

解表示：

解編碼：(𝑥1, 𝑥2, 𝑥3, 𝑥4)四元組，𝑥𝑖表示皇后放在第𝑖行上的列號，如(3,1,2,4);
解空間：{ 𝑥1, 𝑥2, 𝑥3, 𝑥4 |𝑥𝑖 ∈ 𝑆, 𝑖 = 1~4)} 𝑆 = {1,2,3,4}

可行解滿足：

• 顯約束：𝑥𝑖 ∈ 𝑆, 𝑖 = 1~4
• 隱約束：

遞歸算法：

回溯法效率分析

效率影響因素：
通過前面具體實例的討論容易看出，回溯算法的效率在很大程度上依賴于以下因素：

• 產生𝑥[𝑡]的時間；
• 滿足顯約束的𝑥[𝑡]值的個數；
• 計算約束函數constraint的時間；
• 計算上界函數bound的時間；
• 滿足約束函數和上界函數約束的所有𝑥[𝑘]的個數。

好的約束函數能顯著地減少所生成的結點數。但這樣的約束函數往往計算量較大。因此，在選擇約束函數時通常存在生成結點數與約束函數計算量之間的折衷。

效率提高技巧：

對于許多問題而言，在搜索試探時選取𝑥[𝑖]的值順序是任意的。在其它條件相當的前提下，讓可取值最少的𝑥[𝑖]優先。從圖中關于同一問題的2棵不同解空間樹，可以體會到這種策略的潛力。