《算法竞赛进阶指南》0x23剪枝

剪枝，就是减少搜索树的规模、尽可能排除搜索书中不必要的分支的一种手段。形象地看，就好像剪掉了搜索树的枝条，故被称为“剪枝”。在深度优先搜索中，有以下常见的剪枝方法。

1.优化搜索顺序
在一些搜索问题中，搜索树的各个层次、各个分支之间的顺序不是固定的。不同的搜索顺序会产生不同的搜索树形态，其规模大小也相差甚远。
(1).在小猫爬山问题中，把小猫按照重量递减的顺序进行搜索；
(2).在数独问题中，优先搜索“能填的合法数字”最少的位置。

2.排除等效冗余
在搜索过程中，如果我们能判定从搜索树当前节点沿着几条不同的分支到达的子树是等效的，那么只需要对一条分支执行搜索。

3.可行性剪枝
在搜索过程中，及时对当前状态进行检查，如果发现分支已经无法到达递归边界就执行回溯。
某些问题的条件范围是一个区间，此时可行性剪枝也被称为“上下界剪枝”。

4.最优性剪枝
在最优化问题的搜索过程中，如果当前花费的代价已经超过了当前搜到的最优解，无论采取多么优秀的策略到达边界，都不可能更新答案。此时可以停止对该分支的搜索，执行回溯。

5.记忆化
可以记录每个状态的搜索结果，在重复遍历一个状态时直接检索并返回。这就好比我们对图进行深度优先遍历时，标记一个节点是否被访问过。
在小猫爬山和数独问题中，搜索算法的状态空间其实都是“树”形，不会重复访问，所以不需要进行记录。

例题
acwing167.木棒

搜索的状态包括已经拼好的木棍根数，正在拼的当前木棍的长度，每根木棍的使用情况。 在各个状态下，我们从尚未使用的木棍里选择一个，尝试频道当前的原始木棒里。
剪枝策略
1.从小到大枚举原始木棒的长度len，当然应为sum的约数(可行性)，木棍的根数cnt=sum/len。
2.把木棍从小到大排序，优先尝试较长的木棍。（优化搜索顺序）
3.排除等效冗余
(1).限制先后加入一根原始木棒的长度是递减的。例如312，123，231本质上是等效的。
(2).对于原始木棒，记录最近一次尝试拼接的长度，如果失败不在尝试拼接其他相同长度的小木棍。
(3).如果当前原始木棒中“尝试拼接第一根木棍”的递归分支就返回失败，那么直接判定当前分支失败，立即回溯。
证明：后面还没有进行拼接的原始木棒和当前这一个木棒是等效的，如果当前失败，那么拼到后面也会失败。
(4).如果在当前原始木棒中拼入一根木棍后，木棒恰到拼接完整，并且接下来拼接剩余原始木棒的递归分支返回失败，那么直接判定当前分支失败，立即回溯。
证明：如果不拼接这一根木棍，那么就是拼接若干根更小的，根据贪心的思想肯定不会比现在更优。

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int a[100],v[100];
int n,sum,len,cnt;
//正在拼第stick根木棒
//第stick根木棒当前长度是s
//拼接到第stick根木棒中的上一根小木棍是last
bool dfs(int stick,int s,int last)
{if(stick>cnt)return true;//搜索成功if(s==len)return dfs(stick+1,0,1);//去拼下一根for(int i=last;i<=n;i++)//剪枝3-1{if(v[i]||s+a[i]>len)continue;v[i]=1;if(dfs(stick,s+a[i],last+1))return true;v[i]=0;int j=i+1;//剪枝3-2while(j<n&&a[i]==a[j])j++;i=j-1;if(!s||s+a[i]==len)return false;//剪枝3-3，3-4}return false;//所有分支均尝试过，搜索失败
}
int main()
{while(cin>>n,n){sum=0;memset(v,0,sizeof v);for(int i=1;i<=n;i++){cin>>a[i];sum+=a[i];}sort(a+1,a+1+n);reverse(a+1,a+1+n);for(len=a[1];len<=sum;len++){if(sum%len)continue;cnt=sum/len;if(dfs(1,0,1)){cout<<len<<endl;break;}}}return 0;
}

acwing168.生日蛋糕

1.优化搜索顺序
层间为从下往上搜索，层间先枚举r再枚举h，均为从大向小枚举。
2.上下界剪枝
u ≤ R u ≤ m i n { R u + 1 − 1 , n − v u } u \leq R_{u} \leq min\{R_{u+1}-1,\sqrt{\frac{n-v}{u}}\} u≤Ru​≤min{Ru+1​−1,un−v​ ​}
u ≤ H u ≤ m i n { H u + 1 − 1 , n − v R u 2 } u \leq H_{u} \leq min\{H_{u+1}-1,\frac{n-v}{R_u^2}\} u≤Hu​≤min{Hu+1​−1,Ru2​n−v​}
3.可行性剪枝
预处理从上往下的最小体积minv和侧面积mins。如果当前体积v加上上面所有层的最小体积大于n，可以剪枝。
4.最优性剪枝1
如果当前表面积s加上上面所有层的最小表面积大于等于ans，可以剪枝。
5.最优性剪枝2
上面所有层的体积可以表示为
$n-v={\sum }_{k=1}^{dep-1}H[k]\ast R[k{]}^2$
上面所有层的表面积可以表示为
$2{\sum }_{k=1}^{dep-1}H[k]\ast R[k]=\frac{2}{R[dep]}{\sum }_{k=1}^{dep-1}H[k]\ast R[k]\ast R[dep]\ge \frac{2}{R[dep]}{\sum }_{k=1}^{dep-1}H[k]\ast R[k{]}^2\ge \frac{2(n-v)}{R[dep]}$

