深度优先搜索

正文索引 [隐藏]

Intro

今天,我们一起来学习一下深度优先搜索,DFS,Depth First Search。作为搜索家族中最有深度的算法,它,秉承 “犹豫就会败北” 的精神,在问题的状态空间中义无反顾、一马当先、一往直前、一路走到黑,直到一头撞上南墙,也就是在当前这个状态下不能继续转移了,才返回上一个状态,换条路继续开冲。

那么,其实 DFS 的本质就是枚举,通过枚举状态空间中的所有所有状态,从而找到一个或者若干个可行解。

这么说实在抽象,让我们来看看大家都喜欢的走迷宫问题(Maze),这里有一个迷宫,起点在 S,重点在 E。DFS 算法就像是一个记性很好的傻子,虽然盲目尝试但是可以记住自己尝试过的所有路径,绝不走重复路。它从起点 S,一路向前,直到走到一个死胡同,然后回退一步,再尝试其他路径,如此循环,直到枚举完所有的状态,答案也就自然得出了。

迷宫问题

DFS 中的状态空间将形成一颗树,一开始在起点,迈出一步或回退一步。其实就对应在这颗状态空间树上遍历,这么莽啊莽啊。尝试完了所有的可能状态,诶,那我们就找到哪些是可行解了。

状态空间树

因为需要枚举所有的状态,所以DFS的时间复杂度通常与状态空间的大小正相关,一般来说是 O(n!) 或者 O(k^n) 的,随着数据量增加,运行时间也将大大增加。但是 DFS 也有它的优点,运行所需的空间并不多,因为我们只需要存储当前状态的密切相关信息就足够了,换句话说,我们只需要能准确定位当前在状态空间树上的哪里即可。

什么样的问题可以用 DFS 解决呢,那些需要你遍历全部或者大部分情况,直到找到合法情况或者所有答案的问题。比如说在图的遍历找到可行路径、全排列方案、组合方案……或者问题过于复杂只能通过枚举所有情况求解。

面对一个深度优先搜索问题,最重要的问题是确定状态空间,也就是我们要搜什么,怎么搜,如何才可以搜得不重不漏。比如说走迷宫和图的遍历,那么状态就是当前在哪一个点,只要按照某种顺序做尝试,比如还得及网格图中的上右下左的顺序吗?那么就可以保证不重不漏地搜遍整个状态空间。而对于排列与组合问题,我们往往需要记录当前已经取走哪些元素,考虑下一步按照什么样的顺序继续取用哪些元素。

最后一个问题,如何让深度优先搜索更快一些?那么,我们可以根据实际情况,在状态空间树中剪去一些根本没有可能到达答案的分支,从而减少需要搜索空间大小达到加速的效果。

例题

LeetCode 207. 课程表 https://leetcode-cn.com/problems/course-schedule/

这道题目的重点一来是如何遍历一个图,二来在 DFS 遍历有向图的基础上判断图中是否存在环。

我们使用一个 visited 数组标记一个节点是否已经访问过了,如果访问过了就不在访问,这样就可以不重不漏的遍历完一张图中的所有节点。

判断环的思路:如果我们从环上的一个节点开始 DFS,那么那么本次遍历最终一定会再次访问自己,否则的话本次 DFS 中访问到的节点都可以排除了。
那么,我们给 visited 数组三种状态:-1 未访问,0 本轮 DFS 中正在访问,1 已经访问过且排除环上可能。在本轮 DFS 的时候将未访问过的节点置 0,离开的时候将 visited 置 1 表示排除可能。DFS 的过程中遇到 visited 为 0 的节点就说明找到了一个环。

HDU 2553 N皇后http://acm.hdu.edu.cn/showproblem.php?pid=2553

我很喜欢这个题目,因为它可以用到位运算来表示状态,代码十分优美。

这道题目,首先确定搜什么。因为每一行仅且必须放一个皇后,所以我们可以按照顺序一行一行放置皇后,那么就搜每一行得皇后放在哪个位置。

接下来是状态表示,我们判断一个位置是否可以防止皇后,要考虑它的上方,左上 45°,右上 45° 是否放置了皇后,这些就是我们需要在深搜过程中维护的当前状态。

至此一个 DFS 的程序已经可以写出来了,不过我们可以通过位运算让它更加优美。因为数据量很小 n \leq 10,所以我们可以把每一列有没有放置皇后压缩进一个 int 中存储。同理左上 45°,右上 45° 信息也是可以压缩进 int 中表示的,表示经过左上 45° / 右上 45° 的棋子影响后,当前行哪些位置不可以防止皇后,从这一行到下一行仅仅是一个左移 / 右移就可以变化的。

洛谷 P4799 世界冰球锦标赛 https://www.luogu.com.cn/problem/P4799

今年的世界冰球锦标赛在捷克举行。Bobek 已经抵达布拉格,他不是任何团队的粉丝,也没有时间观念。他只是单纯的想去看几场比赛。如果他有足够的钱,他会去看所有的比赛。不幸的是,他的财产十分有限,他决定把所有财产都用来买门票。
给出 Bobek 的预算和每场比赛的票价,试求:如果总票价不超过预算,他有多少种观赛方案。如果存在以其中一种方案观看某场比赛而另一种方案不观看,则认为这两种方案不同。
输入第一行,两个正整数 NM (1 \leq N \leq 40,1 \leq M \leq 10^{18}),表示比赛的个数和 Bobek 那家徒四壁的财产。
输入第二行,N 个以空格分隔的正整数,均不超过 10^{16},代表每场比赛门票的价格。
输出一行,表示方案的个数。由于 N 十分大,注意:答案 \le 2^{40}

这道题目的 M 太大了,没有什么好的做法,只能通过 DFS 进行枚举,求得最终合法的方案数。
但是这里的 N 也有点大,达到了 40,直接枚举的话有 2^{40} 中情况,一定会超时,这时候可以考虑一个 DFS 的技巧叫做 Meet in the Middle,也就是我们从起点开始搜索 20 个,从终点往前搜索 20 个,然后在中间合并搜索的结果,这样搜索空间的大小就是 2^{20} + 2^{20},就可以接受了。合并两侧搜索结果的时候,我们通常将两个 DFS 的结果存在数组里,然后通过二分将两个数组里的状态关联起来。