浅谈搜索的亿些优化 ---- 1

· · 算法·理论

读这个文章的时候请确保你会 DFS 与 BFS ,否则出门右转，去这里与这里学习。

众所周知，搜索是时间与空间开销非常大的算法。

我们可以对它进行优化。

第一个优化:搜索剪枝

搜索剪枝是可以对搜索优化很多的算法。

它可以对搜索树的一些不可能有答案的枝条提前预判然后不搜它进行优化。

搜索剪枝分为四类：

  1. 搜索顺序:对顺序排序，将含有答案的枝条尽量排前面。

  2. 可行性剪枝:将不可能搜到答案的枝条直接不搜。

  3. 最优性剪枝:将已搜到的答案对后面产生的答案作比较，如果不可能比它更优那么直接不搜，常配合搜索顺序一起剪。

  4. 重复性剪枝:尽量减少重复的状态，以降低时间复杂度。

例题:小木棍.

这是一道搜索剪枝经典题目，考虑如下剪枝：

分析：

可以考虑成排列问题，对于每个答案，验证一次的复杂度为 n!。

必然会超时，考虑优化每一次的dfs：

  1. 搜索顺序：因为短木棍更灵活，所以考虑后期救场，将配对每一组时，将木棍从大到小排序。

并且总值域比 n 小，所以以木棍长度建立桶，直接用桶记录支持爆搜。

  1. 可行性：木棍长度之和 mod 最终答案 必须为 0。如果刚拼接好一个木棍或者加上这个木棍刚好拼完，并搜索失败，可以直接回溯.因为在用其他木棍搜下去和它们也是用那么多的木棍拼是一样的，也会失败。

  2. 最优原则：循环从小到大枚举最终答案。

  3. 降低重复运算：用从大到小的顺序保证不会重复。

代码:

#include<bits/stdc++.h>
using namespace std;
int n;
int a[110];
int sum;
int minn=110,maxn;
inline int read(){
    int x=0; bool f=1; char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=0;
    for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
    if(f) return x;
    return 0-x;
}
void write(int x){
    if(x/10==0){
        putchar(x%10+'0');
        return;
    }
    if(x<0) putchar('-'),x=-x;
    write(x/10);
    putchar(x%10+'0');
}
void dfs(int num,int cnt,int maxm,int ans){
    if(num==0){//配对完毕 
        write(ans);
        exit(0);
    }
    if(cnt==ans){//配对一组 
        dfs(num-1,0,maxn,ans);
        return;
    }
    for(int i=maxm;i>=minn;i--)
        if(a[i]>0 && cnt+i<=ans){//能选就选 
            a[i]--;//拿起木棍 
            dfs(num,cnt+i,i,ans);//将此木棍选上 
            a[i]++;//放下木棍 
            if(cnt==0 || i+cnt==ans) 
                return;
        }
}
int main() {
    n=read();
    for(int i=1;i<=n;i++){
        int x;
        x=read();
        if(x>50) continue;
        sum+=x;
        minn=minn>x?x:minn,maxn=maxn<x?x:maxn;
        a[x]++;
    }
    int tmp=sum>>1;
    for(int i=maxn;i<=tmp;i++)
        if(sum%i==0)
            dfs(sum/i,0,maxn,i);
    write(sum);
    return 0;
}

例题:Sudoku.

分析: 一道填数独问题，搜索量有点大。

我们采用一下剪枝:

  1. 遍历当前所有空格，若某位置 A~P 都不能填，回溯。若某位置只有一个字母可填，填上字母。

  2. 遍历所有行 与 列 与 十六宫格，若某字母不能填在该行 与 列 与 十六宫格的任意空位上，回溯。若某字母只有一个空位可填，填上字母。

  3. 最后，找到可填位置最少的地方，进行下一层搜索。

注意要用位运算标记减小常数,一定要记录下之前的数组呀。

代码.

**例题***:[NOI2003] 智破连环阵。

请先到这里学习匈牙利算法（只看那一部分）。

水黑。

首先，每个炸弹能炸到的一定是一个连续的区间 [l,r]。

对于同一个炸弹，[l,r] 不固定。

但是对于同一个炸弹，l 固定，r 固定且能求。

不然不满足炸掉的顺序要求。

我们可以预处理 c_{i,j} 表示第 i 个炸弹能否炸到第 j 个点。（距离够不够）

接着处理 next_{i,j} 表示第 i 个炸弹的一种炸法的 l 为 j 所对应的 r，递推可实现。

处理剪枝所用的 f_j 为炸弹不停的炸（也就是可以重复用），炸第 j 个到第 m 个点的最小用的炸弹数。（用于类似于 A^*（后面要讲））

