DFS优化之剪枝

zhczcg314 · 2023-03-19 01:05:10 · 个人记录

DFS优化之剪枝

前言

在基础的算法中，我们学过简单的DFS，BFS等搜索算法。

除此之外，动态规划，递归，递推都是遍历解空间的方法，但是他们的时间复杂度各不相同。

为追求效率，DFS的各类优化方法相继诞生，剪枝是其中尤为重要的一种。

引入

什么是搜索树？搜索树是在搜索过程中所遍历节点形成的一棵树。显然，搜索的每一步决策都可以决定这棵搜索树的形状。DFS的优化正是在这个过程中产生的。例如：为了不再访问已经访问过的状态，我们有记忆化搜索；为了更快的找到搜索目标，我们可以改变搜索的顺序。

那么对于每条路径，即搜索树上的每条枝干，并不是都可以得到我们想要的搜索目标。那么我们要是可以预判这条路到哪里去，哎～，那多好啊。所以我们可以通过一定手段，提前检查，防止走进死胡同，即可行性剪枝。 在已知不可以到达目标时立即回溯，遍历下一决策。

由此，我们引出剪枝（Prune）优化方法。

数独

数独（sudoku），人尽皆知的益智类小游戏，但是你真的会玩吗？可能你的水平很高，但在极端情况下，你需要许多天的时间才可以找到一个数独的正解。

所以考虑下面的问题：

数独是根据 9×9 盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫内的数字均含 1−9 ，不重复。每一道合格的数独谜题都有且仅有唯一答案，推理方法也以此为基础，任何无解或多解的题目都是不合格的。

输入：给定未填的数独

输出：填好的数独

这道题乍一眼看就是典型的DFS题目，在每一个格子遍历所有决策，直到找到正解，break。

朴素 + 简单剪枝代码：

#include <iostream>
#include <cstring>
using namespace std;
bool row[9][10], col[9][10], block[3][3][10];
int sudoku[9][10];
void show(){
    for(int i = 0; i < 9; i ++){
        for(int j = 0; j < 9; j ++){
            cout << sudoku[i][j] << " ";
        }
        cout << endl;
    }
}
bool stepping(int x, int y);
bool dfs();
bool dfs(int x, int y){
    if(x > 8 || y > 8){
        return true;
    }
    if(sudoku[x][y]) return stepping(x, y);
    else
        for(int i = 1; i <= 9; i ++){
            if(!row[x][i] || !col[y][i] || !block[x / 3][y / 3][i]) continue;
            sudoku[x][y] = i;
            row[x][i] = false;
            col[y][i] = false;
            block[x / 3][y / 3][i] = false;
            if(stepping(x, y)) return true; //剪枝
            sudoku[x][y] = 0;
            row[x][i] = true;
            col[y][i] = true;
            block[x / 3][y / 3][i] = true;
        }
    return false;
}
bool stepping(int x, int y){//代替dfs的调用
    if(y == 8){
        return dfs(x + 1, 0);
    }
    else return dfs(x, y + 1);
}
int main(){
    memset(col, 1, sizeof(col));
    memset(row, 1, sizeof(row));
    memset(block, 1, sizeof(block));
    for(int i = 0; i <= 8; i ++){
        for(int j = 0; j <= 8; j ++){
            cin >> sudoku[i][j];
            row[i][sudoku[i][j]] = false;
            col[j][sudoku[i][j]] = false;
            block[i / 3][j / 3][sudoku[i][j]] = false;
        }
    }
    if(dfs(0, 0)) show();
    else cout << "No Solution" << endl;
    return 0;
}

因为可能当前决策选择后导致后面找不到正解，所以在每次DFS后需要恢复现场。

考虑优化

首先在搜索的问题中，最先应该考虑可不可以优化搜索顺序，在数独问题中，可以结合生活实际：在玩数独的时候，你最开始怎么填？选择数最少的格子开始。回归到搜索树上，如果我们从选择数少的格子开始，意味着我们的树宽度变窄，时间复杂度可以降低。