所以当$\frac{2(n-v)}{R[dep]}+s$大于已经搜索到的答案时，可以剪枝。

#include<iostream>
#include<cmath>
using namespace std;
#define INF 1e9
int n,m;
int minv[25],mins[25];
int r[25],h[25];
int ans=INF;
void dfs(int u,int v,int s)
{if(!u){if(v==n)ans=min(ans,s);return ;}if(v+minv[u]>n)return ;if(s+mins[u]>=ans)return ;if(s+2*(n-v)/r[u+1]>=ans)return ;for(int i=min(r[u+1]-1,(int)sqrt((n-v)/u));i>=u;i--){for(int j=min(h[u+1]-1,(n-v)/i/i);j>=u;j--){int t=0;if(u==m)t=i*i;r[u]=i;h[u]=j;dfs(u-1,v+i*i*j,s+t+2*i*j);}}
}
int main()
{cin>>n>>m;for(int i=1;i<=m;i++){minv[i]=minv[i-1]+i*i*i;mins[i]=mins[i-1]+2*i*i;}r[m+1]=h[m+1]=INF;dfs(m,0,0);if(ans!=INF)cout<<ans;else cout<<0;return 0;
}

acwing169数独2

总体思路：每次找到一个空格，枚举空格选择哪个字母，然后往下递归。
边界：所有空格都填完。
然后有很多剪枝：
1、对于每个空格，如果不能填任何一个字母，则无解；如果只能填一个字母，那么直接填上;
2、对于每一行，如果某个字母不能出现在任何一个位置，则无解；如果某个字母只有一个位置可以填，则直接填上；
3、对于每一列，同2；
4、对于每个16宫格，同2；
5、每次选择空格时，选择备选方案(能填的字母数量)最少的格子来填。

