搜索入门李伟.pptx

搜索———按照一定的方法枚举解空间搜索算法是利用计算机的高性能来有目的的穷举一个问题的部分或所有的可能情况,从而求出问题的解的一种方法。搜索过程实际上是根据初始条件和扩展规则构造一棵解答树并寻找符合目标状态的节点的过程。想一想你会怎么做?比如说找到100以内所有能被3整除的正整数?如果这样————for(i=j=0;i<=100;i++){if(i%3==0)f[j++]=i;}这叫枚举,把所有的解判断一遍,从中选择符合条件的解作为answer如果…………for(i=1;i*3<=100;i++)f[i-1]=i*3;这叫搜索,按照一定的规律来寻找解空间,正是一个搜索的过程。搜索分类搜索中比较形象一点的就是对图的搜索,给你一个图形,然后利用图中的信息搜到解。按照解的不同分为深度搜索和广度搜索。深搜搜的是可能性(或者叫存在性),广搜搜的是最优解。SampleInput445...X...XD....345...X....D000SampleOutputNOYESHDOJ_1010TempteroftheBone题解这是一个广搜的例子,题目大意是让你判断从S能不能在给定的时间内走到D,可能看上去像是深搜搜可能性的,不过变换思考一下就会发现是广搜,如果你用广搜,搜到从S到D所需的最短时间minT,然后和给定的时间T比较一下,如果minT不大于T,那么就可以输出YES了,否者输出NO就行了如果改一下呢比如不给你限制时间T,直接问你从S能到达E吗?你该怎么做?这就是判断可能性的,判断一件事是可能还是不可能。我们可以用深搜,从源点S开始搜,如果能搜到D,那就返回,输出YES。深搜的简单代码段Voiddfs(当前点cur){if(找到符合条件点)returntrue;next=可能到达的后继点;if(后继结点集合为空)returnfalse;if(next没有走过){标记此点走过;dfs(next);重新置0;(表示此点还可以走)}回溯法回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试。这就可以用深搜来实现。1、定义一个解空间,它包含问题的解。2、利用适于搜索的方法组织解空间。3、利用深度优先法搜索解空间。4、利用限界函数避免移动到不可能产生解的子空间。问题的解空间通常是在搜索问题的解的过程中动态产生的,这是回溯算法的一个重要特性。