搜索算法全集

1、搜索算法全集（也是特別爽的哦，內(nèi)部資料?。?搜索算法搜索算法是利用計算機的高性能來有目的的窮舉一個問題的部分或所有的可 能情況，從而求出問題的解 的一種方法。搜索過程實際上是根據(jù)初始條件和擴展規(guī)則構(gòu)造一棵解答樹并尋找 符合目標狀態(tài)的節(jié)點的過程。所有的搜索算法從其最終的算法實現(xiàn)上來看，都可以劃分成兩個部分一一控制結(jié) 構(gòu)和產(chǎn)生系統(tǒng)，而所有的算 法的優(yōu)化和改進主要都是通過修改其控制結(jié)構(gòu)來完成的。 現(xiàn)在主要對其控制結(jié)構(gòu) 進行討論，因此對其產(chǎn)生系 統(tǒng)作如下約定：FunctionExpendNode（Situation:Tsituation;ExpendWayNo:Integer）:TSituation;

2、表示對給出的節(jié)點狀態(tài)Sitution 采用第ExpendWayN種擴展規(guī)則進行擴展，并 且返回擴展后的狀態(tài)。（本文所采用的算法描述語言為類 Pascal 。）第一部分 基本搜索算法一、回溯算法回溯算法是所有搜索算法中最為基本的一種算法， 其采用了一種“走不通就掉 頭”思想作為其控制結(jié)構(gòu)， 其相當于采用了先根遍歷的方法來構(gòu)造解答樹，可用于找解或所有解以及最優(yōu) 解。具體的算法描述如下： 非遞歸算法 <Type>Node（節(jié)點類型）=RecordSitutation:TSituation （當前節(jié)點狀態(tài)） ;Way-NO:Integer （已使用過的擴展規(guī)則的數(shù)目） ;End<Va

3、r>List（回溯表 ）:Array1.Max（最大深度 ） of Node;pos（ 當前擴展節(jié)點編號 ）:Integer;<Init>List<-0;pos<-1;List1.Situation<- 初始狀態(tài) ;<Main Program>While （pos>0（ 有路可走 ） and （ 未達到目標 ） doBeginIf pos>=Max then （ 數(shù)據(jù)溢出 , 跳出主程序 ）;Listpos.Way-NO:=Listpos.Way-No+1;If （Listpos.Way-NO<=TotalExpendMetho

4、d） then （ 如果還有沒用過的擴展規(guī) 則）BeginIf （ 可以使用當前擴展規(guī)則 ） thenBegin（ 用第 way 條規(guī)則擴展當前節(jié)點 ） Listpos+1.Situation:=ExpendNode（Listpos.Situation,Listpos.Way-NO）;Listpos+1.Way-NO:=0;pos:=pos+1;End-If;End-IfElse Begin pos:=pos-1;End-ElseEnd-While; 遞歸算法 Procedure BackTrack（Situation:TSituation;deepth:Integer）;Var I :Int

5、eger;BeginIf deepth>Max then （ 空間達到極限 , 跳出本過程 ）;If Situation=Target then （ 找到目標 ）;For I:=1 to TotalExpendMethod doBeginBackTrack（ExpendNode（Situation,I）,deepth+1）;End-For;End;范例：一個M*M的棋盤上某一點上有一個馬，要求尋找一條從這一點出發(fā)不重復 的跳完棋盤上所有的點的路線。評價：回溯算法對空間的消耗較少， 當其與分枝定界法一起使用時， 對于所求解 在解答樹中層次較深的問題有較好的效果。 但應避免在后繼節(jié)點可能與前

