演算法團隊6

Ⅰ 常見演算法思想6：回溯法

回溯法也叫試探法，試探的處事方式比較委婉，它先暫時放棄關於問題規模大小的限制，並將問題的候選解按某種順序逐一進行枚舉和檢驗。當發現當前候選解不可能是正確的解時，就選擇下一個候選解。如果當前候選解除了不滿足問題規模要求外能夠滿足所有其他要求時，則繼續擴大當前候選解的規模，並繼續試探。如果當前候選解滿足包括問題規模在內的所有要求時，該候選解就是問題的一個解。在試探演算法中，放棄當前候選解，並繼續尋找下一個候選解的過程稱為回溯。擴大當前候選解的規模，以繼續試探的過程稱為向前試探。

（1）針對所給問題，定義問題的解空間。
（2）確定易於搜索的解空間結構。
（3）以深度優先方式搜索解空間，並在搜索過程中用剪枝函數避免無效搜索。

回溯法為了求得問題的正確解，會先委婉地試探某一種可能的情況。在進行試探的過程中，一旦發現原來選擇的假設情況是不正確的，馬上會自覺地退回一步重新選擇，然後繼續向前試探，如此這般反復進行，直至得到解或證明無解時才死心。

下面是回溯的3個要素。
（1）解空間：表示要解決問題的范圍，不知道範圍的搜索是不可能找到結果的。
（2）約束條件：包括隱性的和顯性的，題目中的要求以及題目描述隱含的約束條件，是搜索有解的保證。
（3）狀態樹：是構造深搜過程的依據，整個搜索以此樹展開。

下面是影響演算法效率的因素：

回溯法搜索解空間時，通常採用兩種策略避免無效搜索，提高回溯的搜索效率:

為縮小規模，我們用顯示的國際象棋8*8的八皇後來分析。按照國際象棋的規則，皇後的攻擊方式是橫，豎和斜向。
皇後可以攻擊到同一列所有其它棋子，因此可推導出每1列只能存在1個皇後，即每個皇後分別占據一列。棋盤一共8列，剛好放置8個皇後。

為了擺放出滿足條件的8個皇後的布局，可以按如下方式逐步操作：

把規模放大到N行N列也一樣，下面用回溯法解決N皇後問題：

執行：