回溯法是一種選優搜索法,又稱為試探法,按選優條件向前搜索,以達到目标。但當探索到某一步時,發現原先選擇并不優或達不到目标,就退回一步重新選擇,這種走不通就退回再走的技術為回溯法,而滿足回溯條件的某個狀态的點稱為“回溯點”。
在回溯法中,每次擴大當前部分解時,都面臨一個可選的狀态集合,新的部分解就通過在該集合中選擇構造而成。這樣的狀态集合,其結構是一棵多叉樹,每個樹結點代表一個可能的部分解,它的兒子是在它的基礎上生成的其他部分解。樹根為初始狀态,這樣的狀态集合稱為狀态空間樹。
更多精彩资讯请关注tft每日頭條,我们将持续为您更新最新资讯!