进一步考虑，我们真正需要遍历1～9这所有的数字吗？不需要。原因是因为我们的行，列，九宫格内都不可以出现相同的数字，这就有很大的限制，所以我们只需要枚举那些符合行，列，九宫格的状态就可以。此谓可行性剪枝。

优化搜索顺序
可行性剪枝

再次观察代码，发现在数组定义时有许多二维，三维布尔数组，对于小型数据范围的题目，状态压缩是比较常见且高级的优化方法。具体改动如下；

int row[9], col[9], block[3][3];
int sudoku[9][10], ones[1 << 9];

因为状态压缩的优化，所以我们需要记录每种状态下可以摆放数字数量，用ones数组表示。状态压缩后，我们发现不需要在每一格子遍历1～9所有的决策，而是通过当前的状态来确定哪些数字可以填充。如果用正常的循环遍历二进制数的每一个位数，则时间复杂度会变高，那么有更好的优化方法吗？

有，我们可以用lowbit运算解决这个问题。

lowbit

lowbit运算顾名思义，是找到二进制数最低位的1，例如 lowbit（1010）= 2 。时间复杂度为O(1)。

由于状态压缩在各类题目中的应用十分广泛，所以掌握这个运算尤为重要。

首先让我们尝试推导lowbit公式：

以 n=10100为例，我们首先把n按位取反，有：~n = 01011，而后＋1，有~n + 1=01100。不难发现，取反加一后得到的数值 lowbit之前的位与n刚好相反，因此只需做与运算即可。而在补码表示下，~n + 1 = -n*，所以有 : lowbit(n) = n & (-n)。

但做完lowbit运算后得到的是1，2，4，8，16这一类的数值，转化为位数还需要做对数运算，十分的复杂，我们在这个地方可以做与哈希表pow数组相同的操作，构建哈希表。

这里给出一个“没人告诉你可能永远不知道〞的结论：对于所有的 k=0,1,2,…,35，2 ^ k mod 37 互不相等，且恰好取遍1 ~ 36。于是，对于大多数场景，我们只需取长度为37的Hash数组即可：

 Hash[(1 << i) % 37] = i + 1;

数独的优化版本

综合以上优化，我们做了以下调整：

优化搜索顺序
可行性剪枝
状态压缩
lowbit运算

所以优化后的代码如下：

#include <iostream>
#include <cstring>
using namespace std;
// 在 2 ^ k mod 37 中，结果分别取 1 ～ 36 的值
int Hash[37];
// 状态压缩
int row[9], col[9], block[3][3];
// ones 数组记录状态下1的个数
int sudoku[9][10], ones[1 << 9];
int cnt = 0;
void show(){
    for(int i = 0; i < 9; i ++){
        for(int j = 0; j < 9; j ++){
            cout << sudoku[i][j] << " ";
        }
        cout << endl;
    }
}
void stepping(int x, int y, int num);
// rest表示总共数独中还没有填充数字的格子个数
bool dfs(int res);
bool dfs(int res){
    if(res == 0) return true;
    int x = 0, y = 0, min_state = -1, _min = 1000;
    for(int i = 0; i < 9; i ++){
        for(int j = 0; j < 9; j ++){
            if(sudoku[i][j]) continue;
            int now_state = row[i] & col[j] & block[i / 3][j / 3];
            if(ones[now_state] < _min){
                _min = ones[now_state];
                min_state = now_state;
                x = i;
                y = j;
            }
        }
    }
    //遍历这个位置所有决策
    while(min_state){
        int num = Hash[((min_state) & -min_state) % 37];
        stepping(x, y, num);
        sudoku[x][y] = num;
        if(dfs(res - 1)) return true;
        stepping(x, y, num);
        sudoku[x][y] = 0;
        min_state -= min_state & -min_state;
    }
    return false;
}
void stepping(int x, int y, int num){
    row[x] ^= 1 << (num - 1);
    col[y] ^= 1 << (num - 1);
    block[x / 3][y / 3] ^= 1 << (num - 1);
}
int main(){
    fill(row, row + 9, (1 << 9) - 1);
    fill(col, col + 9, (1 << 9) - 1);
    fill(block[0], block[0] + 9, (1 << 9) - 1);
    for(int i = 0; i < (1 << 9); i ++){
        int j = i;
        while(j){
            ones[i] ++;
            j -= j & -j;
        }
    }
    for(int i = 0; i <= 8; i ++){
        Hash[(1 << i) % 37] = i + 1;
        for(int j = 0; j <= 8; j ++){
            cin >> sudoku[i][j];
            if(sudoku[i][j]){
                stepping(i, j, sudoku[i][j]);
            }
            else{
                cnt ++;
            }
        }
    }
    if(dfs(cnt)) show();
    else cout << "No Solution" << endl;
    return 0;
}

