《算法竞赛进阶指南》0x22 深度优先搜索

一只野生彩色铅笔

发布于 2022-10-31 11:05:42

50800

代码可运行

文章被收录于专栏：彩铅的随笔博客彩铅的随笔博客

运行总次数：0

代码可运行

深度优先搜索基本概念

深度优先搜索（DFS，Depth First Search），顾名思义就是按照深度优先的顺序对 “问题状态空间” 进行搜索的算法。在 0x00 章中，我们多次把 一个问题的求解 看做对 问题状态空间的遍历与映射。从本章节开始，我们可以进一步把 “问题空间” 类比为一张 “图”，其中的状态类比为结点，状态之间的联系与可达性 就用 图中的边 来表示，那么使用 深度优先遍历搜索算法求解问题，就相当于在 一张图上进行深度优先遍历。

读者可能发现，深度优先搜索 与 “递归” 和 “栈” 密切相关。我们倾向于认为 “递归” 是与 “递推” 相对的一种单纯的遍历方法，除了搜索之外，还有许多算法都可以用递归实现。而 “深搜” 是一类包括 遍历形式、状态记录与检索、剪枝优化 等算法整体设计的统称。

在研究 深度优先搜索算法 之前，我们先来定义该过程产生的 “搜索树” 结构。在对图进行深度优先遍历处于点

时，对于某些边

(x,y)

，

是一个尚未访问过的结点，程序从

成功进入了更深层的对

的递归；对于另外的一些边

(x,y)

，

已经被访问过，从而程序继续考虑其他分支。我们称所有点（问题空间中的状态）与成功发生递归的边（访问两个状态之间的移动）构成的树为一棵 “搜索树”。整个深搜算法就是基于该搜索树完成的 —— 为了避免重复访问，我们对状态进行记录和检索；为了使程序更加高效，我们提前剪除搜索树上不可能是答案的子树和分支，不去进行遍历。

我们在0x03节中使用递归实现的指数型、排列型和组合型枚举，其实就是深搜的三种最简单的形式。与之相关的 子集和问题 、 全排列问题 、 N皇后问题 等都是可以用深搜求解的经典 NPC 问题。本节中，我们先通过几道更加综合性的例题直观地感受一下深度优先搜索算法。下节将进一步系统地讨论各类剪枝技巧。

习题

小猫爬山

题目描述

翰翰和达达饲养了

只小猫，这天，小猫们要去爬山。

经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了（呜咕>_<）。

翰翰和达达只好花钱让它们坐索道下山。

索道上的缆车最大承重量为

，而

只小猫的重量分别是

C_1、C_2、……、C_N

。

当然，每辆缆车上的小猫的重量之和不能超过

。

每租用一辆缆车，翰翰和达达就要付

美元，所以他们想知道，最少需要付多少美元才能把这

只小猫都运送下山？

输入格式

第

行：包含两个用空格隔开的整数，

和

。

第

2..N+1

行：每行一个整数，其中第

i+1

行的整数表示第

只小猫的重量

C_i

。

输出格式

输出一个整数，表示最少需要多少美元，也就是最少需要多少辆缆车。

数据范围

1≤N≤18,\ 1≤C_i≤W≤10^8

输入样例：

输出样例：

解析

用深度优先搜索来求解本题，在搜索过程中依次把每一只小猫分配到一辆已经租好的缆车上，或者新租一辆缆车

因此，在搜索的过程中，我们关心的状态有：

已经运送的小猫有多少只
已经租好的缆车有多少辆
每辆缆车上搭载的小猫重量之和

用三个变量

now, cnt, cab[\ ]

分别对应上述三个状态，来标识问题状态空间所类比的 “图” 中的一个结点

在这个 “结点” 上，我们至多有

cnt + 1

个可能的分支

尝试把第

now

只小猫，放到第

i\ (1 \le i \le cnt)

个缆车上。如果第

个缆车装得下，就在

cab[i]

中累加

C_{now}

，然后递归

dfs(now + 1, cnt)

尝试新租一辆缆车来放置小猫，也就是令

cab[cnt + 1] = C_{now}

，然后递归

dfs(now + 1, cnt + 1)

当

now = N + 1

时，搜索倒了递归边界，此时就可以用

cnt

更新答案了

这里再引入下一章节会讲解的剪枝技巧之二：

优化搜索顺序：将小猫重量从小到大逆序排序，先搜索重量较大的小猫，这样初始的搜索分支就会减少，有利于其他剪枝
最优性剪枝：设定全局最小值，当搜索的任何时刻发现

cnt

已经大于等于搜到的答案，则当前分支直接回溯

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 20;

int n, m;
int c[N], cab[N], res = N;

void dfs(int now, int cnt)
{
    if (cnt >= res) return;
    if (now == n + 1)
    {
        res = cnt;
        return;
    }
    for (int i = 1; i <= cnt; i ++ )
    {
        if (cab[i] + c[now] <= m)
        {
            cab[i] += c[now];
            dfs(now + 1, cnt);
            cab[i] -= c[now];
        }
    }
    cab[cnt + 1] = c[now];
    dfs(now + 1, cnt + 1);
    cab[cnt + 1] = 0;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &c[i]);
    sort(c + 1, c + n + 1, greater<int>());
    dfs(1, 0);
    printf("%d\n", res);
    return 0;
}