6、繼節(jié)點相同的問題中使用， 以 免產(chǎn)生循環(huán)。二、深度搜索與廣度搜索 深度搜索與廣度搜索的控制結(jié)構(gòu)和產(chǎn)生系統(tǒng)很相似， 唯一的區(qū)別在于對擴展節(jié) 點選取上。由于其保留了所有的前繼節(jié)點， 所以在產(chǎn)生后繼節(jié)點時可以去掉一部分重復的節(jié)點， 從而提高 了搜索效率。這兩種算法每次都擴展一個節(jié)點的所有子節(jié)點， 而不同的是， 深度搜索下一次擴展的是本次擴 展出來的子節(jié)點中的一個， 而廣度搜索擴展的則是本次擴展的節(jié)點的兄弟節(jié)點。 在具體實現(xiàn)上為了提高效率 所以采用了不同的數(shù)據(jù)結(jié)構(gòu) . 廣度搜索 <Type>Node（節(jié)點類型）=RecordSitutation:TSituation （當前節(jié)點狀態(tài)） ;

7、Level:Integer（ 當前節(jié)點深度 ）;Last :Integer（ 父節(jié)點 ）;End <Var>List（ 節(jié)點表 ）:Array1.Max（ 最多節(jié)點數(shù) ） of Node（ 節(jié)點類型 ）; open（ 總節(jié)點數(shù) ）:Integer;close（ 待擴展節(jié)點編號 ）:Integer;New-S:TSituation;（ 新節(jié)點 ）<Init>List<-0; open<-1;close<-0;List1.Situation<- 初始狀態(tài) ;List1.Level:=1;List1.Last:=0;<Main Program&g

8、t;While （close<open（ 還有未擴展節(jié)點 ） and （open<Max（ 空間未用完 ） and（ 未找到目標節(jié)點 ） doBeginclose:=close+1;擴展一層子節(jié)點）For I:=1 to TotalExpendMethod doBeginNew-S:=ExpendNode（Listclose.Situation,I）;If Not （New-S in List） then（ 擴展出的節(jié)點從未出現(xiàn)過 ）Beginopen:=open+1;Listopen.Situation:=New-S;Listopen.Level:=Listclose.Level

9、+1;Listopen.Last:=close;End-IfEnd-For;End-While; 深度搜索 <Var>Open:Array1.Max of Node;（Close:Array1.Max of Node;（待擴展節(jié)點表 ）已擴展節(jié)點表 ）openL,closeL:Integer;（ 表的長度 ）New-S:Tsituation;（ 新狀態(tài) ）<Init>初始狀態(tài);Open<-0; Close<-0; OpenL<-1;CloseL<-0; Open1.Situation<- Open1.Level<-1;Open1.La

10、st<-0;<Main Program>While (openL>0) and (closeL<Max) and (openL<Max) doBegin closeL:=closeL+1;ClosecloseL:=OpenopenL; openL:=openL-1;For I:=1 to TotalExpendMethod do (擴展一層子節(jié)點)BeginNew-S:=ExpendNode(ClosecloseL.Situation,I);If Not (New-S in List) then( 擴展出的節(jié)點從未出現(xiàn)過 )BeginopenL:=openL

11、+1;OpenopenL.Situation:=New-S;OpenopenL.Level:=ClosecloseL.Level+1;OpenopenL.Last:=closeL;End-IfEnd-For;End;范例：迷宮問題，求解最短路徑和可通路徑。 評價：廣度搜索是求解最優(yōu)解的一種較好的方法， 在后面將會對其進行進一步的 優(yōu)化。而深度搜索多用于只要求解，并且解答樹中的重復節(jié)點較多并且重復較難判斷時使用， 但往往可 以用A*或回溯算法代替。第二部分 搜索算法的優(yōu)化 一、雙向廣度搜索廣度搜索雖然可以得到最優(yōu)解， 但是其空間消耗增長太快。 但如果從正反兩個 方向進行廣度搜索，理想情況下可以減

12、少二分之一的搜索量，從而提高搜索速度。范例：有N個黑白棋子排成一派，中間任意兩個位置有兩個連續(xù)的空格。 每次空 格可以與序列中的某兩個棋子交換位置，且兩子的次序不變。要求出入長度為 length 的一個初始狀態(tài)和 一個目標狀態(tài)，求出最少的轉(zhuǎn)化步數(shù)。問題分析： 該題要求求出最少的轉(zhuǎn)化步數(shù)， 但如果直接使用廣度搜索， 很容易產(chǎn) 生數(shù)據(jù)溢出。但如果從初始狀態(tài)和目標狀態(tài)兩個方向同時進行擴展， 如果兩棵解答樹在某個節(jié)點第一 次發(fā)生重合，則該節(jié)點所連接的兩條路徑所拼成的路徑就是最優(yōu)解。 對廣度搜索算法的改進：1。添加一張節(jié)點表，作為反向擴展表。2。在while循環(huán)體中在正向擴展代碼后加入反向擴展代碼， 其

