文档章节

【算法研究】搜索算法-深度优先搜索

王选易
 王选易
发布于 2013/12/13 19:00
字数 1419
阅读 6.9K
收藏 94

如果您觉得本文有用,可以在微博上关注我,每周我都会在微博上发布新博客发表的通知,我的微博


###深度优先搜索

####介绍

如果您觉得这篇文章排版不舒服,请到我的微盘下载pdf:搜索算法-深度优先搜索

深度优先搜索是一种用来遍历或者搜索树(TREE)或图(GRAPH)结构的算法。搜索开始于某个根节点(从图中选取某个节点),然后在开始回溯前尽可能远地探索到这一支的终点。

对于DFS的实际应用程序来说,DFS常常因为要搜索的图的某一条搜索路径太长(甚至是无限的)而陷入性能瓶颈,所以我们经常制定DFS只能搜索到某个深度,

如果用一个图来代表深度优先搜索的过程,即如下图:

dfs

####深度优先遍历的伪码实现

相应的伪码实现在《算法导论》这本书中有讲解,书中用的方法十分巧妙,它用三种颜色来代表三种状态

  • WHITE代表未访问的结点
  • GRAY代表该节点第一次被访问
  • BLACK代表该节点的所有邻接节点都被访问,即回溯完毕的第二次访问

以下是一个深度优先遍历的递归实现:

DFS(G, s)
	for 在图G中的每一个节点v
		status[v] = WHITE
	// 进行其他初始
	DFS-VISIT(s)

DFS-VISIT(v)
	status[v] = GRAY
		for 每一个v的邻接节点
			if (status[v] == WHITE)
				DFS-VISIT(t)
	status[v] = BLACK

如果想实现深度优先遍历的非递归实现,就需要用到stack来存储未被访问的节点,以便回溯时能够找到

DFS(G, s)
	stack visted, unvisited
	unvisited.push(s)
	while (!unvisited.empty()) // 只有当unvisted不空
		current = unvisited.pop()
		for 每一个current的邻接节点v and 节点v不在visited中 //  在以上的图例中是按从右向左的方式来遍历这些邻接节点
			unvisited.push(v)
		visted.push(current)

非递归实现的图片实例,图片中显示了unvisted栈中的数据情况:

dfs_stack

####深度优先搜索的伪码实现

深度优先搜索与深度优先遍历大部分实现是相同的,只是深度优先搜索会在找到终点时就退出搜索。

以下是深度优先搜索的伪码实现:

DFS(G, s, d)
	stack visted, unvisited
	unvisited.push(s)
	while (!unvisited.empty()) // 只有当unvisted不空
		current = unvisited.pop()
		if (current == d)
			break;
		for 每一个current的邻接节点v and 节点不在visited中 //  在以上的图例中是按从右向左的方式来遍历这些邻接节点
			v.prev = current
			unvisited.push(v)
		visted.push(current)

算法中通过记录每一个节点v都通过他的属性prev记录了他的前继节点是哪一个,最终可以通过前继节点构建出需要的路径。

####深度优先搜索的优化

谈到深度优先搜索的优化,我们可以想到在介绍中我们说过:DFS常常因为要搜索的图的某一条搜索路径太长(甚至是无限的)而陷入性能瓶颈,所以我们在优化时应当针对这一点进行优化,即限制每次搜索的路径长度,以便能够在一定长度的路径之内找到较优解,当在一定长度之内不能找到合适的路径时,我们可以增加限定的搜索路径长度,来进一步进行深度优先搜索,这种方法叫做逐层加深的深度优先算法

我们根据上文中DFS的递归实现来对深度优先搜索,来对深度优先搜索做出优化。

DFS(G, s, d)
	for 在图G中的每一个节点v
		status[v] = WHITE
	// 进行其他初始
	for depth = 0
	for max = 边数/2, 边数 do
		if DFS-VISIT(s, d, depth, max)
			break;

DFS-VISIT(v, d, depth, max)
	if (depth > width)
		return false
	if (v == d)
		return true
	status[v] = GRAY
		for 每一个v的邻接节点t
			if (status[t] == WHITE)
				t.prev = v
				DFS-VISIT(t, d, depth + 1, max)
	status[v] = BLACK
		return false

####深度优先搜索的优点

深度优先搜索,与广度优先搜索相比,它不必遍历所有分支,所以它的速度较快。它不一定能找到最优解,但能找到接近解。

