搜索算法基础.doc

《搜索算法基础.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、搜索算法基础2003-07-30同济大学编程之道搜索算法是利用计算机的高性能来有目的的穷举一个问题的部分或所有的可能情况，从而求出问题的解的一种方法。搜索过程实际上是根据初始条件和扩展规则构造一棵解答树并寻找符合冃标状态的节点的过程。所有的搜索算法从其最终的算法实现上来看，都可以划分成两个部分——控制结构和产生系统，而所有的算法的优化和改进主要都是通过修改其控制结构來完成的。现在主要对其控制结构进行讨论，因此对其产生系统作如下约定：FunctionExpendNode（Situation:Tsituation;ExpendWayNo:Integer）:TSituatio

2、n;表示对给出的节点状态Sitution采用第ExpendWayNo种扩展规则进行扩展，并且返回扩展后的状态。（本文所采用的算法描述语言为类Pascalo）第一部分基本搜索算法一、回溯算法回溯算法纭所有搜索算法中最为基本的一种算法，其采用了一种“走不通就掉头”思想作为其控制结构，其相当于采用了先根遍彷的方法来构造解答树，可用于找解或所有解以及最优解。具体的算法描述如下：［非递归算法］Node（节点类型）=RecordSitutation:TSituation（当前节点状态）；Way-N0:Integer（已使用过的扩展规则的数B）;EndList（

3、回溯表）:Array［1..Max（最大深度）］ofNode;pos（当前扩展节点编号）：Integer;List<~0;pos<~l;List［1］.Situation<-初始状态;While（pos>0（有路可走））and（［未达到目标］）doBeginIfpos>=Maxthen（数据溢出，跳出主程序）；List[pos]・Way-NO:二List[pos].Way-No+1;Tf（List[pos].Way-NO<=TotalExpendMethod=then（如果还有没用过的扩展规则）BeginTf（可以使用当前扩展规则）

4、thenBegin（用第way条规则扩展当前节点）List[pos+1]・Situation:二ExpendNode（List[pos]・Situation,List[pos]・Way-NO）;List[pos+1].Way-NO:二0;pos:二pos+1;End-If;End-IfElseBeginpos:二pos-1;End-ElseEnd-While;[递归算法]ProcedureBackTrack（Situation:TSituation;deepth:Integer）;VarI:Integer;BeginIfdeepth>Maxthen（空间达到极限，跳出本

5、过程）;IfSituation二Targetthen（找到目标）;For1:二1toTotalExpendMethoddoBeginBackTrack（ExpendNode（Situation,I）,deepth+1）;End-For;End;范例：一个的棋盘上某一点上有一个马，要求寻找一条从这一点出发不重复的跳完棋盘上所有的点的路线。评价：回溯算法对空间的消耗较少，当其与分枝定界法一起使用时，对于所求解在解答树屮层次较深的问题有较好的效果。但应避免在后继节点可能与前继节点相同的问题中使用，以免产生循环。二、深度搜寧与广度搜李深度搜索与「度搜索的控制结构和产生系统很相似

6、，唯一的区别在于对扩展节点选取上。由于其保留了所有的前继节点，所以在产生后继节点吋可以去掉一部分重复的节点，从而提高了搜索效率。这两种算法每次都扩展一个节点的所有子节点，而不同的是，深度搜索下一次扩展的是本次扩展出来的子节点中的一个，而广度搜索扩展的则是本次扩展的节点的兄弟节点。在具体实现上为了提高效率，所以釆用了不同的数据结构.[广度搜索]Node（节点类型）^RecordSitutation:TSituation（当前节'点状态）；Level:Integer（当前节点深度）；Last:Integer（父节点）；EndList（节点表）:Arra

7、y[1..Max（最多节点数）]ofNode（节点类型）；open（总节点数）:Integer;close（待扩展节点编号）:Integer;New-S:TSituation;（新节点）List<-0;open<-l;close<-0;List[l].Situation<-初始状态；List[1]・Level:=1;List[1].Last:=0;While（closeVopen（还有未扩展节点）=and（open