资源描述：
《ACM专题-搜索算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、ACM专题讲座——搜索算法肖明搜索算法1.搜索问题2.搜索方法分类3.回溯方法4.一般图搜索算法5.启发式搜索算法1.搜索问题人类的思维过程，可以看作一个搜索过程。我们遇到的很多智力游戏问题，如传教士和野人问题。有3个传教士和3个野人来到河边准备渡河，河岸有一条船，每次最多可乘坐2个人。问传教士为安全起见，应如何规划摆渡方案，使得在任何时刻，在河的两岸以及船上传教士人数不能少于野人的人数？对这个问题，在每一次渡河后，都会有几种渡河方案供选择，究竟哪种方案最有利？这就是搜索问题。1.搜索问题对这类问题，一般我们都转换为状态空间的搜索问题。如传教士和野人问题，可用在河左岸的传教
2、士人数、野人人数和船的情况来表示。即，初始时状态为（3，3，1），结束状态为（0，0，0），而中间状态可表示为（2，2，0）、（3，2，1）等等。初始状态结束状态LRLRm30m03c30c03B10B011.搜索问题由此，可以看出这类问题的解，就是一个合法状态的序列，其中序列中第一个状态是问题的初始状态，而最后一个状态则是问题的结束状态。如图所示即搜索问题的示意图：SgS0解路径搜索空间全状态空间2.搜索方法分类不可撤回方法试探性方法回溯方法图搜索方法3.回溯方法回溯方法，属于盲目搜索的一种，它是这样一种策略：首先将规则给出一个固定的排序，在搜索时，对当前状态依次检测每一
3、条规则，在当前状态未使用过的规则中找到第一条可应用规则，应用于当前状态，得到的新状态重新设置为当前状态，并重复以上搜索。如果当前状态无规则可用，或者所有规则已经被试探过仍未找到问题的解，则将当前状态的前一个状态（即直接生成该状态的状态）设置为当前状态。重复以上搜索，直到找到问题的解，或已试探过所有可能仍找不到问题的解为止。3.回溯方法例：皇后问题QQQQ3.回溯方法()()3.回溯方法()()((1,1))Q3.回溯方法()()((1,1))((1,1)(2,3))QQ3.回溯方法()()((1,1))((1,1)(2,3))Q3.回溯方法()()((1,1))((1,1)
4、(2,3))((1,1)(2,4))QQ3.回溯方法()()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))QQQ3.回溯方法()()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))QQ3.回溯方法()()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q3.回溯方法()()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))3.回溯方法()()((1,1))((1,1)(2,3))((1
5、,1)(2,4))((1,1)(2,4)(3.2))((1,2))Q3.回溯方法()()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))((1,2))((1,2)(2,4))QQ3.回溯方法()()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))((1,2))((1,2)(2,4))((1,2)(2,4)(3,1))QQQ3.回溯方法()()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))((1,2))((1,2)(2,4))((1
6、,2)(2,4)(3,1))((1,2)(2,4)(3,1)(4,3))QQQQ3.回溯方法递归的思想：当前状态目标状态g3.回溯方法算法描述：BACKTRACK1（DATALIST）DATALIST：从初始到当前的状态表（逆向）返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。3.回溯方法1,DATA:=FIRST(DATALIST)2,IFMENBER(DATA,TAIL(DATALIST))RETURNFAIL;3,IFTERM(DATA)RETURNNIL;4,IFDEADEND(DATA)RETURNFAIL;5,IFLENGTH(DATALIS
7、T)>BOUNDRETURNFAIL;6,RULES:=APPRULES(DATA);3.回溯方法7,LOOP:IFNULL(RULES)RETURNFAIL;8,R:=FIRST(RULES);9,RULES:=TAIL(RULES);10,RDATA:=GEN(R,DATA);11,RDATALIST:=CONS(RDATA,DATALIST);12,PATH:=BACKTRCK1(RDATALIST)13,IFPATH=FAILGOLOOP;14,RETURNCONS(R,PATH);4.一般图搜索算法问题的
