文档介绍：搜索
人肉搜索
google
度娘
爬虫
文件查找
什么是搜索算法呢?
搜索算法是利用计算机的高性能来有目的地穷举一个问题的部分或所有的可能情况,从而求出问题的解的一种方法。

搜索过程实际上是根据初始条件和扩展规则构造一棵解答树并寻找符合目标状态的节点的过程。
what
....
A*
广搜
贪心算法
回溯
深搜
广度优先搜索:从初始状态开始,通过规则来生成第一层结点,,并检查是否有目标结点…
广度优先搜索
广度优先搜索
采用队列存储
每次扩展出当前结点的所有子结点
0
1
2
3
4
5
6
广度优先搜索
void BFS(int curNode,int curDepth){
while(front < rear) {
++front;
for(i = 0; i < m; i++) {
newNode = Expend(q[front].node)
if(!Exist(newNode)) {
q[rear++].node = newnode;
}
if(newNode == target) return ;
}
}
return;
}
搜索算法举例:八数码难题
在3×3的方格棋盘上,分别放置了标有数字1、2、3、4、5、6、7和8的八个棋子
5
8
4
7
3
6
2
1
5
8
4
7
3
6
2
1
S0
初始
状态
Sg
目标
状态
空出一个位置使棋子可以移动,形成不同的局面
问题要使棋盘进入某种预定局面应如何移动棋子
广度优先搜索算法举例
2 3
1 8 4
7 6 5
1
2
5
6
7
3
目标
8
4
0层
1层
2层
3层
2 3
1 8 4
7 6 5
2 8 3
1 4
7 6 5
2 3
1 8 4
7 6 5
下
左
右
2 8 3
1 4
7 6 5
2 8 3
1 6 4
7 5
2 8 3
1 4
7 6 5
下
左
右
1 2 3
8 4
7 6 5
下
2 3 4
1 8
7 6 5
下
2 8 3
1 6 4
7 5
2 8 3
1 6 4
7 5
左
右
2 8 3
7 1 4
6 5
8 3
2 1 4
7 6 5
上
下
2 8
1 4 3
7 6 5
2 8 3
1 4 5
7 6
上
下
1 2 3
7 8 4
6 5
1 2 3
8 4
7 6 5
下
右
规则:空格上下左右