基本介紹
- 中文名：回溯法
- 外文名：Back Tracking Method
- 全稱：探索與回溯法
- 屬性：選優搜尋法
- 別稱：試探法
基本思想,算法框架,
基本思想
在回溯法中，每次擴大當前部分解時，都面臨一個可選的狀態集合，新的部分解就通過在該集合中選擇構造而成。這樣的狀態集合，其結構是一棵多叉樹，每個樹結點代表一個可能的部分解，它的兒子是在它的基礎上生成的其他部分解。樹根為初始狀態，這樣的狀態集合稱為狀態空間樹。
回溯法對任一解的生成，一般都採用逐步擴大解的方式。每前進一步，都試圖在當前部分解的基礎上擴大該部分解。它在問題的狀態空間樹中，從開始結點（根結點）出發，以深度優先搜尋整個狀態空間。這個開始結點成為活結點，同時也成為當前的擴展結點。在當前擴展結點處，搜尋向縱深方向移至一個新結點。這個新結點成為新的活結點，並成為當前擴展結點。如果在當前擴展結點處不能再向縱深方向移動，則當前擴展結點就成為死結點。此時，應往回移動（回溯）至最近的活結點處，並使這個活結點成為當前擴展結點。回溯法以這種工作方式遞歸地在狀態空間中搜尋，直到找到所要求的解或解空間中已無活結點時為止。
回溯法與窮舉法有某些聯繫，它們都是基於試探的。窮舉法要將一個解的各個部分全部生成後，才檢查是否滿足條件，若不滿足，則直接放棄該完整解，然後再嘗試另一個可能的完整解，它並沒有沿著一個可能的完整解的各個部分逐步回退生成解的過程。而對於回溯法，一個解的各個部分是逐步生成的，當發現當前生成的某部分不滿足約束條件時，就放棄該步所做的工作，退到上一步進行新的嘗試，而不是放棄整個解重來。
算法框架
問題的解空間
套用回溯法求解問題時，首先應明確定義問題的解空間，該解空間應至少包含問題的一個最優解。例如，對於有n種物品的 0-1 背包問題，其解空間由長度為n的 0-1 向量組成，該解空間包含了對變數的所有可能的0-1 賦值。當 n=3 時，其解空間是{ (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1) }
在定義了問題的解空間後，還需要將解空間有效地組織起來，使得回溯法能方便地搜尋整個解空間，通常將解空間組織成樹或圖的形式。例如，對於n= 3的0-1 背包問題，其解空間可以用一棵完全二叉樹表示，從樹根到葉子結點的任意一條路徑可表示解空間中的一個元素，如從根結點A到結點J的路徑對應於解空間中的一個元素(1, 0, 1)。
回溯法解題的關鍵要素
確定了問題的解空間結構後，回溯法將從開始結點(根結點)出發，以深度優先的方式搜尋整個解空間。開始結點成為活結點，同時也成為擴展結點。在當前的擴展結點處，向縱深方向搜尋並移至一個新結點，這個新結點就成為一個新的活結點，並成為當前的擴展結點。如果在當前的擴展結點處不能再向縱深方向移動，則當前的擴展結點就成為死結點。此時應往回移動(回溯)至最近的一個活結點處，並使其成為當前的擴展結點。回溯法以上述工作方式遞歸地在解空間中搜尋，直至找到所要求的解或解空間中已無活結點時為止。
運用回溯法解題的關鍵要素有以下三點：
(1) 針對給定的問題，定義問題的解空間；
(2) 確定易於搜尋的解空間結構；
(3) 以深度優先方式搜尋解空間，並且在搜尋過程中用剪枝函式避免無效搜尋。
遞歸和疊代回溯
一般情況下可以用遞歸函式實現回溯法，遞歸函式模板如下：
void BackTrace(int t) {
if(t>n)
Output(x);
else
for(int i = f (n, t); i <= g (n, t); i++ ) {
x[t] = h(i);
if(Constraint(t) && Bound (t))
BackTrace(t+1);
}
}
其中，t 表示遞歸深度，即當前擴展結點在解空間樹中的深度；n 用來控制遞歸深度，即解空間樹的高度。當 t>n時，算法已搜尋到一個葉子結點，此時由函式Output(x)對得到的可行解x進行記錄或輸出處理。用 f(n, t)和 g(n, t)分別表示在當前擴展結點處未搜尋過的子樹的起始編號和終止編號；h(i)表示在當前擴展結點處x[t] 的第i個可選值；函式 Constraint(t)和 Bound(t)分別表示當前擴展結點處的約束函式和限界函式。若函式 Constraint(t)的返回值為真，則表示當前擴展結點處x[1:t] 的取值滿足問題的約束條件；否則不滿足問題的約束條件。若函式Bound(t)的返回值為真，則表示在當前擴展結點處x[1:t] 的取值尚未使目標函式越界，還需由BackTrace(t+1)對其相應的子樹做進一步地搜尋；否則，在當前擴展結點處x[1:t]的取值已使目標函式越界，可剪去相應的子樹。
採用疊代的方式也可實現回溯算法，疊代回溯算法的模板如下：
void IterativeBackTrace(void) {
int t = 1;
while(t>0) {
if(f(n, t) <= g( n, t))
for(int i = f(n, t); i <= g(n, t); i++ ) {
x[t] = h(i);
if(Constraint(t) && Bound(t)) {
if ( Solution(t))
Output(x);
else
t++;
}
}
else t− −;
}
}
在上述疊代算法中，用Solution(t)判斷在當前擴展結點處是否已得到問題的一個可行解，若其返回值為真，則表示在當前擴展結點處x[1:t] 是問題的一個可行解；否則表示在當前擴展結點處x[1:t]只是問題的一個部分解，還需要向縱深方向繼續搜尋。用回溯法解題的一個顯著特徵是問題的解空間是在搜尋過程中動態生成的，在任何時刻算法只保存從根結點到當前擴展結點的路徑。如果在解空間樹中，從根結點到葉子結點的最長路徑長度為 h(n)，則回溯法所需的計算空間複雜度為 O(h(n))，而顯式地存儲整個解空間複雜度則需要O(2h(n))或O(h(n)!)。
子集樹與排列樹
當給定的問題是從n個元素的集合S中找出滿足某種性質的子集時，相應的解空間樹稱為子集樹。例如，n個物品的0-1 背包問題所對應的解空間樹是一棵子集樹，該類樹通常有2n個葉子結點，總結點數為2n+1- 1，遍歷子集樹的任何算法需要的計算時間複雜度均為O(2n)。
回溯法搜尋子集樹的一般算法描述如下：
void BackTrace(int t) {
if(t>n)
Output(x);
else
for(int i = 0; i <= n; i++) {
x[t] = i;
if(Contraint(t) && Bound(t))
BackTrace (t + 1);
}
}
當給定的問題是確定 n 個元素滿足某種性質的排列時，對應的解空間樹稱為排列樹。排列樹通常有n! 個葉子結點，遍歷排列樹需要的計算時間複雜度為O(n!)。
回溯法搜尋排列樹的算法模板如下：
void BackTrace(int t) {
if(t>n)
Output(x);
else
for(int i = 0; i <= n; i++) {
Swap(x[t], x[i]);
if(Contraint (t) && Bound (t))
BackTrace(t + 1);
Swap(x[t], x[i]);
}
}
