回溯法 · 算法

[TOC] # 概念回溯法有“通用解法”之稱。回溯法是一個既帶有系統性，又帶有跳躍性的搜索算法。算法搜索至解空間樹的任一節點時，先判斷該結點是否包含問題的解。如果肯定不包含，則跳過對以該結點為根的子樹的搜索，逐層向其祖先結點回溯。|否則，進入該子樹，繼續按深度優先策略搜索。回溯法問題求解時，要回溯到根，且根結點的所有子樹都已被搜索遍才結束。回溯法求問題的一個解時，只要搜索到一個解就可結束。 > 適用于解組合數較大的問題。 # 基本思想 * 約束條件 * 限界函數 # 步驟 * 針對所給的問題，定義問題的解空間； * 確定易于搜索的解空間； * 以深度優先方式搜索解空間，并在搜索的過程中用剪枝函數避免無效搜索。 #### 遞歸回溯 ``` void backtracking(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)) Backtracking(t+1); } } ``` 如上述代碼： t表示遞歸深度，即當前擴展結點在解空間樹中的深度； n用來控制遞歸的深度； t>n表示已經搜索到葉節點；此時，由Output(x)記錄或者輸出得到的可行解x； backtracking的for循環中f(n,t)和g(n,t)分別表示在當前擴展結點處未搜索過的子樹的起始編號和終止編號。 h(i)表示在當前擴展結點處x[t]的第i個可選值。 Constraint(t) 和 Bound(t)分別表示約束條件函數和限界函數，如果既沒有違反約束條件，也沒有違反越界函數，則遞歸下一層。調用一次backtracking(1)即可以完成整個回溯的搜索過程。 #### 迭代回溯 ``` void IterativeBacktrack(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--; } } ``` > 用回溯法解題的一個顯著特征是在搜索的過程中動態產生問題的解空間。在任何時刻，算法只保存從根結點到當前擴展結點的路徑。 # 子集樹和排列樹 * 子集樹：當所給問題是從n個元素的集合S中找出滿足某種性質的子集時，相應的解空間樹稱為子集樹。（0-1背包問題）搜索子集樹的一般算法： ``` void Backtrack(int t) { if(t>n) Output(x); else for(int i = 0;i <=1; i++) { x[t] = i; if(Constraint(t) && Bound(t)) Backtrack(t+1); } } ``` * 排列樹：當所給問題是確定n個元素滿足某種性質的排列時，相應的解空間樹稱為排列樹。（旅行售票員問題）搜索排列樹的一般算法： ``` void Backtrack(int t) { if(t>n) Output(x); else for(int i=t;i<=n;i++) { Swap(x[t],x[i]); //So smart if(Constraint(t) && Bound(t)) Backtrack(t+1); Swap(x[t],x[i]); } } ``` 在調用backtrack(1)執行回溯搜索之前，先將變量數組x初始化為單位排列(1,2,3,...,n)。 * Swap(x[t],x[i])的含義：如在旅行售票員問題中，假設默認x=[1,2,3,4]，其執行過程如下 backtrack(1) : t = 1; for 中 i = 1; swap(x[1],x[1]),即從1開始 backtrack(2) : t = 2; for 中 i = 2,n=4; swap(x[2],x[2])，考察2結點，如果不行，swap(x[2],x[3])，x數組變為x=[1,3,2,4],現在考察3結點。依次向下搜索。