13、擴展過程不 能與正向過程共享一個 for 循環(huán)。3。在正向擴展出一個節(jié)點后，需在反向表中查找是否有重合節(jié)點。 反向擴 展時與之相同。對雙向廣度搜索算法的改進：略微修改一下控制結(jié)構(gòu)， 每次 while 循環(huán)時只擴展正反兩個方向中節(jié)點數(shù)目 較少的一個，可以使兩邊的發(fā)展速度保持一定的平衡，從而減少總擴展節(jié)點的個數(shù)，加快搜索速度。 二、分支定界分支定界實際上是A*算法的一種雛形，其對于每個擴展出來的節(jié)點給出一 個預期值，如果這個預期值不 如當前已經(jīng)搜索出來的結(jié)果好的話， 則將這個節(jié)點 （包括其子節(jié)點 ）從解答樹中刪 去，從而達到加快搜索速度的目的。 范例：在一個商店中購物，設第I種商品的價格為Ci。但

14、商店提供一種折扣， 即給出一組商品的組合，如果一次性購買了這一組商品， 則可以享受較優(yōu)惠的價格。 現(xiàn)在給出一張購買清單 和商店所提供的折扣清單，要求利用這些折扣，使所付款最少。問題分析： 顯然，折扣使用的順序與最終結(jié)果無關， 所以可以先將所有的折扣按 折扣率從大到小排序，然后采用回溯法的控制結(jié)構(gòu)，對每個折扣從其最大可能使用次數(shù)向零遞減搜 索，設 A 為以打完折扣后優(yōu)惠的價格，C為當前未打折扣的商品零售價之和，則其預期值為A+a*C,其中 a 為下一個折扣的折扣率。如當前已是最后一個折扣，則 a=1。 對回溯算法的改進：1。添加一個全局變量BestA nswer，記錄當前最優(yōu)解。2。在每次生成一

15、個節(jié)點時，計算其預期值，并與 BestAnswer比較。如果 不好，則調(diào)用回溯過程。三、A*算法A*算法中更一般的引入了一個估價函數(shù)f,其定義為f=g+h。其中g為到達當前 節(jié)點的耗費，而 h 表示對從當 前節(jié)點到達目標節(jié)點的耗費的估計。其必須滿足兩個條件：1。h 必須小于等于實際的從當前節(jié)點到達目標節(jié)點的最小耗費 h*。2。f 必須保持單調(diào)遞增。A*算法的控制結(jié)構(gòu)與廣度搜索的十分類似，只是每次擴展的都是當前待擴展節(jié) 點中 f 值最小的一個，如果 擴展出來的節(jié)點與已擴展的節(jié)點重復， 則刪去這個節(jié)點。 如果與待擴展節(jié)點重復， 如果這個節(jié)點的估價函數(shù) 值較小，則用其代替原待擴展節(jié)點，具體算法描述如

16、下： 范例：一個 3*3 的棋盤中有 1-8 八個數(shù)字和一個空格， 現(xiàn)給出一個初始態(tài)和一個 目標態(tài)，要求利用這個空格，用最少的步數(shù)，使其到達目標態(tài)。問題分析：預期值定義為 h=|x-dx|+|y-dy| 估價函數(shù)定義為 f=g+h 。<Type>Node（節(jié)點類型）=RecordSitutation:TSituation （當前節(jié)點狀態(tài)） g:Integer;（到達當前狀態(tài)的耗費 ）h:Integer;（預計的耗費 ）f:Real;（ 估價函數(shù)值 ）Last:Integer;（ 父節(jié)點 ）End <Var>List（ 節(jié)點表）:Array1.Max（ 最多節(jié)點數(shù)）of

