找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 5636|回复: 5
收起左侧

[刷题总结] DFS深度优先搜索

[复制链接]

90

主题

46

精华

1908

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1908

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

发表于 3-23-2016 02:18 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 Sophia 于 3-31-2016 05:09 PM 编辑

本文转载自: LeetCode 题解  戴方勤 (soulmachine@gmail.com)
https://github.com/soulmachine/leetcode
版权归原作者所有。

[M.M]这篇文章实在是写得太棒。忍不住转载。。。

1. 适用场景
输入数据:
如果是递归数据结构,如单链表,二叉树,集合,则百分之百可以用深搜;
如果是非递归数据结构,如一维数组,二维数组,字符串,图,则概率小一些。
状态转换图:
树或者图。
求解目标:必须要走到最深(例如对于树,必须要走到叶子节点)才能得到一个解,这种情况适合用深搜。

2. 思考的步骤
1. 是求路径条数,还是路径本身(或动作序列)?
深搜最常见的三个问题,求可行解的总数,求一个可行解,求所有可行解。
(a) 如果是路径条数,则不需要存储路径。
(b) 如果是求路径本身,则要用一个数组 path[] 存储路径。

跟宽搜不同,宽搜虽然最终求的也是一条路径,但是需要存储扩展过程中的所有路径,在没找到答案之前所有路径都不能放弃;而深搜,在搜索过程中始终只有一条路径,因此用一个数组就足够了。

2. 只要求一个解,还是要求所有解?
如果只要求一个解,那找到一个就可以返回;如果要求所有解,找到了一个后,还要继续扩展,直到遍历完。广搜一般只要求一个解,因而不需要考虑这个问题(广搜当然也可以求所有解,这时需要扩展到所有叶子节点,相当于在内存中存储整个状态转换图,非常占内存,因此广搜不适合解这类问题)。

3. 如何表示状态?
即一个状态需要存储哪些些必要的数据,才能够完整提供如何扩展到下一步状态的所有信息。跟广搜不同,深搜的惯用写法,不是把数据记录在状态 struct 里,而是添
加函数参数(有时为了节省递归堆栈,用全局变量),struct 里的字段与函数参数一一对应。

4. 如何扩展状态?
这一步跟上一步相关。状态里记录的数据不同,扩展方法就不同。对于固定不变的数据结构(一般题目直接给出,作为输入数据),如二叉树,图等,扩展方法很简单,直接往下一层走,对于隐式图,要先在第 1 步里想清楚状态所带的数据,想清楚了这点,那如何扩展就很简单了。

5. 关于判重
(a) 是否需要判重?如果状态转换图是一棵树,则不需要判重,因为在遍历过程中不可能重
复;如果状态转换图是一个 DAG,则需要判重。这一点跟 BFS 不一样,BFS 的状态转
换图总是 DAG,必须要判重。
(b) 怎样判重?跟广搜相同,见第 §9.4 节。同时,DAG 说明存在重叠子问题,此时可以用
缓存加速,见第 8 步。

6. 终止条件是什么?
终止条件是指到了不能扩展的末端节点。对于树,是叶子节点,对于图或
隐式图,是出度为 0 的节点。

7. 收敛条件是什么?
收敛条件是指找到了一个合法解的时刻。如果是正向深搜(父状态处理完了才进行递归,即父状态不依赖子状态,递归语句一定是在最后,尾递归),则是指是否达到目标状态;如果是逆向深搜(处理父状态时需要先知道子状态的结果,此时递归语句不在最后),则是指是否到达初始状态。
由于很多时候终止条件和收敛条件是是合二为一的,因此很多人不区分这两种条件。仔细区
分这两种条件,还是很有必要的。
为了判断是否到了收敛条件,要在函数接口里用一个参数记录当前的位置(或距离目标还有
多远)。如果是求一个解,直接返回这个解;如果是求所有解,要在这里收集解,即把第一步中表示路径的数组 path[] 复制到解集合里。

