資源描述：
《中國數學建模-編程交流-搜索算法基礎》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。
1、中國數學建模-編程交流-搜索算法基礎搜索算法基礎搜索算法是利用計算機的高性能來有目的的窮舉一個問題的部分或所有的可能情況，從而求出問題的解的一種方法。搜索過程實際上是根據初始條件和擴展規(guī)則構造一棵解答樹并尋找符合目標狀態(tài)的節(jié)點的過程?！∷械乃阉魉惴◤钠渥罱K的算法實現上來看，都可以劃分成兩個部分──控制結構和產生系統(tǒng)，而所有的算法的優(yōu)化和改進主要都是通過修改其控制結構來完成的?，F在主要對其控制結構進行討論，因此對其產生系統(tǒng)作如下約定：FunctionExpendNode(Situation:Tsituation;ExpendWayNInteger):TSituation; 表示對給
2、出的節(jié)點狀態(tài)Sitution采用第ExpendWayNo種擴展規(guī)則進行擴展，并且返回擴展后的狀態(tài)。（本文所采用的算法描述語言為類Pascal。） 第一部分 基本搜索算法 一、回溯算法回溯算法是所有搜索算法中最為基本的一種算法，其采用了一種“走不通就掉頭”思想作為其控制結構，其相當于采用了先根遍歷的方法來構造解答樹，可用于找解或所有解以及最優(yōu)解。具體的算法描述如下：[非遞歸算法]＜Type＞ Node(節(jié)點類型)＝Record Situtation:TSituation（當前節(jié)點狀態(tài)）; Way-NInteger（已使用過的擴展規(guī)則的數目）;End＜Var＞ List(回溯表):Ar
3、ray[1..Max(最大深度)]ofNode; pos(當前擴展節(jié)點編號):Integer;＜Init＞ List＜-0; pos＜-1; List[1].Situation＜-初始狀態(tài);＜MainProgram＞ While(pos＞0(有路可走))and([未達到目標])do Begin Ifpos＞=Maxthen(數據溢出,跳出主程序); List[pos].Way-N=List[pos].Way-No+1; If(List[pos].Way-NO＜=TotalExpendMethod)then(如果還有沒用過的擴展規(guī)則) Begin If(可以使用當前擴展
4、規(guī)則)then Begin (用第way條規(guī)則擴展當前節(jié)點) List[pos+1].Situation:=ExpendNode(List[pos].Situation,List[pos].Way-NO); List[pos+1].Way-N=0; pos:=pos+1; End-If; End-If ElseBegin pos:=pos-1; End-Else End-While; [遞歸算法]ProcedureBackTrack(Situation:TSituation;deepth:Integer);VarI:Integer;Beg
5、in Ifdeepth＞Maxthen(空間達到極限,跳出本過程); IfSituation=Targetthen(找到目標); ForI:=1toTotalExpendMethoddo Begin BackTrack(ExpendNode(Situation,I),deepth+1); End-For;End; 范例：一個M*M的棋盤上某一點上有一個馬，要求尋找一條從這一點出發(fā)不重復的跳完棋盤上所有的點的路線?！ ≡u價：回溯算法對空間的消耗較少，當其與分枝定界法一起使用時，對于所求解在解答樹中層次較深的問題有較好的效果。但應避免在后繼節(jié)點可能與前繼節(jié)點相同的問題中使用，以
6、免產生循環(huán)?！《⑸疃人阉髋c廣度搜索 深度搜索與廣度搜索的控制結構和產生系統(tǒng)很相似，唯一的區(qū)別在于對擴展節(jié)點選取上。由于其保留了所有的前繼節(jié)點，所以在產生后繼節(jié)點時可以去掉一部分重復的節(jié)點，從而提高了搜索效率。這兩種算法每次都擴展一個節(jié)點的所有子節(jié)點，而不同的是，深度搜索下一次擴展的是本次擴展出來的子節(jié)點中的一個，而廣度搜索擴展的則是本次擴展的節(jié)點的兄弟節(jié)點。在具體實現上為了提高效率,所以采用了不同的數據結構. [廣度搜索]＜Type＞ Node(節(jié)點類型)＝Record Situtation:TSituation（當前節(jié)點狀態(tài)）; Level:Integer(當前節(jié)點深度);
7、Last:Integer(父節(jié)點);End＜Var＞ List(節(jié)點表):Array[1..Max(最多節(jié)點數)]ofNode(節(jié)點類型); open(總節(jié)點數):Integer; close(待擴展節(jié)點編號):Integer; New-S:TSituation;(新節(jié)點)＜Init＞ List＜-0; open＜-1; close＜-0; List[1].Situation＜-初始狀態(tài); List[1].Level:=1; List[1].Last:=0;＜Main
