DFS剪枝与优化

前言

无论在深搜还是宽搜当中，我们都需要对所有的情况进行暴力枚举，要降低我们在深度优先搜索时的时间开销，剪枝优化至关重要。在具体的题目中，我们可以考虑的剪枝方法主要有以下五个方向：
1.优化搜索顺序：不同的搜索顺序会产生不同的搜索树规模，在大部分情况下，应当优先搜索分支较少的节点。
2.排除等效冗余：有些结果是数据的组合而无需考虑组内顺序，这时我们需要控制不去搜索重复状态，排除冗余。
3.可行性剪枝：在搜索的过程当中对当前的状态随时进行检查，发现当前分支已无法到达递归边界或已无法满足结果要求可直接回溯。
4.最优性剪枝：当我们发现当前分支无论数和都比最优解要差时，可提前退出。
5.记忆化搜索：我们可以记录每一个状态的搜索结果，当重复遍历时可以直接返回。

简单示例

ACwing 165
链接：https://www.acwing.com/problem/content/167/
翰翰和达达饲养了 N 只小猫，这天，小猫们要去爬山。
经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了（呜咕>_<）。
翰翰和达达只好花钱让它们坐索道下山。
索道上的缆车最大承重量为 W，而 N 只小猫的重量分别是 C1、C2……CN。
当然，每辆缆车上的小猫的重量之和不能超过 W。
每租用一辆缆车，翰翰和达达就要付 1 美元，所以他们想知道，最少需要付多少美元才能把这 N 只小猫都运送下山。
输入格式
第 1 行：包含两个用空格隔开的整数，N 和 W。
第 2..N+1 行：每行一个整数，其中第 i+1 行的整数表示第 i 只小猫的重量 Ci。
输出格式
输出一个整数，表示最少需要多少美元，也就是最少需要多少辆缆车。
数据范围
1≤N≤18,
1≤Ci≤W≤108

可通过该问题体会一下几种剪枝的方法。
在DFS问题中我们首先考虑搜索顺序再思考其他的剪枝方法，要使未来的搜索分支较少，我们应当优先枚举较大的重量，其次对每辆缆车所需重量之和进行可行性剪枝，同时我们注意到本题要求最优解，所以可以记录当前的最优结果，当搜索分支已经超过最优解时直接跳出,在考虑好剪枝方法后，我们只需打板并注意回溯即可，非常简单。

完整代码如下

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 20;
int n,m;
int w[N];
int s[N];
int ans = N;
bool cmp(int a,int b){
    return a > b;
}

void dfs(int u,int k){
    //最优性剪枝
    if(k >= ans)return ;
    if(u == n){
        ans = k;
        return ;
    }
    
    for(int i = 0;i < k;i++){
        if(s[i] + w[u] <= m){ //可行性剪枝
            s[i] += w[u];
            dfs(u + 1,k);
            s[i] -= w[u]; //恢复现场
        }
    }
    
    s[k] = w[u];
    dfs(u + 1,k + 1);
    s[k] = 0; //恢复现场
}

int main()
{
    cin>>n>>m;
    for(int i = 0;i < n;i++)cin>>w[i];
    
    //优化搜索顺序
    sort(w,w + n,cmp);
    dfs(0,0);
    cout<<ans<<endl;
    
    return 0;
}

数独问题

比较经典的DFS例题
数独是一种传统益智游戏，你需要把一个 9×9 的数独补充完整，使得数独中每行、每列、每个 3×3 的九宫格内数字 1∼9 均恰好出现一次。
请编写一个程序填写数独。
输入格式
输入包含多组测试用例。
每个测试用例占一行，包含 81 个字符，代表数独的 81 个格内数据（顺序总体由上到下，同行由左到右）。
每个字符都是一个数字（1−9）或一个 .（表示尚未填充）。
您可以假设输入中的每个谜题都只有一个解决方案。
文件结尾处为包含单词 end 的单行，表示输入结束。
输出格式
每个测试用例，输出一行数据，代表填充完全后的数独。

相应链接：
http://poj.org/problem?id=3074
https://www.acwing.com/problem/content/168/
https://leetcode.cn/problems/sudoku-solver/

这道题目中没有太多的剪枝方法，但是可以用位运算进行优化，主要考虑搜索顺序、可行性及位运算优化。对于每一行列及九宫格中，可用一个9位二进制数来记录当前行、列、九宫格的状态，某一位为1时代表该位已被填上数字，在判断某位置是否可以填数时，我们将行、列及九宫格的状态求与，即可判断可否填数。
求二进制表示中的1可用lowbit函数来求解，代表当前数二进制表示中最低位的值。

#define lowbit(x) (x & -x)

也可直接使用__builtin_popcount()函数来实现，__builtin_popcount属于GCC提供的指令，也是通过打表实现，时间复杂度O(1)。
手动打表则定义ones[],map[]数组分别表示0-2^9中各个状态有多少个1、当前数为2的多少次方。
为优化搜索顺序，我们从空格数最少的状态开始搜索。
另外注意当前代码目前会卡常数TLE，需要开O2优化。

完整代码如下

