ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解.ppt

ACM算法设计BFS(广度搜索)-DFS(深度搜索)详解
1
专业课件,值得参考!
BFS算法
by plato
2
专业课件,值得参考!
复习DFS算法
思想: 一直往深处走,直到找到解或者走不下去为止
框架:
DFS(dep,…) //dep代表目前DFS的深度
{
if (找到解||走不下去了)
{
…
return;
}
枚举下一种情况,DFS(dep+1,…)
}
3
专业课件,值得参考!
DFS的遍历方式
H
A
L
I
F
B
C
D
E
J
G
K
S
4
专业课件,值得参考!
存在其他的遍历方式?
5
专业课件,值得参考!
BFS的思想
,利用规则,生成下一层的状态。
,看是否出现目标状态G。
否则就对该层所有状态节点,分别利用规则。生成再下一层的所有状态节点。
,这样一层一层往下展开。直到出现目标状态为止。
按层次的顺序来遍历搜索树
6
专业课件,值得参考!
BFS框架
通常用队列(先进先出,FIFO)实现
初始化队列Q.
Q={起点s}; 标记s为己访问;
while (Q非空) {
取Q队首元素u; u出队;
if (u == 目标状态) {…}
所有与u相邻且未被访问的点进入队列;
标记u为已访问;
}
7
专业课件,值得参考!
8
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
入口
出口
寻找一条从入口到出口的通路
迷宫问题
8
专业课件,值得参考!
东
南
北(上)
西(左)
前进方向:上(北)、下(南)、左(西)、右(东)
首先从下方开始,按照逆时针方向搜索下一步可能前进的位置
迷宫问题-DFS
9
专业课件,值得参考!
入口
出口
在迷宫周围加墙,避免判断是否出界
8
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
9
0
9
0
迷宫问题-DFS
10
专业课件,值得参考!