搜索-by-superbin.ppt

搜索-by-superbin
目录
(Depth-first search)
(Breadth-first search)
深度优先搜索
国际象棋，大家应该都听说过吧。
国际象棋，又
再看这幅图，有何感想？
广度优先搜索
广搜 是以某一节点为出发点，先拜访所有相邻的节点。 再依序拜访与刚才被拜访过的节点相邻但未曾被拜访过的节点，直到所有相邻的节点都已被拜访过。 因此，进行广搜 时，需要使用queue ，以便记录拜访的顺序。
广度优先搜索
1. 起始。
广度优先搜索
2. 假设从a 开始拜访，我们将a 放进queue。
QUEUE
queue front
a
queue back
接下来把a 从queue中取出，a 有三个节点可以拜访(b, c, d)。
QUEUE
queue empty
广度优先搜索
3. 假设我们选择先拜访b ，我们将b 放进queue。
QUEUE
queue front
b
queue back
广度优先搜索
4. 再来，假设我们选择拜访c ，我们将c 放进queue。
QUEUE
queue front
b
c
queue back
广度优先搜索
5. 我们选择拜访d ，我们将d 放进queue。
QUEUE
queue front
b
c
d
queue back
由于已经拜访过所有与a相邻的节点，我们从queue中取出下一个元素b， b有两个节点可以拜访(e, f)。
QUEUE
queue front
c
d
queue back
广度优先搜索
6. 假设我们选择先拜访e ，我们将e 放进queue。
QUEUE
queue front
c
d
e
queue back
广度优先搜索
7. 再来我们选择拜访f ，我们将f 放进queue。
QUEUE
queue front
c
d
e
f
queue back
由于已经拜访过所有与b相邻的节点，我们从queue中取出下一个元素c， c没有节点可以拜访。
QUEUE
queue front
d
e
f
queue back
由于已经拜访过所有与c相邻的节点，我们再从queue中取出下一个元素d， d可以拜访g。
QUEUE
queue front
e
f
queue back
广度优先搜索
8. 我们选择拜访g ，我们将g 放queue。
QUEUE
queue front
e
f
g
queue back
由于已经拜访过所有与d相邻的节点，我们从queue中取出下一个元素e， e没有节点可以拜访。
QUEUE
queue front
f
g
queue back
由于已经拜访过所有与e相邻的节点，我们从queue中取出下一个元素f， f没有节点可以拜访。
QUEUE
queue front
g
queue back
由于已经拜访过所有与f相邻的节点，我们从queue中取出下一个元素g， g没有节点可以拜访。
QUEUE
queue empty
由于g 也没有节点可以拜访，此时queue 已经全部清空，breadth-first search完成。
广度优先搜索
int bfs()
{
int i;
queue<point> qu;
memset(mark, 0, sizeof(mark));
= sx;
= sy;
= 0;
(cur);
if (sx == ex && sy == ey)
return 0;
mark[sx][sy] = 1;
while (!())
{
cur = ();
();
for (i = 0; i < 8; i++)
{
= + dir[i][0];
= + dir[i][1];
= + 1;