什麼是回溯法

回溯法是一種選優搜索法，又稱為試探法，按選優條件向前搜索，以達到目標。但當探索到某一步時，發現原先選擇並不優或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法，而滿足回溯條件的某個狀態的點稱為“回溯點”。

在回溯法中，每次擴大當前部分解時，都面臨一個可選的狀態集合，新的部分解就通過在該集合中選擇構造而成。這樣的狀態集合，其結構是一棵多叉樹，每個樹結點代表一個可能的部分解，它的兒子是在它的基礎上生成的其他部分解。樹根為初始狀態，這樣的狀態集合稱為狀態空間樹。