MATLAB-搜索算法.zip

中国数学建模-编程交流-搜索算法基础 登录 注册 搜索 风格 论坛状态 论坛展区 社区服务 社区休闲 网站首页 我能做什么 >> VC++,C,Perl,Asp...编程学习,算法介绍. 中国数学建模 → 学术区 → 编程交流 → 搜索算法基础 您是本帖的第 447 个阅读者 * 贴子主题：搜索算法基础 b 等级：职业侠客 文章：470 积分：956 门派：黑客帝国 注册：2003-8-28 鲜花(0) 鸡蛋(0) 楼主 搜索算法基础 搜索算法基础 搜索算法是利用计算机的高性能来有目的的穷举一个问题的部分或所有的可能情况，从而求出问题的解的一种方法。搜索过程实际上是根据初始条件和扩展规则构造一棵解答树并寻找符合目标状态的节点的过程。 　　所有的搜索算法从其最终的算法实现上来看，都可以划分成两个部分──控制结构和产生系统，而所有的算法的优化和改进主要都是通过修改其控制结构来完成的。现在主要对其控制结构进行讨论，因此对其产生系统作如下约定： Function ExpendNode(Situation:Tsituation;ExpendWayNInteger):TSituation; 　　表示对给出的节点状态Sitution采用第ExpendWayNo种扩展规则进行扩展，并且返回扩展后的状态。 （本文所采用的算法描述语言为类Pascal。） 　　第一部分　基本搜索算法 　　一、回溯算法 　　回溯算法是所有搜索算法中最为基本的一种算法，其采用了一种“走不通就掉头”思想作为其控制结构，其相当于采用了先根遍历的方法来构造解答树，可用于找解或所有解以及最优解。具体的算法描述如下： [非递归算法] ＜Type＞ 　Node(节点类型)＝Record 　Situtation:TSituation（当前节点状态）; 　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 Situation=Target then (找到目标); 　For I:=1 to TotalExpendMethod do 　　Begin 　　　BackTrack(ExpendNode(Situation,I),deepth+1); 　End-For; End; 　　范例：一个M*M的棋盘上某一点上有一个马，要求寻找一条从这一点出发不重复的跳完棋盘上所有的点的路线。 　　评价：回溯算法对空间的消耗较少，当其与分枝定界法一起使用时，对于所求解在解答树中层次较深的问题有较好的效果。但应避免在后继节点可能与前继节点相同的问题中使用，以免产生循环。 　　二、深度搜索与广度搜索 　　深度搜索与广度搜索的控制结构和产生系统很相似，唯一的区别在于对扩展节点选取上。由于其保留了所有的前继节点，所以在产生后继节点时可以去掉一部分重复的节点，从而提高了搜索效率。这两种算法每次都扩展一个节点的所有子节点，而不同的是，深度搜索下一次扩展的是本次扩展出来的子节点中的一个，而广度搜索扩展的则是本次扩展的节点的兄弟节点。在具体实现上为了提高效率,所以采用了不同的数据结构. 　　[广度搜索] ＜Type＞ 　Node(节点类型)＝Record 　Situtation:TSituation（当前节点状态）; 　Level:Integer(当前节点深度); 　Last :Integer(父节点); End ＜Var＞ 　List(节点表):Array[1..Max(最多节点数)] of Node(节点类型); 　open(总节点数):Integer; 　 close(待扩展节点编号):Integer; 　New-S:TSituation;(新节点) ＜Init＞ 　List＜-0; 　open＜-1; 　close＜-0; 　List[1].Situation＜- 初始状态; 　List[1].Level:=1; 　List[1].Last:=0; ＜Main Program＞ 　While (close＜open(还有未扩展节点)) and 　　(open＜Max(空间未用完)) and 　　(未找到目标节点) do 　Begin 　　 close:=close+1; 　　For I:=1 to TotalExpendMethod do（扩展一层子节点） 　　Begin 　　　New-S:=ExpendNode(List[close].Situation,I); 　　　If Not (New-S in List) then 　　　　(扩展出的节点从未出现过) 　　　Begin 　　　　open:=open+1; 　　　　List[open].Situation:=New-S; 　　　　List[open].Level:=List[close].Level+1; 　　　　List[open].Last:=close; 　　　End-If 　　End-For; 　End-While; 　　[深度搜索] ＜Var＞ 　Open:Array[1..Max] of Node;(待扩展节点表) 　Close:Array[1..Max] of Node;(已扩展节点表) 　openL,closeL:Integer;(表的长度) 　New-S:Tsituation;(新状态) ＜Init＞ 　Open＜-0; Close＜-0; 　OpenL＜-1;CloseL＜-0; 　Open[1].Situation＜- 初始状态; 　Open[1].Level＜-1; 　Open[1].Last＜-0; ＜Main Program＞ 　While (openL＞0) and (closeL＜Max) and (openL＜Max) do 　Begin 　　closeL:=closeL+1; 　　Close[closeL]:=Open[openL]; 　　openL:=openL-1; 　　For I:=1 to TotalExpendMethod do（扩展一层子节点） 　　Begin 　　　New-S:=ExpendNode(Close[closeL].Situation,I); 　　　If Not (New-S in List) then 　　　(扩展出的节点从未出现过) 　　　Begin 　　　　openL:=openL+1; 　　　　Open[openL].Situation:=New-S; 　　　　Open[openL].Level:=Close[closeL].Level+1; 　　　　Open[openL].Last:=closeL; 　　　End-If 　　End-For; End; 　　范例：迷宫问题，求解最短路径和可通路径。 　　评价：广度搜索是求解最优解的一种较好的方法，在后面将会对其进行进一步的优化。而深度搜索多用于只要求解，并且解答树中的重复节点较多并且重复较难判断时使用，但往往可以用A*或回溯算法代替。 第二部分　搜索算法的优化 　　一、双向广度搜索 　　广度搜索虽然可以得到最优解，但是其空间消耗增长太快。但如果从正反两个方向进行广度搜索，理想情况下可以减少二分之一的搜索量，从而提高搜索速度。 　　范例：有N个黑白棋子排成一派，中间任意两个位置有两个连续的空格。每次空格可以与序列中的某两个棋子交换位置，且两子的次序不变。要求出入长度为length的一个初始状态和一个目标状态，求出最少的转化步数。 　　问题分析：该题要求求出最少的转化步数，但如果直接使用广度搜索，很容易产生数据溢出。但如果从初始状态和目标状态两个方向同时进行扩展，如果两棵解答树在某个节点第一次发生重合，则