(原創(chuàng)精品)回溯法

《(原創(chuàng)精品)回溯法》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。

1、回溯法概述回溯法(探索與回溯法)是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達到目標。但當探索到某一步時，發(fā)現(xiàn)原先選擇并不優(yōu)或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法，而滿足回溯條件的某個狀態(tài)的點稱為“回溯點”?；厮莘ㄔ趩栴}的解空間樹中，按深度優(yōu)先策略，從根結點出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點時，先判斷該結點是否包含問題的解。如果肯定不包含，則跳過對該結點為根的子樹的搜索，逐層向其祖先結點回溯；否則，進入該子樹，繼續(xù)按深度優(yōu)先策略搜索?；厮莘ǎ簽榱吮苊馍赡切┎豢赡墚a(chǎn)生最佳解的問題狀態(tài)，要不斷地利用限界函數(shù)(boundingfunction)來處死

2、那些實際上不可能產(chǎn)生所需解的活結點，以減少問題的計算量。具有限界函數(shù)的深度優(yōu)先生成法稱為回溯法回溯法搜索解空間樹時，通常采用兩種策略避免無效搜索，提高回溯法的搜索效率：①用約束函數(shù)在擴展結點處剪去不滿足約束的子樹；②用限界函數(shù)剪去得不到最優(yōu)解的子樹。這兩類函數(shù)統(tǒng)稱為剪枝函數(shù)3個步驟:(1)針對所給問題，定義問題的解空間；(2)確定易于搜索的解空間結構；(3)以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。遞歸回溯回溯法對解空間作深度優(yōu)先搜索，因此，在一般情況下用遞歸方法實現(xiàn)回溯法。迭代回溯采用樹的非遞歸深度優(yōu)先遍歷算法，可將回溯法表示為一個非遞歸迭代過程。用回溯法解題

3、的一個顯著特征是在搜索過程中動態(tài)產(chǎn)生問題的解空間。在任何時刻，算法只保存從根結點到當前擴展結點的路徑。如果解空間樹中從根結點到葉結點的最長路徑的長度為h(n)，則回溯法所需的計算空間通常為O(h(n))。而顯式地存儲整個解空間則需要O(2h(n))或O(h(n)!)內存空間。用回溯法解題時用到的兩類解空間樹：子集樹：當所給的問題是從n個元素的集合S中找出滿足某種性質的子集時，相應的解空間樹排列數(shù)：當所給的問題是確定n個元素滿足某種性質的排列時，相應的解空間樹