数独

题目描述

数独是一种传统益智游戏，你需要把一个

9×9

的数独补充完整，使得图中每行、每列、每个

3×3

的九宫格内数字

1∼9

均恰好出现一次。

请编写一个程序填写数独。

输入格式

输入包含多组测试用例。

每个测试用例占一行，包含

个字符，代表数独的

个格内数据（顺序总体由上到下，同行由左到右）。

每个字符都是一个数字（1 − 9）或一个 .（表示尚未填充）。

您可以假设输入中的每个谜题都只有一个解决方案。

文件结尾处为包含单词 end 的单行，表示输入结束。

输出格式

每个测试用例，输出一行数据，代表填充完全后的数独。

输入样例：

4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......
......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.
end

输出样例：

417369825632158947958724316825437169791586432346912758289643571573291684164875293
416837529982465371735129468571298643293746185864351297647913852359682714128574936

解析

精确覆盖问题建议直接上 DLX

数独问题的搜索框架非常简单，我们关心的 “状态” 就是数独的每个位置上填了什么数。在每个状态下，我们找出一个还没有填的位置，检查有哪些合法的数字可以填。这些合法的数字就构成该状态向下继续递归的 “分支” 。

搜索边界分为两种：

如果所有位置都被填满，就找到了一个解
如果发现某个位置没有能填的合法数字，说明当前分支搜索失败，应该回溯去尝试其他分支

【注】在任意状态下，我们只需要找出

个位置，考虑该位置上填什么树，不需要枚举枚举所有的位置和可填的数向下递归（因为其他位置在更深层次会被搜索到）。新手常犯的错误就是重叠、混淆 “层次” 和 “分支” ，造成重复遍历若干棵覆盖同一状态空间的搜索树，致使搜索的复杂度大规模增长

然而，数独问题的 “搜索树” 规模仍然很大，直接盲目搜索的效率实在不能接受。应该采取的启发式策略是：在每个状态下，从所有未填的位置里选择 “能填的合法数字” 最少的位置，考虑该位置上填什么数，作为搜索的分支，而不是任意找出 1 个位置

在搜索程序中，影响时间效率的因素除了搜索树的规模（影响算法的时间复杂度），还有在每个状态上记录、检索、更新的开销（影响程序运行的 “常数” 时间）。我们可以使用位运算来代替数组执行 “对数独各个位置所填数字的记录” 以及 “可填性的检查与统计”。这就是我们所说的程序 “常数优化”:

对于每行、每列、每个九宫格，分贝用一个 9 位二进制数（全局整数变量）保存哪些数字可以填
对于每个位置，把它所在行、列、九宫格的 3 个二进制数做位与(&)运算，就可以得到该位置能填哪些数，用 lowbit 运算就可以把填的数字取出
当一个位置填上某个数后，把该位置所在的行、列、九宫格记录的二进制数的对应位改为 0，即可更新当前状态；回溯时改回 1 即可还原现场

上述算法已经能够快速求解

9\times 9

的数独问题，更大的就需要用到剪枝优化算法了

#include <iostream>
#include <cstring>

#define lowbit(x) x&-x
using namespace std;

const int N = 9;

int cnt[1 << N], map[1 << N];
int row[N], col[N], cell[N / 3][N / 3];
char str[110];

void init()
{
    for (int i = 0; i < N; i ++ ) row[i] = col[i] = (1 << N) - 1;
    for (int i = 0; i < 3; i ++ )
        for (int j = 0; j < 3; j ++ )
            cell[i][j] = (1 << N) - 1;
}
void draw(int x, int y, int k, bool is_set)
{
    if (is_set) str[x * N + y] = k + '1';
    else str[x * N + y] = '.';
    int v = 1 << k;
    if (!is_set) v = -v;
    row[x] -= v;
    col[y] -= v;
    cell[x / 3][y / 3] -= v;
}
int get(int x, int y)
{
    return row[x] & col[y] & cell[x / 3][y / 3];
}
bool dfs(int u)
{
    if (!u) return true;

    int x, y, z = 10;
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            if (str[i * N + j] == '.' && z > cnt[get(i, j)])
                z = cnt[get(i, j)], x = i, y = j;
    for (int i = get(x, y); i; i -= lowbit(i))
    {
        int num = map[lowbit(i)];
        draw(x, y, num, true);
        if (dfs(u - 1)) return true;
        draw(x, y, num, false);
    }
    return false;
}
int main()
{
    for (int i = 0; i < N; i ++ ) map[1 << i] = i;
    for (int i = 0; i < 1 << N; i ++ )
        for (int j = i; j; j -= lowbit(j))
            cnt[i] ++ ;
    while (cin >> str, strcmp(str, "end"))
    {
        init();
        int s = 0;
        for (int i = 0; i < N; i ++ )
            for (int j = 0; j < N; j ++ )
                if (str[i * N + j] != '.') draw(i, j, str[i * N + j] - '1', true);
                else s ++ ;
        dfs(s);
        cout << str << endl;
    }
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-02-11，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度