【6】搜索剪枝优化学习笔记

前言

WFLS 2023 寒假集训 Day4 Day 5

搜索剪枝的复杂度很玄学，最好还是能剪枝就剪枝，只要不是错误的，总没有坏处。

最优化剪枝

当题目要求求最优解的时候，此时如果已经求出一个可行解，那么答案超过这个可行解的分支一定不是最优解，所以这些分支可以剪掉。

找到可行解

if(check()&&now<ans){ans=now;return;}

超过可行解

if(now>ans)return;

例题 $1$ ：

P1213 [USACO1.4][IOI1994]时钟 The Clocks

剪枝 $1$ ：等效冗余

我们知道，如果同一个操作执行了 $4$ 次，那么时钟就转了 $360$ 度，相当于没有转。所以如果同一个操作执行了超过 $4$ 次，那么一定会有更优解，这些分支是冗余的，所以剪枝。

剪枝 $2$ ：最优化剪枝

如果已经求出一个可行解，那么答案超过这个可行解的分支一定不是最优解，所以这些分支可以剪掉。

剪枝 $3$ ：记忆化剪枝

如果这个时钟状态已经访问过了，那么后面的分支就已经计算过了，没有必要再计算。由搜索顺序得到，第一次搜索到一个时钟状态一定是最优解，所以可以剪枝。

#include<bits/stdc++.h>
using namespace std;
int cl[9],ans=99999999,an[100],hu[100],did[100];
bool bef[4][4][4][4][4][4][4][4][4]; 
int cha[9][9]=
{
//A B C D E F G H I{1,1,0,1,1,0,0,0,0},{1,1,1,0,0,0,0,0,0},{0,1,1,0,1,1,0,0,0},{1,0,0,1,0,0,1,0,0},{0,1,0,1,1,1,0,1,0},{0,0,1,0,0,1,0,0,1},{0,0,0,1,1,0,1,1,0},{0,0,0,0,0,0,1,1,1},{0,0,0,0,1,1,0,1,1}
};
void nxt(int h)
{for(int i=0;i<9;i++)if(cha[h][i]){cl[i]=cl[i]+3;if(cl[i]==15)cl[i]=3;}
}void pre(int h)
{for(int i=0;i<9;i++)if(cha[h][i]){cl[i]=cl[i]-3;if(!cl[i])cl[i]=12;}
}bool check()
{for(int i=0;i<9;i++)if(cl[i]!=12)return 0;return 1;
}void dfs(int now)
{if(now>ans||now>40)return;if(check()&&now<ans){ans=now;for(int i=0;i<ans;i++)an[i]=hu[i];return;}if(bef[cl[0]/3-1][cl[1]/3-1][cl[2]/3-1][cl[3]/3-1][cl[4]/3-1][cl[5]/3-1][cl[6]/3-1][cl[7]/3-1][cl[8]/3-1])return;bef[cl[0]/3-1][cl[1]/3-1][cl[2]/3-1][cl[3]/3-1][cl[4]/3-1][cl[5]/3-1][cl[6]/3-1][cl[7]/3-1][cl[8]/3-1]=1;for(int i=0;i<9;i++){if(did[i]>=3)continue;nxt(i);hu[now]=i+1;did[i]++;dfs(now+1);did[i]--;hu[now]=0;pre(i);}return;
}int main()
{for(int i=0;i<9;i++)scanf("%d",&cl[i]);dfs(0);for(int i=0;i<ans;i++)printf("%d ",an[i]);return 0;
}

可行性剪枝

根据题目的要求，把已经明显不符合题目要求的分支剪去，可以避免搜索无效信息，降低程序的时间复杂度。

例题 $2$ ：

P1731 [NOI1999] 生日蛋糕

剪枝 $1$ ：最优化剪枝

如果已经求出一个可行解，那么答案超过这个可行解的分支一定不是最优解，所以这些分支可以剪掉。

剪枝 $2$ ：搜索顺序

可以贪心一下，先从大的搜索，这样后面的选择就会较多，得到可行解的几率也会更大。所以对于半径和高可以从大到小枚举。

剪枝 $3$ ：可行性剪枝

如果这一层蛋糕体积总和已经超过 $N$ ，那么这个分支就是不可行的，剪枝。

剪枝 $4$ ：可行性剪枝

如果这一层蛋糕半径和高小于剩余层数，由于 $R_i\gt R_{i+1}$ 且 $H_i\gt H_{i+1}$ ，所以接下来就算每次只减少 $1$ 也不够放那么多层蛋糕，所以这个分支就是不可行的，剪枝。

剪枝 $5$ ：可行性剪枝

设这一层蛋糕半径为 $R_n$ ，高为 $H_n$ ，那么这一层蛋糕的体积是：

$V_n=R_n^2\times H_n$

由于 $R_i\gt R_{i+1}$ 且 $H_i\gt H_{i+1}$ ，所以接下来每层只可能比这一层小。如果接下来全与这一层相等都无法到达 $N$ ，那么剪枝。

剪枝 $6$ ：可行性剪枝

由于 $R_i\gt R_{i+1}$ 且 $H_i\gt H_{i+1}$ ，逆向推理得到上面第一层最小 $R_n=1,H_n=1$ ，第二层最小 $R_n=2,H_n=2$ ，第三层 $\dots$ 。

可以把这些最小体积打成一张表，如果剩余体积不足这么多，就证明连最小情况的不合法，剪枝。

