搜索技巧之-剪枝
剪枝是去除搜索树当中不必要的搜索路径，从而优化算法，降低时间开销。
常见的剪枝包括：
1可行性剪枝 2排除等效剪枝 3最优性剪枝 4顺序剪枝 5记忆化剪枝
下面将一一举例介绍其原理：
1可行性剪枝
在寻找所有的解决方案时，若某种方案明显不可行/无法找到答案，则停止继续搜索。
2排除等效剪枝
当该方案和之前搜过的方案对结果具有相同效果时，可以只使用一个继续向下搜索。
3最优性剪枝
当前的方案与已有方案相比，结果明显不是最优的时候，例如在某一层取max/min后，发现不能得到更优解时，停止继续搜索。
4顺序剪枝
似乎不太常见，在搜索之前进行排序（预处理），搜索过程中可以结合其他方法进行剪枝。
5记忆化剪枝
当每个状态的结果是唯一确定且有可能会多次重复搜索时，记录每个状态的搜索结果，并在再次调用时直接返回记录值。
下面将是一些例题:
洛谷 P1731 生日蛋糕
从下往上搜索，枚举每层的半径和高度作为分支
搜索状态：第dep层，当前外表面积s,当前体积v,dep+1层的高度和半径
整个蛋糕的底面积=最底层的圆面积，这样在m-1层搜索时，只需要计算侧面积
剪枝：
1.是否可行剪枝
首先枚举，其次枚举
2.优化搜索顺序
倒序搜索枚举
3.可行性剪枝
预处理最小体积和侧面积，然后剪枝
可行剪枝
#include <bits/stdc++.h>
using namespace std;
int n,m;
int ans=2e9;
void dfs(int dep,int s,int v,int past_r,int past_h)
{
if(s >= ans) return;
if(dep == m+1 && v == n)
{
ans = min(ans,s);
return;
}
if(v >= n) return;
int rest_dep = m - dep + 1;
if(rest_dep * past_r * past_r * past_h + v < n) return;
if(dep == 1)
{
for(int r = past_r; r >= m; --r)
for(int h = m; h <= past_h; ++h)
dfs(dep + 1,s + r * r + 2 * r * h,v + r * r * h,r,h);
}
else
{
for(int r=past_r-1; r>=m-dep+1; --r)
for(int h=m-dep+1; h<past_h; ++h)
dfs(dep + 1,s + 2 * r * h,v + r * r * h,r,h);
}
}
int main()
{
scanf("%d%d",&n,&m);
dfs(1,0,0,28,28);
if(ans == 2e9) printf("0\n");
else printf("%d\n",ans);
}
洛谷 P1120 小木棍
剪枝
1.优化搜索顺序：从大到小排序，优先尝试长的木棍
2.排除等效分支：
(1).因为先拼一根a长度的，再拼一根b长度的等于先拼一根b长度的，再拼一根a长度,只要搜索其中一种
(2).记录最近一次尝试拼接的木棍长度，如果搜索失败则不尝试同种长度的木棍
(3).当尝试拼入的第一根木棍就返回失败，则直接回溯
(4).如果当前木棍拼入后，一节木棒被填充完整，而另一根木棍
失败了，则直接回溯
剪枝代码
#include<bits/stdc++.h>
#define MAXN 100005
using namespace std;
int n,sum=0,a[MAXN];
bool vis[MAXN];
int cmp(int a,int b)
{
return a>b;
}
bool dfs(int num,int len,int now_len,int number)
{
if(number==sum/len)return 1;
if(now_len==len)
{
if(dfs(1,len,0,number+1))return 1;
}
for(int i=num; i<=n; i++)
{
if(!vis[i]&&now_len+a[i]<=len)
{
vis[i]=true;
if(dfs(i+1,len,now_len+a[i],number))return 1;
vis[i]=false;
if(a[i]==len-now_len||now_len==0)break;
while(a[i]==a[i+1])i++;
}
}
return 0;
}
int main()
{
memset(vis,false,sizeof(vis));
scanf("%d",&n);
for(int i=1; i<=n; i++)
{
scanf("%d",&a[i]);
sum+=a[i];
}
sort(a+1,a+1+n,cmp);
for(int i=a[1]; i<=sum; i++)
{
if(sum%i!=0)continue;
if(dfs(1,i,0,0))
{
cout<<i<<endl;
break;
}
}
}
洛谷吃奶酪
我们只需要记录当前走过的距离来和ans做比较，重点讲一下如何将路径用二进制压缩。
首先我们在状态中有一个 当前到了数组哪个点的状态，命名为nowdot。每次定义p为当前点到第i个的距离，用二进制保存，初始化为int p = nowdot + (1 << (i - 1))，如果从p到i的距离已经有过更新并且本次构造的距离还大于之前，则跳过；否则更新，继续搜索。
状压+剪枝
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
//dfs(当前吃了多少个，当前吃的第几个，当前跑了多远，现在的点)
const int N = 20;
int n;
bool vis[N];
double ans = 1e9, dp[65000][20]; //dp用来存路径
struct node {
double x;
double y;
}a[N];
double discal (int l, int m) { //距离计算函数
return sqrt((a[l].x - a[m].x) * (a[l].x - a[m].x) + (a[l].y - a[m].y) * (a[l].y - a[m].y));
}
void dfs(int sum, int nowi, double dis, int nowdot) {
if (dis > ans) {
return;
} //剪枝
if (sum == n) {
if (dis < ans) ans = dis;
return;
}
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
int p = nowdot + (1 << (i - 1));
//二进制状态压缩从当前点到这个点
if (dp[p][i] != 0 && dp[p][i] <= dis + discal(nowi, i)) {
continue;
}
vis[i] = true;
dp[p][i] = dis + discal(nowi, i);
dfs(sum + 1, i, dp[p][i], p);
vis[i] = false;
}
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i].x >> a[i].y;
}
dfs(0, 0, 0, 0);
printf("%.2lf", ans);
return 0;
}
P1434 [SHOI2002] 滑雪
记忆化
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int n,m,a[201][201],s[201][201],ans;
bool use[201][201];//这个就是所谓的不需要
int dfs(int x,int y){
if(s[x][y])return s[x][y];//记忆化搜索
s[x][y]=1;//题目中答案是有包含这个点的
for(int i=0;i<4;i++)
{ int xx=dx[i]+x;
int yy=dy[i]+y;//四个方向
if(xx>0&&yy>0&&xx<=n&&yy<=m&&a[x][y]>a[xx][yy]){
dfs(xx,yy);
s[x][y]=max(s[x][y],s[xx][yy]+1);
}
}
return s[x][y];
}
int main()
{
scanf("%d%d",&n,&m);//同题目的R,C
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
for(int i=1;i<=n;i++)//找从每个出发的最长距离
for(int j=1;j<=m;j++)
ans=max(ans,dfs(i,j));//取最大值
printf("%d",ans);
return 0;
}