####深度优先搜索的应用

  • 深度优先的第一种应用:走迷宫,上一章列出的代码是寻找一条有效的路径,深度优先也可以穷举出迷宫中所有的路径。只需要在每次找到迷宫出口时,不要结束程序,而继续回溯,就可以继续寻找其他走出迷宫的办法,直到变量step为0,程序退出。你可以记录每一种走法的路径长度(step),最后得到最优解。

  • 深度优先的第二种应用:穷举。用例子说明:列出 A ~ F 这六个字母所能列出的所有组合(必须6位,不允许重复)。当然你可以用6重循环给出答案,但是随着字母数量增多,深度优先会是你的不二选择。下面继续通过一些例子说明应用吧,著名的“八皇后问题”,“背包问题”(当然也都可以用其他算法),大家可以在百度上搜索这两个东东。

© 著作权归作者所有

王选易

王选易

粉丝 98
博文 20
码字总数 20066
作品 3
南京
程序员
私信 提问
加载中

评论(3)

湖心亭看雪
湖心亭看雪

引用来自“王选易”的评论

引用来自“湖心亭看雪”的评论

大神。我正在做一个井字棋游戏,你能不能给我详细讲解一下极大极小算法啊?

抱歉,还没看过这个算法,过一段时间看看,能不能写一篇博客

坐等大神你来给我讲解一下
王选易
王选易 博主

引用来自“湖心亭看雪”的评论

大神。我正在做一个井字棋游戏,你能不能给我详细讲解一下极大极小算法啊?

抱歉,还没看过这个算法,过一段时间看看,能不能写一篇博客
湖心亭看雪
湖心亭看雪
大神。我正在做一个井字棋游戏,你能不能给我详细讲解一下极大极小算法啊?
基本算法——深度优先搜索(DFS)和广度优先搜索(BFS)

深度优先搜索和广度优先搜索,都是图形搜索算法,它两相似,又却不同,在应用上也被用到不同的地方。这里拿一起讨论,方便比较。 一、深度优先搜索 深度优先搜索属于图算法的一种,是一个针对...

安然若知
2018/07/13
0
0
【算法】前端遇到的广度/深度优先搜索

前言 在面试或者技术社区冲浪的时候,一不小心就会看到深度优先搜索、广度优先搜索这两个概念,这一次在项目中一个需求用到了相关的知识,故此在这里通过理论+实际来总结一下。 1. 示例 下面...

眼已望穿
2019/07/19
0
0
图的搜索

前言 图的搜索指的是系统化地跟随图中的边来访问图中每一个结点,并不是随意地访问图中的结点。图的搜索算法可以用来发现图的结构,许多图的算法都要求先搜索全图,可以说,图的搜索是整个图...

某昆
2017/09/16
0
0
【译】Swift算法俱乐部-深度优先搜索

本文是对 Swift Algorithm Club 翻译的一篇文章。 Swift Algorithm Club是 raywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目,目前在GitHub上有18000+⭐️,我初略统计了一下...

Andy_Ron
2019/07/26
0
0
无向图----深度优先搜索

上一篇:无向图的实现 下一篇:深度优先遍历 根据描述,很容易实现图的深度优先搜索: 深度优先遍历标记与起点连通的所有顶点所需的时间和顶点的度数之和成正比。 使用深度优先搜索查找图中路...

Superheros
2017/12/19
4
0

没有更多内容

加载失败,请刷新页面

加载更多

MBTI助你成功,让你更了解你自己

MBTI助你成功,让你更了解你自己 生活总是一个七日接着又一个七日,相信看过第七日的小伙伴,很熟悉这段开场白,人生是一个测试接着又一个测试,上学的时候测试,是为了证明你的智力,可谓从...

蛤蟆丸子
今天
55
0
Android实现App版本自动更新

现在很多的App中都会有一个检查版本的功能。例如斗鱼TV App的设置界面下: 当我们点击检查更新的时候,就会向服务器发起版本检测的请求。一般的处理方式是:服务器返回的App版本与当前手机安...

shzwork
昨天
63
0
npm 发布webpack插件 webpack-html-cdn-plugin

初始化一个项目 npm init 切换到npm源 淘宝 npm config set registry https://registry.npm.taobao.org npm npm config set registry http://registry.npmjs.org 登录 npm login 登录状态......

阿豪boy
昨天
87
0
java基础(16)递归

一.说明 递归:方法内调用自己 public static void run1(){ //递归 run1(); } 二.入门: 三.执行流程: 四.无限循环:经常用 无限递归不要轻易使用,无限递归的终点是:栈内存溢出错误 五.递...

煌sir
昨天
63
0
REST接口设计规范总结

URI格式规范 URI中尽量使用连字符”-“代替下划线”_”的使用 URI中统一使用小写字母 URI中不要包含文件(脚本)的扩展名 URI命名规范 文档(Document)类型的资源用名词(短语)单数命名 集合(Co...

Treize
昨天
69
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部