信息学竞赛第34讲搜索算法..doc

信息学竞赛第34讲:搜索算法            信息学竞赛第34讲:搜索算法    搜索算法基础教程    大榕树            搜索算法是利用计算机的高性能来有目的的穷举一个问题的部分或所有的可能情况,从而求出问题的解的一种方法。搜索过程实际上是根据初始条件和扩展规则构造一棵解答树并寻找符合目标状态的节点的过程。所有的搜索算法从其最终的算法实现上来看,都可以划分成两个部分──控制结构和产生系统,而所有的算法的优化和改进主要都是通过修改其控制结构来完成的。现在主要对其控制结构进行讨论,因此对其产生系统作如下约定:FunctionExpendNode(Situation:Tsituation;ExpendWayNo:Integer):TSituation;表示对给出的节点状态Sitution采用第ExpendWayNo种扩展规则进行扩展,并且返回扩展后的状态。(本文所采用的算法描述语言为类Pascal。)一、回溯算法    回溯算法是所有搜索算法中最为基本的一种算法,其采用了一种“走不通就掉头”思想作为其控制结构,其相当于采用了先根遍历的方法来构造解答树,可用于找解或所有解以及最优解。具体的算法描述如下:[非递归算法]<Type>Node(节点类型)=Record    Situtation:TSituation(当前节点状态);    Way-NO:Integer(已使用过的扩展规则的数目);End<Var>List(回溯表):Array[1..Max(最大深度)]ofNode;pos(当前扩展节点编号):Integer;<Init>List<-0;pos<-1;List[1].Situation<-初始状态;<MainProgram>While(pos>0(有路可走))and([未达到目标])doBeginIfpos>=Maxthen(数据溢出,跳出主程序);List[pos].Way-NO:=List[pos].Way-No+1;If(List[pos].Way-NO<=TotalExpendMethod)then(如果还有没用过的扩展规则)Begin    If(可以使用当前扩展规则)then    Begin    (用第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-IfElseBegin    pos:=pos-1;    End-ElseEnd-While;[递归算法]ProcedureBackTrack(Situation:TSituation;deepth:Integer);VarI    :Integer;BeginIfdeepth>Maxthen(空间达到极限,跳出本过程);IfSituation=Targetthen(找到目标);ForI:=1toTotalExpendMethoddoBegin    BackTrack(ExpendNode(Situation,I),deepth+1);End-For            ;End;范例:一个M*M的棋盘上某