搜索——剪枝与TLE的拉扯

· · 个人记录

前言

搜索人，搜索魂，搜索就是人上人。

正文

众所周知，OI中最常用的搜索有两种——深度优先搜索（DFS），广度优先搜索（BFS），百度优先搜索（BDFS） 深搜简单粗暴，广搜温文尔雅。但丧心病狂的出题人总会想尽一切办法卡死搜索，于是，一种用来对抗出题人优化时间的方法诞生了——剪枝。

剪枝主要有四种办法：

1.优化搜索顺序

在不同的问题中，搜索树的各个层次、各个分支之间的顺序不是固定的，不同的搜索顺序会产生不同的搜索树形态，其规模大小也相差甚远。

2.排除等效冗余

在搜索过程中，若能判断从搜索树当前节点上沿某几条不同分支到达的子树是相同的，那么只需对其中一条分支执行搜索。

3.可行性剪枝

可行性剪枝也叫上下界剪枝，其是指在搜索过程中，及时对当前状态进行检查，若发现分支已无法到达递归边界，就执行回溯。

4.最优性剪枝

在最优化问题的搜索过程中，若当前花费的代价已超过当前搜索到的最优解，那么无论采取多么优秀的策略到达递归边界，都不可能更新答案，此时可以停止对当前分支的搜索进行回溯。

这篇博客主要介绍第4种剪枝办法，并使用深搜。

\tt{Question\, 1.}

给你一个 n\times n 的矩阵，每行每列只能取一个数，求和的最小值。

未剪枝前的裸深搜：

#include<bits/stdc++.h>
using namespace std;

int L[30][30],n,maxx[30],vis[30];
int ans=2147483647;

void dfs(int line, int now){
    if(line==n+1){
        ans=min(now,ans);
    }
    for(int i = 1; i<=n; i++){
        if(!vis[i]){
            vis[i]=1;
            dfs(line+1,now+L[line][i]);
            vis[i]=0;
        }
    }
    return;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    cin>>n;
    for(int i = 1; i<=n; i++)
        for(int j = 1; j<=n; j++){
            cin>>L[i][j];
    dfs(1,0);
    cout<<ans;
    return 0;
}

看上去就写满了一堆TLE吧，确实，在如今愈发严峻的数据下，很少有无剪枝的暴力搜索可以AC的题，怎么优化呢？

我们将重点放在 now 变量上，由于我们要让它尽量比 ans 小，如果它已经大于 ans，还有执行的必要吗？

所以，我们只需要在深搜函数里加上这样一句话：

if(now>ans)return;
\tt{Question\,2.}

如上题，只是要求取最大值。题目来源

很简单的一道状压DP对吧，但如果你不会呢？

毫不犹豫，直接暴力深搜。

#include<bits/stdc++.h>
using namespace std;
int L[30][30],n,vis[30];
int ans=-2147483647;

void dfs(int line, int now){
    if(line==n+1){
        ans=max(now,ans);
    }
    for(int i = 1; i<=n; i++){
        if(!vis[i]){
            vis[i]=1;
            dfs(line+1,now+L[line][i]);
            vis[i]=0;
        }
    }
    return;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    cin>>n;
    for(int i = 1; i<=n; i++){
        for(int j = 1; j<=n; j++){
            cin>>L[i][j];
        }
    }
    dfs(1,0);
    cout<<ans;
    return 0;
}

结果

你也许会觉得 25 分已经足够，但是如果这是 CSP-J 第二题呢？

这道题不可能再直接加一个if就可以完成足够好的剪枝，于是我们思考下列策略:

设 maxx[i] 为前 i 行的最大值之和（不考虑冲突），那么 l~r 的最大值之和（不考虑冲突）就为 maxx[r]-maxx[l-1]，这里运用了前缀和的思想。

那么，如果 now + maxx[n]-maxx[line-1] \le ans，也就是说不考虑冲突的问题下这个分支也不可能大于 ans，那么果断 return 0;

满分代码：

#include<bits/stdc++.h>
using namespace std;
int L[30][30],n,maxx[30],vis[30];
int ans=-2147483647;

void dfs(int line, int now){
    if(line==n+1){
        ans=max(now,ans);
    }
    if(now+maxx[n]-maxx[line-1]<=ans) return;
    for(int i = 1; i<=n; i++){
        if(!vis[i]){
            vis[i]=1;
            dfs(line+1,now+L[line][i]);
            vis[i]=0;
        }
    }
    return;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    cin>>n;
    for(int i = 1; i<=n; i++){
        int maxn=-2147483647;//当前行的最大值
        for(int j = 1; j<=n; j++){
            cin>>L[i][j];
            maxn=max(maxn,L[i][j]);
        }
        maxx[i]=maxn+maxx[i-1];
    }
    dfs(1,0);
    cout<<ans;
    return 0;
}

尾声

实际上还有一种比较好用的迭代加深搜索，有深搜的外表，广搜的内涵，时间复杂度也比较优秀，感兴趣的读者可以阅读这篇博客。