回溯搜索算法

《回溯搜索算法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、補充22回溯法ò理解回溯法的深度優(yōu)先搜索策略。ò掌握用回溯法解題的算法框架（1）遞歸回溯（2）迭代回溯（3）子集樹算法框架（4）排列樹算法框架ò通過應用范例學習回溯法的設(shè)計策略。1算法導論Sch2-1方法概述ò搜索算法介紹（1）窮舉搜索（2）盲目搜索—深度優(yōu)先(DFS)或回溯搜索(Backtracking);—廣度優(yōu)先搜索(BFS);—分支限界法(Branch&Bound)(Branch&Bound)；—博弈樹搜索(α-βSearch)（3）啟發(fā)式搜索—A*算法和最佳優(yōu)先(Best-FirstSearch)—迭代加深的A*算法—B*,AO*

2、,SSS*等算法—LocalSearch,GA等算法2算法導論Sch2-1方法概述ò搜索空間的三種表示：—表序表示：搜索對象用線性表數(shù)據(jù)結(jié)構(gòu)表示；—顯示圖表示：搜索對象在搜索前就用圖（樹）的數(shù)據(jù)結(jié)構(gòu)表示；—隱式圖表示：除了初始結(jié)點，其他結(jié)點在搜索過程中動態(tài)生成。緣于搜索空間大，難以全部存儲。ò搜索效率的思考：隨機搜索—上世紀70年代中期開始，國外一些學者致力于研究隨機搜索求解困難的組合問題，將隨機過程引入搜索；—選擇規(guī)則是隨機地從可選結(jié)點中取一個，從而可以從統(tǒng)計角度分析搜索的平均性能；—隨機搜索的一個成功例子是：判定一個很大的數(shù)是不是素數(shù)，

3、獲得了第個多式時第一個多項式時間的算法算法。3算法導論Sch2-1方法概述ò回溯法：—回溯法是一個既帶有系統(tǒng)性又帶有跳躍性的搜索算法；—它在包含問題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根結(jié)點出發(fā)搜索解空間樹。——系統(tǒng)性—算法搜索至解空間樹的任一結(jié)點時，判斷該結(jié)點為根的子樹是否包含問題的解，如果肯定不包含，則跳過以該結(jié)點為根的子樹的搜索，逐層向其祖先結(jié)點回溯。否則，進入該子樹，繼續(xù)深度優(yōu)先的策略進行搜索?！S性—這種以深度優(yōu)先的方式系統(tǒng)地搜索問題的解得算法稱為回溯法，它適用于解一些組合數(shù)較大的問題。4算法導論Sch2-1方法概述ò

4、問題的解空間—問題的解向量：回溯法希望一個問題的解能夠表示成一個n元式(x,x,…,x)12n的形式?！@約束：對分量x的取值限定。i—隱約束：為滿足問題的解而對不同分量之間施加的約束?！饪臻g：對于問題的一個實例，解向量滿足顯式約束條件的所有多元組，構(gòu)成了該實例的一個解空間。注意：同一個問題可以有多種表示，有些表示方法更簡單，所需表示的狀態(tài)空間更小（存儲量少，搜索方法簡單）。n=3時的0-1背包問題用完全二叉樹表示的解空間5算法導論Sch2-1方法概述6算法導論Sch2-1方法概述ò基本思想：—搜索從開始結(jié)點（根結(jié)點）出發(fā)，以深度優(yōu)先搜索

5、整個解空間?！@個開始結(jié)點成為活結(jié)點，同時也成為當前的擴展結(jié)點。在當前的擴展結(jié)點處，搜索索移向縱深方向移至一個新新結(jié)點。這這新個新結(jié)點就成成新為新的活結(jié)點，并成為當前擴展結(jié)點。—如果在當前的擴展結(jié)點處不能再向縱深方向擴展，則當前擴展結(jié)點就成為死結(jié)點?！藭r，應往回移動（回溯）至最近的一個活結(jié)點處，并使這個活結(jié)點成為當前的擴展結(jié)點；直到找到一個解或全部解。7算法導論Sch2-1方法概述ò基本步驟：①針對所給問題，定義問題的解空間；②確定易于搜索的解空間結(jié)構(gòu)；③以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。常用剪枝函數(shù)：①用約

6、束函數(shù)在擴展結(jié)點處剪去不滿足約束的子樹；②用限界函數(shù)剪去得不到最優(yōu)解的子樹。8算法導論Sch2-1方法概述ò二類常見的解空間樹：①子集樹：當所給的問題是從n個元素的集合S中找出滿足某種性質(zhì)的子集時，相應的解空間樹稱為子集樹。子集樹通常有2n個葉子結(jié)點，其總結(jié)點個數(shù)為2n+1-1，遍歷子集樹時間為Ω(2n)。如0-1背包問題，葉結(jié)點數(shù)為2n，總結(jié)點數(shù)2n+1；②排列樹：當所給問題是確定n個元素滿足某種性質(zhì)的排列時，相應的解空間樹稱為排列樹。排列樹通常有n!個葉子結(jié)點，因此，遍歷排列樹需要Ω(n!)的計算時間。如TSP問題，葉結(jié)點數(shù)為n!，遍歷

7、時間為Ω(n!)。9算法導論Sch2-1方法概述例1[0-1背包]：n=3,w=(16,15,15),v=(45,25,25),c=30(1)定義解空間：X={(0,0,0),(0,0,1),(0,1,0),…,(1,1,0),(1,1,1)}(2)構(gòu)造解空間樹：10算法導論Sch2-1方法概述11算法導論Sch2-1方法概述ò例2[TSP問題]:（1）定義解空間：X={12341,12431,13241,13421,14231,14321}（2）構(gòu)造解空間樹：（3）從A出發(fā)按DFS搜索整棵樹：最優(yōu)解：13241，14231成本：2512算

8、法導論Sch2-1方法概述ò用回溯法解題的一個顯著特征是在搜索過程中動態(tài)產(chǎn)生問題的解空間。在任何時刻，算法只保存從根結(jié)點到當前擴展結(jié)點的路徑。如果解空間樹中從根結(jié)點到葉結(jié)點的最長