算法——回溯法

回溯法有“通用的解題法”之稱。用它可以系統地搜尋一個問題的所有解或任一解。回溯法是一種即帶有系統性又帶有跳躍性的搜尋算法。它在問題的解空間樹中，按深度優先政策，從根節點出發搜尋解空間樹。算法搜尋至解空間樹的任一結點時，先判斷該節點是否包含問題的解。如果不包含，則跳過對以該節點為根的子樹的搜尋，逐層向其它祖先節點回溯。否則，進入該子樹，繼續按照深度優先政策搜尋。回溯法求問題的所有解時，要回溯到根，且根節點的所有子樹都已被搜尋遍才結束。回溯法求問題的一個解時，隻要搜尋到問題的一個解就可結束。這種以深度優先方式系統搜尋問題的算法稱為回溯法，它是用于解組合數大的問題。

用回溯法解問題時，應明确定義問題的解空間。問題的解空間至少包含問題的一個（最優）解。例如對于有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背包問題，可用一顆完全的二叉樹表示其解空間，如下圖。

解空間樹的第i層到第i+1層邊上的标号給出了變量的值。從樹根到葉子的任一路徑表示解空間中的一個元素。例如，從根節點到節點H的路徑相當與解空間中的元素(1,1,1)。

确定了解空間的組織結構後，回溯法從根節點出發，以深度優先搜尋方式搜尋整個解空間。回溯法以這種工作方式遞歸地在解空間中搜尋，直到找到所要求的解或解空間所有解都被周遊過為止。

回溯法搜尋解空間樹時，通常采用兩種政策避免無效搜尋，提高回溯法的搜尋效率。其一是用限制函數在目前節點（擴充節點）處剪去不滿足限制的子樹；其二是用限界函數剪去得不到最優解的子樹。這兩類函數統稱為剪枝函數。

回溯法解題通常包含以下三個步驟：

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

2.确定易于搜尋的解空間結構；

3.以深度優先方式搜尋解空間，并在搜尋過程中用剪枝函數避免無效搜尋。

回溯法對解空間作深度優先搜尋，是以在一般情況下可用遞歸函數來實作回溯法。一般函數結構如下：

<a></a>

采用樹的非遞歸深度優先算法周遊算法，也可以将回溯法表示為一個非遞歸的疊代過程。一般函數形式如下：

用回溯法解體的一個顯著特征是在搜尋過程中動态産生問題的解空間。在任何時刻，算法隻儲存從根節點到目前節點（擴充節點）的路徑。如果解空間樹從根節點到葉節點的最長路徑的長度為h(n)，則回溯法所需的計算空間通常為O(h(n))。而顯式地存儲整個解空間則需要O(2^h(n))或O(h(n)!)記憶體空間。

八皇後問題是一個以國際象棋為背景的問題：如何能夠在 8×8 的國際象棋棋盤上放置八個皇後，使得任何一個皇後都無法直接吃掉其他的皇後？為了達到此目的，任兩個皇後都不能處于同一條橫行、縱行或斜線上。八皇後問題可以推廣為更一般的n皇後擺放問題：這時棋盤的大小變為n×n，而皇後個數也變成n。當且僅當 n = 1 或 n ≥ 4 時問題有解。

以下是n後問題的例子代碼：

n後問題

　　測試結果：帶入參數8，得到92種解，這個符合答案。

計算機算法設計與分析/王曉東編著。-3版。-北京：電子工業出版社，2007.5

本文轉自 Ron Ngai 部落格園部落格，原文連結：http://www.cnblogs.com/rond/archive/2012/07/10/2584044.html  ，如需轉載請自行聯系原作者