day3搜索-曹利国-noip培训.ppt

《day3搜索-曹利国-noip培训.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、搜索算法搜索算法的基本思想搜索是计算机解题中常用的方法，它实质上是枚举法的应用。由于它相当于枚举法，所以其效率是相当地低。因此，为了提高搜索的效率，人们想出了很多剪枝的方法，如分枝定界，启发式搜索等等。在竞赛中，我们不仅要熟练掌握这些方法，而且要因地制宜地运用一些技巧，以提高搜索的效率。定义：FunctionExpendNode(Situation:Tsituation;ExpendWayNo:Integer):TSituation;表示对给出的节点状态Sitution采用第ExpendWayNo种扩展规则进

2、行扩展，并且返回扩展后的状态。基本搜索算法一【回溯算法】回溯算法是采用了一种“走不通就掉头”思想作为其控制结构，用先根遍历的方法来构造解答树，可用于找所有解以及最优解。回溯算法对空间的消耗较少，当其与分枝定界法一起使用时，对于所求解在解答树中层次较深的问题有较好的效果。但应避免在后继节点可能与前继节点相同的问题中使用，以免产生循环。基本搜索算法一【回溯算法】Node(节点类型)＝RecordSitutation:TSituation（当前节点状态）;Way-NO:Integer（已使用过的扩展规则

3、的数目）;End基本搜索算法一【回溯算法】[递归算法]ProcedureBackTrack(Situation:TSituation;deepth:Integer);Vari:Integer;BeginIfdeepth>Maxthen(空间达到极限,跳出本过程);IfSituation=Targetthen(找到目标);ForI:=1toTotalExpendMethoddoBeginBackTrack(ExpendNode(Situation,I),deepth+1);End-For;End;构造字串生成长

4、度为n的字串，其字符从26个英文字母的前p(p≤26)个字母中选取，使得没有相邻的子序列相等。例如p=3，n=5时‘abcba’满足条件‘abcbc’不满足条件输入：n，p输出：所有满足条件的字串分析状态：待扩展的字母序号at。实际上字串s亦参与了递归运算，但是由于该变量的存储量太大，因此我们将s设为全局变量；边界条件和目标状态：产生了一个满足条件的字串，即at=n+1；搜索范围：第at位置可填的字母集{‘a’..chr(ord(‘a’)+p-1)}；约束条件：当前字串没有相邻子串相等的情况varn，p：in

5、teger；{字串长度和可选字母的个数}tl：longint；{满足条件的字串数}ed：char；{可选字母集中的最大字母}s：string；{满足条件的字串}proceduresolve(at：integer)；{递归扩展第at个字母}varch：char；i：integer；beginifat=n+1{若产生了一个满足条件的字串，则输出，满足条件的字串数+1}thenbeginwriteln(f，s)；inc(tl)；exit{回溯}end；{then}forch←'a'toeddo{搜索每一个可填字母}

6、begins←s+ch；i←1；{检查当前字串是否符合条件}while(i<=atdiv2)and(copy(s，length(s)-i+1，i)<>copy(s，length(s)-2*i+1，i))doinc(i)；ifi>atdiv2thensolve(at+1)；{若当前字串符合条件，则递归扩展下一个字母}delete(s，length(s)，1){恢复填前的字串}end{for}end；{solve}beginreadln(n，p)；{输入字串长度和前缀长短}ed←chr(ord('a')+p-1)

7、；{计算可选字母集中的最大字母}s←''；tl←0；{满足条件的字串初始化为空，字串数为0}solve(1)；{从第1个字母开始递归计算所有满足条件的字串}writeln('Total：'，tl)；{输出满足条件的字串数}end.{main}基本搜索算法[深度搜索与广度搜索]深度搜索与广度搜索的区别：深度搜索下一次扩展的是本次扩展出来的子节点中的一个，而广度搜索扩展的则是本次扩展的节点的兄弟节点。在具体实现上为了提高效率,所以采用了不同的数据结构。广度搜索是求解最优解的一种较好的方法，而深度搜索多用于只要求解

8、，并且解答树中的重复节点较多并且重复较难判断时使用，但往往可以用A*或回溯算法代替。搜索策略综合数据库与问题相关的所有数据元素构成的集合，用来表述问题状态或有关事实。产生式规则构建了综合数据库以后，还需要研究问题的移动规则，称为产生式规则。搜索策略搜索策略的实质是确定如何选取规则的方式。有两种基本方式：一种是不考虑给定问题所具有的特定知识，系统根据事先确定好某种固定顺序，依次调用规则或随机调用规则，