下载此文档

ACM算法设计-BFS广度搜索-DFS入门深度搜索详解专题课件.ppt

文档分类：IT计算机 | 页数：约51页举报非法文档有奖

1/51

下载提示

1.该资料是网友上传的，本站提供全文预览，预览什么样，下载就什么样。
2.下载该文档所得收入归上传者、原创者。
3.下载的文档，不会出现我们的网址水印。

同意并开始全文预览

(约 1-6 秒)

1/51 下载此文档

文档列表 文档介绍

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

ACM算法设计-BFS广度搜索-DFS入门深度搜索详解专题课件来自淘豆网m.daumloan.com转载请标明出处.

ACM算法设计-BFS广度搜索-DFS入门深度搜索详解专题课件.ppt

ACM算法设计-BFS广度搜索-DFS入门深度搜索详解专题课件

ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解解读教学文案

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

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

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

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

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

ACM算法设计BFS(广度搜索)DFS入门(深度搜索)详解精要

关于深度优先搜索DFS和广度优先搜索BFS算法的实现

关于深度优先搜索DFS与广度优先搜索BFS算法实现