搜索入门李伟.ppt

搜索入门
搜索是很多算法的基础
1
搜索———按照一定的方法枚举解空间
搜索算法是利用计算机的高性能来有目的的穷举一个问题的部分或所有的可能情况，从而求出问题的解的一种方法。搜索过程实际上是根据初始条件和扩展规则构造一棵解答树并寻找符合目标状态的节点的过程。
2
想一想你会怎么做？
比如说找到100以内所有能被3整除的正整数？
3
如果这样————
for(i = j = 0; i <= 100; i++){
if (i % 3 == 0)
f[j++] = i;
}
这叫枚举，把所有的解判断一遍，从中选择符合条件的解作为answer
4
如果 …………
for (i = 1; i * 3 <= 100; i++)
f[i - 1] = i * 3;
这叫搜索，按照一定的规律来寻找解空间，正是一个搜索的过程。
5
搜索分类
搜索中比较形象一点的就是对图的搜索，给你一个图形，然后利用图中的信息搜到解。按照解的不同分为深度搜索和广度搜索。
深搜搜的是可能性（或者叫存在性），广搜搜的是最优解。
6
Sample Input4 4 5...X...XD....3 4 5...X....D0 0 0
Sample OutputNOYES
HDOJ_1010 Tempter of the Bone
7
题解
这是一个广搜的例子，题目大意是让你判断从S能不能在给定的时间内走到D，可能看上去像是深搜搜可能性的，不过变换思考一下就会发现是广搜，如果你用广搜，搜到从S到D所需的最短时间minT，然后和给定的时间T比较一下，如果minT不大于T，那么就可以输出YES了，否者输出NO就行了
8
如果改一下呢
比如不给你限制时间T，直接问你从S能到达E吗？你该怎么做？
这就是判断可能性的，判断一件事是可能还是不可能。
我们可以用深搜，从源点S开始搜，如果能搜到D，那就返回，输出YES。
9
深搜的简单代码段
Void dfs(当前点cur)
{
if (找到符合条件点)
return true；
next = 可能到达的后继点；
if (后继结点集合为空)
return false;
if (next没有走过){
标记此点走过；
dfs(next)；
重新置0；(表示此点还可以走)
}
10