8. 如何加速?
(a) 剪枝。深搜一定要好好考虑怎么剪枝,成本小收益大,加几行代码,就能大大加速。这
里没有通用方法,只能具体问题具体分析,要充分观察,充分利用各种信息来剪枝,在
中间节点提前返回。
(b) 缓存。
i. 前提条件:状态转换图是一个 DAG。DAG=> 存在重叠子问题 => 子问题的解会被
重复利用,用缓存自然会有加速效果。如果依赖关系是树状的(例如树,单链表
等),没必要加缓存,因为子问题只会一层层往下,用一次就再也不会用到,加了
缓存也没什么加速效果。
ii. 具体实现:可以用数组或 HashMap。维度简单的,用数组;维度复杂的,用 HashMap,
C++ 有 map,C++ 11 以后有 unordered_map,比 map 快。

拿到一个题目,当感觉它适合用深搜解决时,在心里面把上面 8 个问题默默回答一遍,代码基本上就能写出来了。对于树,不需要回答第 5 和第 8 个问题。如果读者对上面的经验总结看不懂或感觉“不实用”,很正常,因为这些经验总结是我做了很多题目后总结出来的,从思维的发展过程看,“经验总结”要晚于感性认识,所以这时候建议读者先做做前面的题目,积累一定的感性认识后,再回过头来看这一节的总结,一定会有共鸣。
3. 代码模板




4. 深搜与回溯法的区别
深搜 (Depth-first search, DFS) 的定义见 http://en.wikipedia.org/wiki/Depth_first_search
回溯法 (backtracking) 的定义见 http://en.wikipedia.org/wiki/Backtracking

回溯法 = 深搜 + 剪枝。一般大家用深搜时,或多或少会剪枝,因此深搜与回溯法没有什么不同,可以在它们之间画上一个等号。本书同时使用深搜和回溯法两个术语,但读者可以认为二者等价。
深搜一般用递归 (recursion) 来实现,这样比较简洁。
深搜能够在候选答案生成到一半时,就进行判断,抛弃不满足要求的答案,所以深搜比暴力搜索法要快。

5. 深搜与递归的区别
深搜经常用递归 (recursion) 来实现,二者常常同时出现,导致很多人误以为他俩是一个东西。
深搜,是逻辑意义上的算法,递归,是一种物理意义上的实现,它和迭代 (iteration) 是对应的。
深搜,可以用递归来实现,也可以用栈来实现;而递归,一般总是用来实现深搜。可以说,递归一定是深搜,深搜不一定用递归。

递归有两种加速策略: 一种是剪枝 (prunning),对中间结果进行判断,提前返回;一种是缓存,缓存中间结果,防止重复计算,用空间换时间
其实,递归 + 缓存,就是 memorization。所谓 memorization(翻译为备忘录法),
就是”top-down with cache”(自顶向下 + 缓存),它是 Donald Michie 在 1968 年创造的术语,表示一种优化技术,在 top-down 形式的程序中,使用缓存来避免重复计算,从而达到加速的目的。
memorization 不一定用递归,就像深搜不一定用递归一样,可以在迭代 (iterative) 中使用
memorization 。递归也不一定用 memorization,可以用 memorization 来加速,但不是必须的。只有当递归使用了缓存,它才是 memorization 。
既然递归一定是深搜,为什么很多书籍都同时使用这两个术语呢?在递归味道更浓的地方,一般用递归这个术语,在深搜更浓的场景下,用深搜这个术语,读者心里要弄清楚他俩大部分时候是一回事。在单链表、二叉树等递归数据结构上,递归的味道更浓,这时用递归这个术语;
在图、隐式图等数据结构上,深搜的味道更浓,这时用深搜这个术语。

本帖被以下淘专辑推荐:

发表于 3-23-2016 03:09 PM | 显示全部楼层

21

主题

4

精华

481

积分

高级会员

Rank: 3Rank: 3

积分
481
发表于 3-23-2016 07:22 PM | 显示全部楼层
他的手写代码手册和Leetcode题解也很赞,后者尤其是分类,比leetcode上的分类出来早很多。两本书上边都有这个代码模板,还有BFS的。不过后者的缺点在于解释很简略,而且答案不一定是最优解,时间复杂度分析还有不少错误。。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表