由于使用了二进制优化，所以在DFS传参中也要做一些改动，参数只需要传入res，表示还没有填充的格子个数。

排除等效冗余剪枝

观察如下问题：

乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过 50。

现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。

给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。

再次回归到搜索树上，我们期望树的上层分的数量越小越好，这样树的宽度会变小，那我们可以对所有木棒进行从大到小的排列，在选择中先选择长的木棒，这样一来上层的决策数量就会变小。

我们再次考虑剪枝策略：

若一个长度的小段放进后，不可以得到解，那么则剪枝，并且与其长度一致的小段全部剪枝。
两个不同长度的小段先放与后放油没有区别？没有，可以交换位置，所以只需要按照从长到短的顺序遍历各个小段，则没有重复。
如果进入木棍的第一个小段就失败，说明什么？说明这一支不用走了，因为无论如何在当前情况下这个小段只要放进木棍就会失败，无论在什么位置。于是直接返回。
可否将失败的小段换成其余若干个长度比他小的小段？不可以，从贪心的角度思考，剩余的小段越多，剩余的小段才有更多的拼接方法，进而才更有可能拼成木棒。

在如上四种条件的限制下，许多重复多余的搜索部分被去除，这个就叫做排除等效冗余剪枝。

我们给出优化完成的代码：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n, a[66], len, sum = 0, _max = -1;
bool visited[66];
bool dfs(int cnt, int now_len, int idx, int fail_len){
    if(cnt == 0) return true;
    for(int i = idx; i <= n; i ++){
        if(visited[i] || a[i] == fail_len) continue;
        if(now_len + a[i] <= len){
            visited[i] = true;
            if(now_len + a[i] < len){
                if(dfs(cnt, now_len + a[i], i + 1, fail_len))
                    return true;
            }
            else if(now_len + a[i] == len){
                if(dfs(cnt - 1, 0, 1, -1)) return true;
            }
            visited[i] = false;
            fail_len = a[i];
        }
        if(now_len == 0 || now_len + a[i] == len) return false;
    }
    return false;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        sum += a[i];
        _max = max(_max, a[i]);
    }
    sort(a + 1, a + n + 1, greater<int>());
    for(len = _max; len <= sum; len ++){
        if(sum % len) continue;
        memset(visited, 0, sizeof(visited));
        if(dfs(sum / len, 0, 1, -1)) break;
    }
    cout << len << endl;
    return 0;
}

总结

DFS优化的方法有很多，剪枝是非常基础的一种，其重点在于找到多余重复的搜索部分，进而进行剪枝，进过大量数据测试可知，剪枝的效率远高于不优化的朴素DFS算法。

一些好题

[走迷宫 - 洛谷]

[[NOIP2000 提高组] 单词接龙 - 洛谷]

[[NOIP2009 提高组] 靶形数独 - 洛谷]