回溯搜索算法

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

1、補(bǔ)充22回溯法ò理解回溯法的深度優(yōu)先搜索策略。ò掌握用回溯法解題的算法框架（1）遞歸回溯（2）迭代回溯（3）子集樹算法框架（4）排列樹算法框架ò通過應(yīng)用范例學(xué)習(xí)回溯法的設(shè)計(jì)策略。1算法導(dǎo)論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算法導(dǎo)論Sch2-1方法概述ò搜索空間的三種表示：—表序表示：搜索對象用線性表數(shù)據(jù)結(jié)構(gòu)表示；—顯示圖表示：搜索對象在搜索前就用圖（樹）的數(shù)據(jù)結(jié)構(gòu)表示；—隱式圖表示：除了初始結(jié)點(diǎn)，其他結(jié)點(diǎn)在搜索過程中動(dòng)態(tài)生成。緣于搜索空間大，難以全部存儲(chǔ)。ò搜索效率的思考：隨機(jī)搜索—上世紀(jì)70年代中期開始，國外一些學(xué)者致力于研究隨機(jī)搜索求解困難的組合問題，將隨機(jī)過程引入搜索；—選擇規(guī)則是隨機(jī)地從可選結(jié)點(diǎn)中取一個(gè)，從而可以從統(tǒng)計(jì)角度分析搜索的平均性能；—隨機(jī)搜索的一個(gè)成功例子是：判定一個(gè)很大的數(shù)是不是素?cái)?shù)，

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

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

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

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

7、時(shí)間為Ω(n!)。9算法導(dǎo)論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算法導(dǎo)論Sch2-1方法概述11算法導(dǎo)論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、法導(dǎo)論Sch2-1方法概述ò用回溯法解題的一個(gè)顯著特征是在搜索過程中動(dòng)態(tài)產(chǎn)生問題的解空間。在任何時(shí)刻，算法只保存從根結(jié)點(diǎn)到當(dāng)前擴(kuò)展結(jié)點(diǎn)的路徑。如果解空間樹中從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的最長