17、Node（ 節(jié)點類型）; open（ 總節(jié)點數(shù) ）:Integer;close（ 待擴展節(jié)點編號 ）:Integer;New-S:Tsituation;（ 新節(jié)點 ）<Init>List<-0;open<-1;close<-0;初始狀態(tài);List1.Situation<- <Main Program>While （close<open（ 還有未擴展節(jié)點 ） and （open<Max（ 空間未用完 ） and（ 未找到目標節(jié)點 ） doBeginBeginclose:=close+1;For I:=close+1 to open do

18、 （Beginif List.f<Listclose.f thenBegin交換 List 和 Listclose;End-If;尋找估價函數(shù)值最小的節(jié)點 ）End-For;End;擴展一層子節(jié)點）For I:=1 to TotalExpendMethod doBeginNew-S:=ExpendNode（Listclose.Situation,I）If Not （New-S in List1.close） then（ 擴展出的節(jié)點未與已擴展的節(jié)點重復 ） BeginIf Not （New-S in Listclose+1.open） then（ 擴展出的節(jié)點未與待擴展的節(jié)點重復 ） B

19、eginopen:=open+1;Listopen.Situation:=New-S;Listopen.Last:=close;Listopen.g:=Listclose.g+cost;Listopen.h:=GetH（Listopen.Situation）;Listopen.f:=Listopen.h+Listopen.g;End-IfElse BeginIf Listclose.g+cost+GetH（New-S）Listsame.f then（ 擴展出來的節(jié)點的估價函數(shù)值小于與其相同的節(jié)點 ）BeginListsame.Situation:= New-S;Listsame.Last:=c

20、lose;Listsame.g:=Listclose.g+cost;Listsame.h:=GetH（Listopen.Situation）;Listsame.f:=Listopen.h+Listopen.g;End-If;End-Else;End-IfEnd-For;End-While;對A*算法的改進-分階段A*:當A*算法出現(xiàn)數(shù)據(jù)溢出時，從待擴展節(jié)點中取出若干個估價函數(shù)值較小的節(jié) 點，然后放棄其余的待擴展節(jié)點，從而可以使搜索進一步的進行下去。第三部分 搜索與動態(tài)規(guī)劃的結(jié)合例1.有一個棋子，其1、6面2、4面3、5面相對?，F(xiàn)給出一個 M*N的棋盤， 棋子起初處于 （1,1） 點，擺放狀態(tài)給

21、定，現(xiàn)在要求用最少的步數(shù)從（1,1）點翻滾到（M,N）點，并且1面向上。 分析：這道題目用簡單的搜索很容易發(fā)生超時，特別當 M N較大時。所以可以 考慮使用動態(tài)規(guī)劃來解題。對于一個棋子， 其總共只有 24種狀態(tài)。 在（1,1） 點時， 其向右翻滾至 （2,1） 點， 向上翻滾至 （1,2） 點。而任意（I , J）點的狀態(tài)是由（I-1，J）和（I , J-1 ）點狀態(tài)推導出來的。所 以如果規(guī)定棋子只能向上和向右翻滾，則可以用動態(tài)規(guī)劃的方法將到達（M N）點的所有可能的狀態(tài) 推導出來。顯然，從（ 1，1 ）到達（N, M）這些狀態(tài)的路徑時最優(yōu)的。如果這些狀態(tài)中有 1面向上的， 則已求出解。如果沒

22、有，則可以從（M N）點開始廣度搜索，以（M N）點的狀態(tài)組作為初始狀態(tài)， 每擴展一步時，檢查當前所得的狀態(tài)組是否有狀態(tài)與到達格子的狀態(tài)組中的狀態(tài)相同， 如果有，則由 動態(tài)規(guī)劃的最優(yōu)性和廣度搜索的最優(yōu)性可以保證已求出最優(yōu)解。例2.給出一個正整數(shù)n,有基本元素a,要求通過最少次數(shù)的乘法，求出 a"。 分析：思路一：這道題從題面上來看非常象一道動態(tài)規(guī)劃題，a5=aAx1*aAx2。在保證aAx1和aAx2的最優(yōu)性之后，aAn的最優(yōu)性應該得到保證。但是仔細分析后可以發(fā)現(xiàn)，aAx1與aAx2 的乘法過程中可能有一部分的重復， 所以在計算 aAn 時要減去其重復部分。 由于重復部分的 計算較繁