#include <bits/stdc++.h>
using namespace std;
const int N=16;
int ones[1<<N],cnt_log[1<<N];//ones[x]表示x在二进制下有多少个1；log[x]表示log(x)的值 
int state[N][N];//状态存储，表示x行y列这个格子可以填哪些数（0-15），15位二进制表示 
char str[N][N+1];
int bstate[N*N+1][N][N],bstate2[N*N+1][N][N];//bstate和bstate2都存储状态的备份(搜索最多有N*N层，每层有一个备份) 
char bstr[N*N+1][N][N+1];//输入的N宫格也要备份 inline int lowbit(int x)//返回x在二进制下的最后一个1  (inline加速函数调用过程)
{return x & -x;
}void draw(int x,int y,int c)//在(x,y)这个格子上写上字母c(0到15表示A到P) 
{str[x][y]='A'+c;//先写进去，转换为原来的字母 for (int i=0;i<N;++i)//更新state {state[x][i] &= ~(1 << c);//x这一行其他位置都不能再填c (把表示c的二进制位改成0，yxc大佬的位运算)state[i][y] &= ~(1 << c);//y这一列其他位置都不能再填c }int sx=x/4*4,sy=y/4*4;//把(x,y)所在的十六宫格也做一次同样的操作 for (int i=0;i<4;++i)for (int j=0;j<4;++j)state[sx+i][sy+j] &= ~(1 << c);//同上 state[x][y]=1<<c;
}bool dfs(int cnt)//传入的参数cnt表示当前空格个数 
{if (!cnt) return true;//cnt为零就找到了方案，返回trueint kcnt=cnt;//先进行备份 //剪枝1：对于每个空格，如果不能填任何一个字母，则返回false；如果只能填一个字母，那么直接填上for (int i=0;i<N;++i)//直接枚举所有的空格for (int j=0;j<N;++j)if (str[i][j]=='-')//如果当前格子是空格 {if (!state[i][j])//如果不能填任何一个字母，则返回false；并且copy回去 {return false;}if (ones[state[i][j]]==1)//如果只能填一个字母，那么直接填上{draw(i,j,cnt_log[state[i][j]]);--cnt;//填好一个空格，所以剩余空格数减1}}//剪枝2：对于每一行，如果某个字母不能出现在任何一个位置，则返回false；如果某个字母只有一个位置可以填，则直接填上 for (int i=0;i<N;++i)//枚举所有行 {int sor=0,sand=(1<<N)-1;//sor存的是这一行里每个格子备选方案的并集;sand用来找“如果某个字母只有一个位置可以填”，先假设所有字母都符合要求 int drawn=0;//drawn表示所有已经填上的字母是哪些 for (int j=0;j<N;++j)//枚举当前行所有格子 {int s=state[i][j];//只是为了少打字 sand &= ~(sor & s);//把不符合要求的删掉(和前面更新state是一个道理) sor |= s;//求并集 if (str[i][j]!='-') drawn |= state[i][j];//如果当前这个位置已经填上字母，就记录下来 }if (sor!=(1<<N)-1)//如果这个并集不够A到P就是无解 {return false;}//这样以后sand中是1的位置就表示这个字母有一个位置可以填for (int j=sand;j;j-=lowbit(j))//所以把所有是1的位置枚举一遍 {int t=lowbit(j);//也是为了少写一点 if (!(drawn & t))//如果正好也没填过就填上 {for (int k=0;k<N;++k)//更新state if (state[i][k] & t){draw(i,k,cnt_log[t]);--cnt;break;}}}}//剪枝3：对于每一列，同剪枝2  (直接把上面复制过来再把i和j调换一下就好了) for (int i=0;i<N;++i){int sor=0,sand=(1<<N)-1;int drawn=0;for (int j=0;j<N;++j){int s=state[j][i];sand &= ~(sor & s);sor |= s;if (str[j][i]!='-') drawn |= state[j][i];}if (sor!=(1<<N)-1){return false;}for (int j=sand;j;j-=lowbit(j)){int t=lowbit(j);if (!(drawn & t)){for (int k=0;k<N;++k)if (state[k][i] & t)//这里i和k也要和上面要反一下 {draw(k,i,cnt_log[t]);--cnt;break;}}}}//剪枝4：对于每个N宫格，同剪枝2for (int i=0;i<N;++i)//i枚举每个N宫格的位置 {int sor=0,sand=(1<<N)-1;int drawn=0;for (int j=0;j<N;++j)//j枚举一个N宫格的每个位置 {int sx=i/4*4,sy=i%4*4;int dx=j/4,dy=j%4;//需要定义一个偏移量 int s=state[sx+dx][sy+dy];sand &= ~(sor & s);sor |= s;if (str[sx+dx][sy+dy]!='-') drawn |= state[sx+dx][sy+dy];}if (sor!=(1<<N)-1){return false;}for (int j=sand;j;j-=lowbit(j)){int t=lowbit(j);if (!(drawn & t)){for (int k=0;k<N;++k){int sx=i/4*4,sy=i%4*4;int dx=k/4,dy=k%4;if (state[sx+dx][sy+dy] & t){draw(sx+dx,sy+dy,cnt_log[t]);--cnt;break;}}}}}//啊，还剩一个剪枝啦 //剪枝5：每次选择空格时，选择备选方案(能填的字母数量)最少的格子来填 if (!cnt) return true;//哦对，先看看现在有没有填完(一个小剪枝) int x,y,s=100;//(x,y)存储最后选择的格子，s是备选方案最小值 for (int i=0;i<N;++i)//遍历一遍所有的格子 for (int j=0;j<N;++j)if (str[i][j]=='-' && ones[state[i][j]]<s)//如果当前格子还没填过，并且这个格子的备选方案更少，就更新 {s=ones[state[i][j]];x=i,y=j;}//求完了那个格子备选方案最少，然后枚举应该在这个格子填那个字母 memcpy(bstate[kcnt],state,sizeof state);//先备份一下，bstate2在这里终于用到了 memcpy(bstr[kcnt],str,sizeof str);for (int i=state[x][y];i;i-=lowbit(i))//枚举这个格子的备选方案 {draw(x,y,cnt_log[lowbit(i)]);if (dfs(cnt-1)) return true;//进行下一层递归，如果成功，返回true memcpy(state,bstate[kcnt],sizeof state);memcpy(str,bstr[kcnt],sizeof str);}//失败了也要copy回来 memcpy(state,bstate[kcnt],sizeof state);memcpy(str,bstr[kcnt],sizeof str);return false;//一直没找到返回false 
}int main()
{for (int i=0;i<N;++i) cnt_log[1<<i]=i;//预处理cnt_log数组，如log(2)=1,log(4)=2,log(8)=3 for (int i=0;i<(1<<N);++i)//预处理ones数组 for (int j=i;j;j-=lowbit(j))//j每次减去最后一个1 ++ones[i];//每减一个1说明这个i就多一个1 while (cin>>str[0])//多组测试数据 {for (int i=1;i<N;++i) cin>>str[i];for (int i=0;i<N;++i)//预处理statefor (int j=0;j<N;++j)state[i][j]=(1<<N)-1;//一开始假设所有空格都是空的int cnt=0;//存储空格个数for (int i=0;i<N;++i)//接着在遍历一遍，看那些格子已经填好了for (int j=0;j<N;++j)if (str[i][j]!='-') draw(i,j,str[i][j]-'A');//如果已经填好了就更新state,A到P分别用0到15表示else ++cnt;dfs(cnt);//DFS开始for (int i=0;i<N;++i) cout<<str[i]<<endl;//输出答案puts("");//每次输出完答案加一个空行}return 0;
}