#include <bits/stdc++.h>
using namespace std;
int n,m,ans=99999999,mr[10000],mh[10000],t[16]={0,0,1,9,36,100,225,441,784,1296,2025,3025,4356,6084,8281,11025};
void dfs(int now,int sum,int cnt)
{if(sum>=n-t[m-now]&&now!=m)return;if(cnt>=ans)return;if(now==m){if(sum==n)ans=min(ans,cnt);return;}for(int i=mr[now]-1;i>=0;i--)for(int j=mh[now]-1;j>=0;j--){long long v=i*i*j;if(i<(m-now)||j<(m-now)||sum+v>n-t[m-now]||v<(n-sum)/(m-now))continue;mr[now+1]=i;mh[now+1]=j;if(now==0)cnt=i*i;dfs(now+1,sum+i*i*j,cnt+2*i*j);}
}int main()
{scanf("%d%d",&n,&m);mr[0]=sqrt(n)+1;mh[0]=n;dfs(0,0,0);printf("%d",ans);return 0;
}

记忆化剪枝

如果一个状态已经搜索过了，为了不重复搜索，可以把这个状态记录下来，下次再次搜索到就直接剪枝。

例题 $3$ ：

P1189 SEARCH

剪枝 $1$ ：记忆化剪枝

设状态 $f [x] [y] [d] = 1$ 表示在第 $d$ 步时访问过点 $(x, y)$ ，后面扩展的信息已经计算过了，没必要重复计算。如果再次搜索到，直接剪枝。

#include <bits/stdc++.h>
using namespace std;
int n,m,k,x,y;
int f[200][200][200];
char map1[60][60];
char ch,str[1000];
int dir[3000],cnt=1;
int x1[4]={-1,1,0,0};
int y2[4]={0,0,-1,1};
int dfs(int x,int y,int di)
{if(di==k+1){map1[x][y]='*';return 0;}if(f[x][y][di])return 0;for(int i=1;;i++){if(!(x+x1[dir[di]]*i<n&&x+x1[dir[di]]*i>=0&&y+y2[dir[di]]*i<m&&y+y2[dir[di]]*i>=0))break;if(map1[x+x1[dir[di]]*i][y+y2[dir[di]]*i]=='X')break;dfs(x+x1[dir[di]]*i,y+y2[dir[di]]*i,di+1);f[x][y][di]=1;}return 0;
}int main()
{scanf("%d%d",&n,&m);for(int i=0;i<n;i++){for(int j=0;j<m;j++){while(!(ch=='.'||ch=='X'||ch=='*'))ch=getchar();if(ch=='*'){x=i;y=j;}map1[i][j]=ch;ch='\0';}}scanf("%d",&k);for(int i=0;i<k;i++){scanf("%s",str);switch(str[0]){case 'N':dir[cnt++]=0;break;case 'S':dir[cnt++]=1;break;case 'W':dir[cnt++]=2;break;case 'E':dir[cnt++]=3;break;}}map1[x][y]='.';dfs(x,y,1);for(int i=0;i<n;i++){for(int j=0;j<m;j++)printf("%c",map1[i][j]);printf("\n");}return 0;
}

双向搜索

如果搜索有确定的始态和终态，那么可以从始态和终态分别出发进行搜索，把原搜索树分为深度为原搜索树一半的两颗子树。最后在交汇处进行计算。也就是所谓的

Meet in the Middle

对于指数级增长的搜索，这无疑是个大优化。

例题 $4$ ：

P4799 [CEOI2015 Day2] 世界冰球锦标赛

剪枝 $1$ ：双向搜索

首先搜索前一半序列，把所有选择计算出来，存入一个数组并排序。

然后搜索后一半序列，搜索完成后进行 Meet in the Middle ：

在前一半序列中二分查找，找到与这一次搜索结果之和最接近但不超过钱数 $M$ 的数组元素。由于序列有序，那么这个以及其之前的元素与结果相加均不超过 $M$ ，加到 $an s$ 里就行了。

时间复杂度： $O(2^{\frac{n}{2}}+2^{\frac{n}{2}}\log2^{\frac{n}{2}})$

虽然式子看起来很奇怪，但是确实是正确的时间复杂度。

#include <bits/stdc++.h>
using namespace std;
long long n,m,a[100],q[(1<<21)+1],cq=0,ch=0,ans=0;
void dfs1(long long now,long long sum,long long dep)
{if(now==dep){q[cq++]=sum;return;}dfs1(now+1,sum,dep);if(sum+a[now]<=m)dfs1(now+1,sum+a[now],dep);return ;
}void search(long long a)
{long long k=m-a;long long l=0,r=cq-1;while(l<r){long long mid=(l+r+1)/2;if(q[mid]<=k)l=mid;else r=mid-1;}ans+=(l+1);
}void dfs2(long long now,long long sum,long long dep)
{if(now==dep){search(sum);return;}dfs2(now+1,sum,dep);if(sum+a[now]<=m)dfs2(now+1,sum+a[now],dep);return ;
}int main()
{scanf("%lld%lld",&n,&m);for(int i=0;i<n;i++)scanf("%lld",&a[i]);sort(a,a+n);reverse(a,a+n);dfs1(0,0,n/2);sort(q,q+cq);dfs2(n/2,0,n);printf("%lld",ans);return 0;
}