中国数学建模-编程交流-搜索算法基础 搜索算法基础 搜索算法是利用计算机的高性能来有目的的穷举一个问题的部分或所有的可能情况，从而求出问题的解的一种方法。搜索过程实际上是根据初始条件和扩展规则构造一棵解答树并寻找符合目标状态的节点的过程。 所有的搜索算法从其最终的算法实现上来看，都可以划分成两个部分──控制结构和产生系统，而所有的算法的优化和改进主要都是通过修改其控制结构来完成的。现在主要对其控制结构进行讨论，因此对其产生系统作如下约定： Fu nction Ex pendNode(Situ ation:Tsitu ation;Ex pendWay NInteger):TSitu ation; 表示对给出的节点状态 Situ tion 采用第 Ex pendWay No 种扩展规则进行扩展，并且返回扩展后的状态。 （本文所采用的算法描述语言为类Pascal。） 第一部分 基本搜索算法 一、回溯算法 回溯算法是所有搜索算法中最为基本的一种算法，其采用了一种“走不通就掉头”思想作为其控制结构，其相当于采用了先根遍历的方法来构造解答树，可用于找解或所有解以及最优解。具体的算法描述如下： [非递归算法] ＜Ty pe＞ Node(节点类型)＝Record Situ tation:TSitu ation（当前节点状态）; Way -NInteger（已使用过的扩展规则的数目）; End ＜Var＞ List(回溯表):Array [1..Max (最大深度)] of Node; pos(当前扩展节点编号):Integer; ＜Init＞ List＜-0; pos＜-1; List[1].Situation＜-初始状态; ＜Main Program＞ While (pos＞0(有路可走)) and ([未达到目标]) do Begin If pos＞=Max then (数据溢出,跳出主程序); List[pos].Way-N=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-N=0; pos:=pos+1; End-If; End-If Else Begin pos:=pos-1; End-Else End-While; [递归算法] Procedure BackTrack(Situation:TSituation;deepth:Integer); Var I :Integer; Begin If deepth＞Max then (空间达到极限,跳出本过程); If Situ ation=Target then (找到目标); For I:=1 to TotalEx pendMethod do Begin BackTrack(Ex pendNode(Situ ation,I),deepth+1); End-For; End; 范...