于是开始 dfs。 设 `dfs` 的一个状态炸了前 $a-1$ 个点，用了 $b$ 个炸弹。 一个可行性兼最优性剪枝就是只要 $b+f_a\le ans$，直接 `return`。 $ans$ 为当前最优的答案，最开始为 $n$（都用）。 因为 $f_a$ 必定比正确答案要小（重复用），所以成立。 枚举要炸的区间 $[a,i]$，建成一个点，跑一下匈牙利算法。 看一下能否匹配上，不能匹配就不递归了。（可行性剪枝） 因为此题只要最大匹配数等于点数的情况。 注意回溯清空。 代码。 ```cpp #include<bits/stdc++.h> using namespace std; int m,n,k; int X[110],Y[110]; int nxt[110][110],f[110],ans; bool c[110][110]; int mat[110]; bool vis[110]; int e[110][110]; bool dfs2(int x){//匈牙利算法 for(int i=1;i<=n;i++) if(!vis[i] && e[x][i]){ vis[i]=1; if(!mat[i] || dfs2(mat[i])){ mat[i]=x; return 1; } } return 0; } void dfs(int a,int b){//炸了前 a-1 个，用了 b 个炸弹 if(b+f[a]>=ans) return;//剪枝 if(a>m){//炸完收工 ans=min(ans,b); return; } int bm[110]={0}; for(int i=1;i<=n;i++) bm[i]=mat[i];//储存 for(int i=a;i<=m;i++){//枚举区间终点 memset(vis,0,sizeof vis);//清空匈牙利算法的 vis for(int j=1;j<=n;j++) if(c[j][a] && i<=nxt[j][a]) e[b+1][j]=1;//右部点（连环阵） b+1 向左部点（炸弹）连边，注意一些右部点被缩成了一个点 bool p=dfs2(b+1);//对那个右部点去匹配 //为什么要别扭的让右部点去匹配左部点，因为需要搜到最后才能确定所以左部点连接的右部点，但是每一步都可以确定一个右部点连的所有边，这样可以直接边搜边跑匈牙利算法，方便剪枝 if(p) dfs(i+1,b+1);//能配上就继续搜 for(int j=1;j<=n;j++) mat[j]=bm[j];//回溯 for(int j=1;j<=n;j++) if(c[j][a] && i<=nxt[j][a]) e[b+1][j]=0;//回溯 } } inline int dist(int x,int y,int x2,int y2){//求距离的平方 return (x-x2)*(x-x2)+(y-y2)*(y-y2); } int main() { cin>>m>>n>>k; for(int i=1;i<=m;i++) cin>>X[i]>>Y[i],f[i]=2e9; for(int i=1;i<=n;i++){ int X2,Y2; cin>>X2>>Y2; for(int j=1;j<=m;j++) if(dist(X[j],Y[j],X2,Y2)<=k*k) c[i][j]=1;//能否炸到 for(int j=m;j>=1;j--) if(c[i][j]) nxt[i][j]=max(j,nxt[i][j+1]);//l 固定，求 r } for(int j=m;j>=1;j--) for(int i=1;i<=n;i++) if(c[i][j]) f[j]=min(f[j],f[nxt[i][j]+1]+1);//简单的线性 dp 求重复用炸弹用的种数，不用多讲 ans=n;//初始 ans dfs(1,0); cout<<ans; return 0; } ``` # 第二个优化:迭代加深 迭代加深，顾名思义，是一层一层向下搜，类似于 BFS。 BFS 有什么缺点，那就是占空间，但在某些时候比 DFS 快。 毕竟，如果 DFS 找错分支，而那个分支没有答案并且很深，就会耗费大量的时间。 于是，我们想着，可以自小到大枚举深度进行 DFS，这样既能保证，这些节点会一层一层搜到，加快寻找答案的速度，又不占空间。 例题:[Addition Chains](https://www.luogu.com.cn/problem/UVA529)。 此题可以用迭代加深一层一层的向下，但是还会TLE，我们需要适当的剪枝。 剪枝方案如下: 1. 中途判断是否合法。 2. $a_i$ 一定小于 $a_{i-1}$ 的二倍。 有了这些剪枝，配上迭代加深，成功AC。 代码: ```cpp #include<bits/stdc++.h> using namespace std; int n,a[20010]={1}; bool b[20010]; void print(int n){ for(int i=0;i<=n;i++) cout<<a[i]<<" "; cout<<"\n"; } bool dfs(int x,int dep){ if(x>dep) return a[dep]==n; if(a[x-1]*(1<<(dep-x+1))<n) return false; for(int i=x-1;i>=0;i--) for(int j=x-1;j>=i;j--){ int k=a[i]+a[j]; if(k>min(n,a[x-1]*2)) break; if(k<=a[x-1]) continue; a[x]=k; if(dfs(x+1,dep)) return true; } return false; } void solve(){ memset(b,0,sizeof b); memset(a,0,sizeof a); a[0]=1; cin>>n; if(n==0) exit(0); for(int i=0;i<=n;i++) if(dfs(1,i)){ cout<<i+1<<" "; print(i); return; } } int main() { while(true) solve(); return 0; } ``` 例题:[埃及分数](https://www.luogu.com.cn/problem/P1763)。 此题有可能搜索深度很大，但答案很浅，所以采用迭代加深。 我们采用如下剪枝。 让分母从小到大的DFS排除重复。 每次选的数之和不能超过 $\frac{a}{b}$。 搜倒数第二个的时候可以确定最后一个数，可以减少一层搜索，加快速度。 最后再卡下常,AC。 下一篇:[浅谈搜索的亿些优化 ---- 2](https://www.luogu.com.cn/blog/libingyue2011/qian-tan-sou-suo-di-yi-suo-you-hua-2-post).