深度优先搜索

正文索引 [隐藏]

Intro
例题

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/

现在你总共有 n 门课需要选，记为 0 到 n-1。
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]
给定课程总量以及它们的先决条件，判断是否可能完成所有课程的学习？

现在你总共有 n 门课需要选，记为 0 到 n-1。

在选修某些课程之前需要一些先修课程。例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]

给定课程总量以及它们的先决条件，判断是否可能完成所有课程的学习？

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

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

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

<br />class Solution {
public:
    int vis[100050];
    vector<int> edge[100050];

    bool dfs(int x){
        vis[x] = 0;

        bool ret = true;
        for (auto v: edge[x]){
            if (vis[v] == 0) return false;
            if (vis[v] == -1) ret = ret && dfs(v);
        }

        vis[x] = 1;
        return ret;
    }

    bool canFinish(int n, vector<vector<int>>& prerequisites) {
        for (int i = 0; i < n; i++) vis[i] = -1, edge[i].clear();
        for (auto p: prerequisites) edge[p[0]].push_back(p[1]);

        bool ret = true;
        for (int i = 0; i < n; i++){
            if (vis[i] == -1) ret = ret && dfs(i);
        }

        return ret;
    }
};

<br />class Solution {

public:

int vis[100050];

vector<int> edge[100050];

bool dfs(int x){

vis[x] = 0;

bool ret = true;

for (auto v: edge[x]){

if (vis[v] == 0) return false;

if (vis[v] == -1) ret = ret && dfs(v);

}

vis[x] = 1;

return ret;

}

bool canFinish(int n, vector<vector<int>>& prerequisites) {

for (int i = 0; i < n; i++) vis[i] = -1, edge[i].clear();

for (auto p: prerequisites) edge[p[0]].push_back(p[1]);

bool ret = true;

for (int i = 0; i < n; i++){

if (vis[i] == -1) ret = ret && dfs(i);

}

return ret;

}

};

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

在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。
你的任务是，对于给定的N，求出有多少种合法的放置方法。

在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。

你的任务是，对于给定的N，求出有多少种合法的放置方法。

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

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

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

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

#include <cstdio>

using namespace std;

int dfs(int cur, int n, int lb, int rb, int cb){
    if (cur > n) return 1;

    int ban = lb | rb | cb, ret = 0;

    for (int i = 0; i < n; i++){
        if ((ban >> i) & 1) continue;
        ret += dfs(cur + 1, n, (lb | (1 << i)) << 1, (rb | (1 << i)) >> 1, cb | (1 << i));
    }
    return ret;
}

int main(){
    int n, ans[15];

    for (int i = 1; i <= 10; i++) ans[i] = dfs(1, i, 0, 0, 0);

    while(scanf("%d", &n) != EOF && n > 0)
        printf("%d\n", ans[n]);
    return 0;
}

#include <cstdio>

using namespace std;

int dfs(int cur, int n, int lb, int rb, int cb){

if (cur > n) return 1;

int ban = lb | rb | cb, ret = 0;

for (int i = 0; i < n; i++){

if ((ban >> i) & 1) continue;

ret += dfs(cur + 1, n, (lb | (1 << i)) << 1, (rb | (1 << i)) >> 1, cb | (1 << i));

}

return ret;

}

int main(){

int n, ans[15];

for (int i = 1; i <= 10; i++) ans[i] = dfs(1, i, 0, 0, 0);

while(scanf("%d", &n) != EOF && n > 0)

printf("%d\n", ans[n]);

return 0;

}

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

今年的世界冰球锦标赛在捷克举行。Bobek 已经抵达布拉格，他不是任何团队的粉丝，也没有时间观念。他只是单纯的想去看几场比赛。如果他有足够的钱，他会去看所有的比赛。不幸的是，他的财产十分有限，他决定把所有财产都用来买门票。
给出 Bobek 的预算和每场比赛的票价，试求：如果总票价不超过预算，他有多少种观赛方案。如果存在以其中一种方案观看某场比赛而另一种方案不观看，则认为这两种方案不同。
输入第一行，两个正整数 $N$ 和 $M$ ($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 的结果存在数组里，然后通过二分将两个数组里的状态关联起来。

#include <cstdio>
#include <algorithm>
using namespace std;

#define LL long long
const int MAXN = 45;
const int MAXM = 1<<21;
LL M, price[55], pre[MAXM], suf[MAXM];


void dfs(int l, int r, LL v, LL sum[], int &cnt){
    if (l > r) { sum[cnt++] = v; return; }
    dfs(l + 1, r, v, sum, cnt);
    dfs(l + 1, r, v + price[l], sum, cnt);
}

int main(){
    int n, a = 0, b = 0;

    scanf("%d%lld", &n, &M);
    for (int i = 1; i <= n; i++) scanf("%lld", &price[i]);

    dfs(1, n / 2, 0, pre, a);
    dfs(n / 2 + 1, n, 0, suf, b);

    sort(suf, suf + b);

    LL ans = 0;
    for (int i = 0; i < a; i++)
        ans += upper_bound(suf, suf + b, M - pre[i]) - suf;

    printf("%lld\n", ans);
    return 0;
}

#include <cstdio>

#include <algorithm>

using namespace std;

#define LL long long

const int MAXN = 45;

const int MAXM = 1<<21;

LL M, price[55], pre[MAXM], suf[MAXM];

void dfs(int l, int r, LL v, LL sum[], int &cnt){

if (l > r) { sum[cnt++] = v; return; }

dfs(l + 1, r, v, sum, cnt);

dfs(l + 1, r, v + price[l], sum, cnt);

}

int main(){

int n, a = 0, b = 0;

scanf("%d%lld", &n, &M);

for (int i = 1; i <= n; i++) scanf("%lld", &price[i]);

dfs(1, n / 2, 0, pre, a);

dfs(n / 2 + 1, n, 0, suf, b);

sort(suf, suf + b);

LL ans = 0;

for (int i = 0; i < a; i++)

ans += upper_bound(suf, suf + b, M - pre[i]) - suf;

printf("%lld\n", ans);

return 0;

}

一	二	三	四	五	六	日
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31

WNJXYKの博客

喂你脚下有坑