1. 首頁 > 生活經驗 > >

什么是回溯法

生活百科什么

回溯法是一種選優搜索法，又稱為試探法 ， 按選優條件向前搜索，以達到目標 。但當探索到某一步時，發現原先選擇并不優或達不到目標 ， 就退回一步重新選擇 ， 這種走不通就退回再走的技術為回溯法，而滿足回溯條件的某個狀態的點稱為“回溯點” 。
【什么是回溯法】在回溯法中，每次擴大當前部分解時，都面臨一個可選的狀態集合，新的部分解就通過在該集合中選擇構造而成 。這樣的狀態集合 ， 其結構是一棵多叉樹，每個樹結點代表一個可能的部分解，它的兒子是在它的基礎上生成的其他部分解 。樹根為初始狀態，這樣的狀態集合稱為狀態空間樹 。