#include<iostream>
#include<cstring>
#include<algorithm>
#pragma GCC optimize(2)
using namespace std;
const int N = 9,M = 1 << N; 
int ones[M],map[M]; //map表示的是2的次方 map[logn]=i,ones表示0-2^9中的数中每个状态有多少个1
int row[N],col[N],cell[3][3]; //各行列九宫格状态
char s[100];

int lowbit(int x)  // 返回末尾的1
{
    return x & -x;
}

int get(int x,int y){
    return row[x] & col[y] & cell[x / 3][y / 3];
}

void init(){  //初始状态 行列9宫格没有填
    for(int i = 0;i < N;i++){
        row[i] = col[i] = (1 << N) - 1; //2^9 - 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 t,bool is_set){   //辅助函数 填数或删数 通过is_set进行判断
    if(is_set)s[x * N + y] = '1' + t;
    else s[x * N + y] = '.';
    
    int v = 1 << t;
    if(!is_set)v = -v;
    
    row[x] -= v;
    col[y] -= v;
    cell[x / 3][y / 3] -= v;
}

bool dfs(int cnt){
    if(!cnt)return true; //填满所有空格时结束
    
    int minv = 10;  //最多可以填10个数
    int x,y; //循环完后x y存储的就是分支数量最少的格子
    for(int i = 0;i < N;i++){
        for(int j = 0;j < N;j++){
            if(s[i * N + j] == '.'){
                int state = get(i,j);
                if(ones[state] < minv){
                    minv = ones[state];
                    x = i,y = j;
                }
            }
        }
    }
    
    int state = get(x,y);  //从当前位置开始搜索
    for(int i = state; i ;i -= lowbit(i)){
        int t = map[lowbit(i)];   //从表中取数
        draw(x,y,t,true);           
        if(dfs(cnt - 1))return true;
        draw(x,y,t,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 = 0;j < N;j++){
            ones[i] += i >> j & 1;
        }
    }
    
    while(cin >> s,s[0] != 'e'){
        init();
        
        int cnt = 0;//空格的数目  
        for(int i = 0,k = 0;i < N;i++){   //输入数独并统计空格数目
            for(int j = 0;j < N;j++,k++){
                if(s[k] != '.'){
                    int t = s[k] - '1';
                    draw(i,j,t,true);     
                }else cnt++;
            }
        }
        
        dfs(cnt);
        puts(s);
    }
    
    return 0;
}

扩展练习

sticks
乔治拿来一组等长的木棒，将它们随机地砍断，使得每一节木棍的长度都不超过 50 个长度单位。
然后他又想把这些木棍恢复到为裁截前的状态，但忘记了初始时有多少木棒以及木棒的初始长度。
请你设计一个程序，帮助乔治计算木棒的可能最小长度。
每一节木棍的长度都用大于零的整数表示。
输入格式
输入包含多组数据，每组数据包括两行。
第一行是一个不超过 64 的整数，表示砍断之后共有多少节木棍。
第二行是截断以后，所得到的各节木棍的长度。
在最后一组数据之后，是一个零。
输出格式
为每组数据，分别输出原始木棒的可能最小长度，每组数据占一行。
数据范围
数据保证每一节木棍的长度均不大于 50。
本题链接：https://vjudge.net/problem/UVA-307
首先考虑搜索顺序，为使未来分支较少，我们优先枚举长度较大的木棍。
其次，枚举木棒的长度时，长度length要被所有木棍的总长度sum整除才能符合题意。
比较细节的是等效冗余的考虑，主要有以下四个方面：
1.组内顺序不影响结果，可以不用重复搜索
2.在枚举木棍的过程中，如果当前长度的木棍加入到方案中无法满足要求，则之后的相同长度的木棍都可以跳过
3.如果木棒枚举第一根木棍时无法满足要求，则可直接跳过，一定无法满足要求
4.同3，如果木棒枚举最后一根木棍时无法满足要求，则可直接跳过
可通过反证法证明3.4
完整代码如下

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 70;
int n;
int w[N];
int sum,length;
bool st[N];

bool cmp(int a,int b){
    return a > b;
}

bool dfs(int u,int cur,int start){  //当前组，当前组长度，当前组枚举到的位置
    if(u * length == sum)return true;  //总长度达到，返回结果
    if(cur == length)return dfs(u + 1,0,0); //枚举下一组
    for(int i = start;i < n;i++){
        if(st[i] || cur + w[i] > length)continue;
        
        st[i] = true;
        if(dfs(u,cur + w[i],i + 1))return true;   //枚举下一根木棍
        st[i] = false;
        
        if(!cur || cur + w[i] == length)return false; //3.4
        
        int j = i;   //跳过相同长度
        while(j < n && w[j] == w[i])j++;
        i = j - 1;
    }
    
    return false;
}

int main()
{
    while(cin >> n,n){
        memset(st,0,sizeof st);
        sum = 0;
        
        for(int i = 0;i < n;i++){
            cin>>w[i];
            sum += w[i];
        }
        
        sort(w,w + n,cmp);  //优化搜索顺序
        
        length = 1;   //外层枚举木棒长度
        while(true){
            if(sum % length == 0 && dfs(0,0,0)){   //整除要求
                cout<<length<<endl;
                break;
            }
            length++;
        }
    }
    
    return 0;
}