回溯法

回溯法（英語：backtracking）是暴力搜尋法中的一種。

對於某些計算問題而言，回溯法是一種可以找出所有（或一部分）解的一般性算法，尤其適用於約束滿足問題（在解決約束滿足問題時，我們逐步構造更多的候選解，並且在確定某一部分候選解不可能補全成正確解之後放棄繼續搜索這個部分候選解本身及其可以拓展出的子候選解，轉而測試其他的部分候選解）。

在經典的教科書中，八皇后問題展示了回溯法的用例。（八皇后問題是在標準國際象棋棋盤中尋找八個皇后的所有分布，使得沒有一個皇后能攻擊到另外一個。）

回溯法採用試錯的思想，它嘗試分步的去解決一個問題。在分步解決問題的過程中，當它通過嘗試發現，現有的分步答案不能得到有效的正確的解答的時候，它將取消上一步甚至是上幾步的計算，再通過其它的可能的分步解答再次嘗試尋找問題的答案。回溯法通常用最簡單的遞歸方法來實現，在反覆重複上述的步驟後可能出現兩種情況：

在最壞的情況下，回溯法會導致一次複雜度為指數時間的計算。

典型應用[編輯]

八皇后問題是應用回溯法求解的典型案例。