回溯算法(Backtracking)

什麼是回溯？

回溯是一種基本的搜尋算法，通過在搜尋過程中尋找問題的解，當發現已不滿足求解條件時，就"回溯"傳回，嘗試别的路經。在探索過程中，當探索到某一步時，發現原先搜尋并不優或達不到目标，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法，而滿足回溯條件的某個狀态的點稱為“回溯點”。

搜尋方式:

• 深度優先搜尋(dfs)
• 寬度優先搜尋(bfs)

基本思想

在包含問題的所有解的空間樹中，按照dfs的政策，從根結點出發深度探索空間樹。當探索到某一結點時，要先判斷該結點是否包含問題的解，如果包含，就從該結點出發繼續探索下去，如果該結點不包含問題的解，則逐層向其祖先結點回溯。（其實回溯法就是對隐式圖的深度優先搜尋算法）。

若用回溯法求問題的所有解時，要回溯到根，且根結點的所有可行的子樹都要已被搜尋遍才結束。

而若使用回溯法求任一個解時，隻要搜尋到問題的一個解就可以結束。

算法基本步驟

1. 滿足一定條件下将目前資料加入到結果集(或檢查到不滿足要求當即傳回)
2. 選擇一條路經
3. dfs向前進行
4. 回退路經

一些情況下需要對資料進行預先處理，或在第2步直接檢查以決定是否抛棄目前路經，以避免過多地遞歸，帶來時間損耗。換而言之，不滿足條件的路經越早抛棄越好。