23、瑣，所以可以將其化為一組展開計算。描述如下：I:=n;（ 拆分 aAn）splitn:=x1;（分解方案 ）Usedn:=True;（ 在乘法過程中出現(xiàn)的數(shù)字 ）Repeat（ 不斷分解數(shù)字 ）UsedI-splitI:=True;UsedsplitI:=True;Dec（I）;While （I>1） and （not UsedI） do dec（I）;Until I=1;For I:=n downto 1 do（計算總的乘法次數(shù) ）If UsedI then count:=count+1;Result:=count;（ 返回乘法次數(shù) ） 思路二：通過對思路一的輸出結(jié)果的分析可以發(fā)現(xiàn)一個

24、規(guī)律：aA19=aA1*aA18aA18=aA2*aA16aA16=aA8*aA8aA8=aA4*aA4aA4=aA2*aA2aA2=a*a對于一個n,先構(gòu)造一個最接近的2Ak，然后利用在構(gòu)造過程中產(chǎn)生的2八|, 對 n-2Ak 進行二進制分解，可以得出解。對次數(shù)的計算的描述如下：count:=0;Repeat|f n mod 2 = 0 then count:=count+1Else count:=count+2; n:=n div 2;Until n=1;Result:=count; 反思：觀察下列數(shù)據(jù)：aA15 aA23 aA27Cost:5 Cost:6 Cost:6aA2=aA1*a

25、A1aA3=aA1*aA2aA6=aA3*aA3 aA12=aA6*aA6aA2=aA1*aA1aA3=aA1*aA2aA5=aA2*aA3 aA10=aA5*aA5aA2=aA1*aA1aA3=aA1*aA2 aA6=aA3*aA3aA12=aA6*aA6aA15=aA3*aA12aA20=aA10*aA10aA24=aA12*aA12aA23=aA3*aA20aA27=aA3*aA24這些數(shù)據(jù)都沒有采用思路二種的分解方法，而都優(yōu)于思路二中所給出的解。但是經(jīng)過實測，思路一二 的所有的解的情況相同，而卻得不出以上數(shù)據(jù)中的解。經(jīng)過對aA2aA15的數(shù)據(jù)的完全分析，發(fā)現(xiàn)對于一個aAn，存在多個分解

26、方法都可以得出最優(yōu)解，而在思路一中只保留了一 組分解方式。例如對于 aA6只保留了 aA2*aA4 ，從而使 aA3*aA3 這條路中斷，以至采用思路一的算法時 無法得出正確的耗費值，從而丟失了最優(yōu)解。 所以在計算 aAn=aAx1*aAx2 的重復時， 要引入一個搜索過程。例如 :aA15=aA3*aA12 ，&八12=&八6*&八6 ，而&八6=&八3*&八3。如果采用了 &八6=&八2*&八4，則必須多用一 步。<Type>Link=ANode; （使用鏈表結(jié)構(gòu)紀錄所有的可能解）Node=Recordsp

27、lit:Integer;next :Link;End;<Var>Solution:Array1.1000 of Link;（對于 aAn 的所有可能解）Cost :Array1.1000 of Integer;（解的代價）max :Integer;（推算的上界）<Main Program>Procedure GetSolution;Var i,j :Integer;min,c:Integer;count:Integer;temp,tail:Link;plan :Array1.500 of Integer; nUsed:Array1.1000 of Boolean;Procedure GetCost（From,Cost:Integer）; （搜索計算最優(yōu)解）Var temp:Link;a,b :Boolean;i :Integer;BeginIf Cost>c then Exit;（剪枝）If From=1 then （遞歸終結(jié)條件）BeginIf Cost<c then c:=Cost;Exit;End;temp:=Soluti