搜索算法基礎(chǔ)

《搜索算法基礎(chǔ)》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、搜索算法基礎(chǔ)2003-07-30同濟大學(xué)編程之道搜索算法是利用計算機的高性能來有目的的窮舉一個問題的部分或所有的可能情況，從而求出問題的解的一種方法。搜索過程實際上是根據(jù)初始條件和擴展規(guī)則構(gòu)造一棵解答樹并尋找符合目標(biāo)狀態(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:Inte

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

3、（已使用過的擴展規(guī)則的數(shù)目）；EndList（回溯表）:Array［1..Max（最大深度）］ofNode;pos（當(dāng)前擴展節(jié)點編號）:Integer;List<-0;pos<-l;List[1].Situation<-初始狀態(tài)；VMainProgram>Wh訂e（pos>0（有路可走））and（[未達到目標(biāo)]）doBeginIfpos>=Maxthen（數(shù)據(jù)溢出，跳出主程序）;List[pos].Way-NO:=List[pos].Way-No+1;If（List[pos].Way-NO<=TotalExpendMet

4、hod—then（如果還有沒用過的擴展規(guī)則）BeginIf（可以使用當(dāng)前擴展規(guī)則）thenBegin（用第way條規(guī)則擴展當(dāng)前節(jié)點）List[pos+1]?Situation:二ExpendMode（List[pos]?Situation,List[pos]?Way-NO）:List[pos+1].Way-NO:=0;pos:=pos+l;End-If;End-IfElseBeginpos:二pos-1;End-ElseEnd-While;[遞歸算法]ProcedureBackTrack（Situation:TSituation;deepth

5、:Integer）;VarI:Integer;BeginIfdeepth>Maxthen（空間達到極限，跳出本過程）；IfSituation=Targetthen（找到目標(biāo)）;For1:二1toTotalExpendMethoddoBeginBackTrack（ExpendNode（Situation,I）,deepth+1）;End-For;End;范例：一個M*M的棋盤上某一點上有一個馬，要求尋找一條從這一點出發(fā)不重復(fù)的跳完棋盤上所有的點的路線。評價：回溯算法對空間的消耗較少，當(dāng)其與分枝定界法一起使用時，對于所求解在解答樹中層次較深的問題

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

7、ion:TSituation（當(dāng)前節(jié)點狀態(tài)）；Level:Integer（當(dāng)前節(jié)點深度）;Last:Integer（父節(jié)點）；EndList（節(jié)點表）:Array[1..Max（最多節(jié)點數(shù)）]ofNode（節(jié)點類型）；open（總節(jié)點數(shù)）:Integer;close（待擴展節(jié)點編號）:Integer;New-S:TSituation;（新節(jié)點）ListV-0;openVT;close<-0;List[l].Situation<-初始狀態(tài)；List[1].Level:=1;List[1].Last:=0;

8、ram>While（close