搜索优化剪枝策略

状态剪枝

如果将搜索的状态看作结点，状态之间的转移看作边，搜索的过程就构建出了一棵“搜搜树”。其实，这也是判定搜索题目的一个方法。
所谓“剪枝”，就是在搜索树上去掉一些枝杈不进行搜索，从而减少小时间消耗。搜索树的剪枝如下图所示。

系统地说，剪枝的策略分为可行性剪枝和最优性剪枝两种。
但需要指出的是，搜索题目的性质极其灵活，在应用时一定要具体问题具体分析，设计合适的剪枝策略，不必拘泥于所学。
例1：数的划分

【问题描述】
将整数n分成k份，且每份不能为空，问有多少种不同的分法。当n=7，k=3，下面三种分法被认为是相同的：1,1,5; 1,5,1; 5,1,1
【输入格式】
输入文件只有一行为两个整数n和k (6<n≤200，2≤k≤6)
【输出格式】
输出文件仅有一行为一个整数，即不同的分法数。
【样例输入】
7 3
【样例输出】
4
【样例解释】
四种分法为：1,1,5；1,2,4；1,3,3；2,2,3；

/*#include<bits/stdc++.h>
using namespace std;
int k,n,ans;
void dfs(int last,int sum,int p)//从last位置开始，划分的和sum;划分的段数p 
{
	int i;
	if(p==k)
	{
		if(sum==n)
			ans++;
		return;
	}
	for(i=last;sum+i*(k-p)<=n;i++)
		dfs(i,sum+i,p+1);
}
int main()
{
	cin>>n>>k;
	dfs(1,0,0);
	cout<<ans<<endl;
	return 0;
}
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
int n,k,ans;
int f[250][10];//已经分j份，且该份的和是i;这里n是资源，待分配 
/*1.先初始化，任何当k=1的情况下仅有一种分法。
2.然后如分析3组建dp方程，从i中分j份的方案数 (f[i,j]) , 为 i-1 中分 j-1 份 ( f[i-1,j-1] ,即分出_1_)
 和 i-j 分 j 份 (f[i-j][j],因为分出1后剩下 i-j 个可分的1，j 次机会) 的方案数之和。
3.同时要注意一个小小的细节(未经实测，可能不会导致WA)。
*/ 
int main()
{
	cin>>n>>k;
	f[0][0]=1;//初始化 
	for(int t=1;t<=n;t++)//分出来的整块的大小 
		for(int i=t;i<=n;i++)//整个一块的大小 
			for(int j=1;j<=k;j++)//分的段数 
				f[i][j]+=f[i-t][j-1];
	cout<<f[n][k];//输出将整数n分成k份的分法 
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

例2：生日蛋糕（上下届剪枝，优化搜索顺序，可行性剪枝，最优性剪枝）

【问题描述】
一个体积为Nπ的M层生日蛋糕，每层都是一个圆柱体。 从下往上数第i(1<=i<=M)层蛋糕是半径为Ri，高度为Hi的圆柱。当i<M时，Ri>Ri+1且Hi>Hi+1。希望蛋糕外表面（最下一层的下底面除外）的面积Q最小。令Q=Sπ，请编程对给出的N和M，找出、适当的Ri和Hi的值，使S最小。（除Q外，以上所有数据皆为正整数） 【输入格式】
第一行为N（N≤10000），表示待制作的蛋糕的体积为Nπ；
第二行为M（M≤20），表示蛋糕的层数为M。
【输出格式】
输出仅一行，是一个整数S（若无解则S=0）。
附：圆柱公式：体积V=πR²H；侧面积A’=2πRH；底面积A=πR²

【算法分析】
搜索框架：从下往上搜索，枚举搜索面对的状态有：正在搜索蛋糕第dep层，当前外表面面积s，当前体积v，第dep + 1 层的高度和半径。不妨用数组h和r分别记录每层的高度和半径。整个蛋糕的“上表面”面积之和等于最底层的圆面积，可以在第M层直接累加到 s 中。这样在第 M-1层往上的搜索中，只需要计算侧面积。
剪枝：
上下界剪枝
在第dep层时，只在下面的范围内枚举半径和高度即可。
首先，枚举R∈[dep,min⁡(⌊√N−v⌋,r[dep+1]−1)]
其次，枚举H∈[dep,min⁡(⌊N−v/R²⌋,ℎ[dep+1]−1)]
上面两个区间右边界中的式子可以通过圆柱体积公式：πR²H=π(N-v)得到.
优化搜索顺序
在上面确定的范围中，使用倒序枚举。
可行性剪枝
可以预处理出从上往下前i(1≤i≤M)层的最小体积和侧面积。显然，当第1~i层的半径分别取1，2，3，…，i，高度也分别取1，2，3，…，i时，有最小体积与侧面积。
如果当前体积v加上1~dep-1层的最小体积大于N，可以剪枝。
最优性剪枝1
如果当前表面积s加上1~dep-1层的最小侧面积大于已经搜到的答案，剪枝。
最优性剪枝2
1~dep-1层的体积可表示为n−v=∑_k=1^{dep−1▒ℎ[k]∗r[k]}2,
1~dep-1层的侧面积可表示为2∑_k=1^dep−1▒ℎ[k]∗r[k]。
因为2∑_k=1^{dep−1▒ℎ[k]∗r[k]=2/r[dep]∗∑_k=1}dep−1▒ℎ[k]∗r[k]∗r[dep]≥2/r[dep]∗∑_k=1^{dep−1▒ℎ[k]∗r[k]}2≥2(n−v)/r[dep]，所以当2(n−v)/r[dep]+s大于已搜到的答案时，可以剪枝。
加入以上五个剪枝后，搜索算法就可以快速求出该问题的最优解了。

例3：Addition Chains（优化搜索顺序）

【问题描述】
已知一个数列a0,a1…am（其中a0 = 1，am = n，a0 < a1 < a2 < … < am-1 < am）。对于每个k(1<=k<=m)，需要满足ak=ai+aj（0 <= i, j <= k-1，这里i与j可以相等）。
现给定n的值，要求m的最小值（并不要求输出）,及这个数列的值(可能存在多个数列,只输出任一个满足条件的就可以了)。
【输入格式】
多组数据，每行给定一个正整数n。输入以0结束。
【输出格式】
对于每组数据，输出满足条件的长度最小的数列。

【算法分析】
由于ak=ai+aj(0≤i,j<k),所以在搜索的过程中可采用由小到大搜索数列的每一项的搜索顺序进行试算。一般搜索时习惯于从小到大依次搜索每个数的取值，但是在这到题目中按照这样的顺序搜索编程运算其结果（效率）十分不理想。
由于题目要求的是m的最小值，也就是需要我们尽快得到数n，所以每次构造的数应当是尽可能大的数，根据题目的这个特性，我们将搜索顺序改为从大到小搜索每个数。后一种搜索顺序得到的程序效率大大地优于第一种搜索顺序得到的程序。
可见，选择合适的搜索顺序对于提高程序的效率是非常重要的，运用良好的搜索顺序来对搜索题目进行优化是性价比很高的技巧。

#include<cstdio>
#include<cstring>
using namespace std;
int a[105],bo[105],ans[105];
int n,m;
bool check(int v,int x)
{
	for (int i=0; i<=x; ++i)
	if (v-a[i]>=0 && bo[v-a[i]]) return 1;
	return 0;
}
void dfs(int x)
{
	if (x>=m) return;
	if (a[x]==n) {
		if (x<m) m=x,memcpy(ans,a,sizeof(ans)); 		
		return;
	}
	for (int j=n; j>a[x]; --j)
	if (check(j,x)){
		a[x+1]=j;
		bo[j]=1;
		dfs(x+1);
		bo[j]=0;
	}
	return;
}
int main()
{
	bo[1]=1;
	a[0]=1;
	while (scanf("%d",&n),n){
		for (int i=2; i<=n; ++i) bo[i]=0;
		m=1e5;
		dfs(0);
		for (int i=0; i<=m; ++i) printf("%d ",ans[i]);
		printf("\n");
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

例4：小木棍（多种剪枝策略）

【问题描述】
同样长的小木棍被随意砍成几段，已知每段的长都不超过50。现在，要把小木棍拼接成原来的样子，但却不知道开始时有多少根木棍和它们的长度。给出每段小木棍的长度，求原始木棍的最小可能长度。
【文件输入】
第一行为一个单独的整数 N 表示砍过以后的小木棍的总数，其中N<=60；
第二行为 N 个用空个隔开的正整数，表示 N根小木棍的长度。
【文件输出】
输出文件仅一行，表示要求的原始木棍的最小可能长度。

【算法分析】
要得到最小的原始木棍长度，可以按照分段数的长度，依次枚举所有的可能长度len；每次枚举len时，深搜判断是否能用截断后的木棍拼合出整数个len，能用的话，找出最小的len即可。对于1S的时间限制，用不加任何剪枝的深搜时，时间效率为指数级，效率非常低。对于此题，可从可行性和最优性上加以剪枝。
从最优性上来分析，可以剪枝以下2点：
①设所有木棍的长度和是sum，那么原长度(也就是需要输出的长度)一定能够被sum整除，即一定是拼出整数根。
②木棍原来的长度一定大于等于所有木棍中最长的那根。
综合上述两点，可知原木棍的长度len在最长木棍的长度到sum之间，且sum能被len整除。所以，在搜索原木棍的长度时，可以设定为从截断后所有木棍中最长的长度开始，每次增加长度后，必须能整除sum。
从可行性上来分析，可以再剪枝以下7点：
③短木棍比长木棍更灵活组合，所以可以对木棍按长度从大到小排序。
④在截断后的排好序的木棍中，当用木棍i拼合原始木棍时，可以从第i+1后的木棍开始搜。
⑤用当前最长长度的木棍开始搜，如果拼不出当前设定的原木棍长度len，则直接返回，换一个原始木棍长度len。
⑥相同长度的木棍不要搜索多次。用当前长度的木棍搜下去得不出结果时，可以提前返回。
⑦判断搜到的几根木棍组成的长度是否大于原始长度len，如果大于，可以提前返回。
⑧判断当前剩下的木棍根数是否能够拼的木棍根数，如果不够，肯定拼合不成功，直接返回。
⑨找到结果后，在能返回的地方马上返回到上一层递归处。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 66;
int n,sum,nm=maxn,mx,d;
int len[maxn],a[maxn],pre[maxn];
void dfs(int u,int k,int p)
{
	//当前长棍还有u没有拼，还有k根长棍没有拼，当前长棍的最短短棍长度是p
	if(u==0)
	{
		dfs(d,k-1,a[n]);
		return;
	 } 
	 if(k==0)
	 {
	 	cout<<d;
	 	exit(0);
	 }
	 p=(p<u)?p:u;
	 while(p&&len[p]==0)--p;
	 while(p)
	 {
	 	if(len[p])//枚举当前棍长 
	 	{
	 		--len[p];
	 		dfs(u-p,k,p);
	 		++len[p];
	 		if((u==p)||(u==d))return;
	 		p=pre[p];
		 }
		 else p=pre[p];
	 }
}
int main()
{
	cin>>n;
	for(int i = 1,x;i<=n;++i)
	{
		cin>>x;
		sum+=x;
		++len[a[i]=x];
	}
	sort(a+1,a+1+n);
	for(int i = 1;i<=n;i++)//预处理长度i的上一个长度
	{
		if(a[i]!=a[i-1])pre[a[i]]=a[i-1];
	 } 
	 for(d=a[n];(d<<1)<=sum;++d)
	 {
	 	if((sum%d)==0)
	 		dfs(d,sum/d,a[n]);
	 }
	 cout<<sum;
	 return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

练习题目：（www.51nod.com，自行注册，免费）
1、分成2组
2、邻之差为k
3、挑选数字
4、小明爱正方形

后续课程：
1、迭代加深与双向搜索
2、启发式搜索