搜索剪枝

目录

什么是剪枝

几种常见的剪枝

1.可行性剪枝

2.排除等效冗余

3.最优性剪枝

4.顺序剪枝

5.记忆化

运用实例

1.选数

2.吃奶酪

3.小木棍

剪枝：通过某种判断，避免一些不必要的遍历过程。

搜索的时间复杂度通常很大，通过剪枝对搜索进行优化，可以大大提高程序运行的效率。

判断继续搜索是否能得到答案，如果不能，就返回

即：不可行，就返回

在搜索的几个分支中具有完全相同的效果时，选择其中一个走即可

即：有相同，选一个

和可行性剪枝有点相似，区别在于继续搜索可能得到答案，但一定不是最优

首先得到最优解：每搜索到一个解，和之前的解做对比，得到最优解

然后最优性剪枝：如果当前搜索到的解已经超过最优解，就返回

即：非最优，就返回

优化搜索顺序，更快得到解

即：先排序，再搜索

记录每个状态的搜索结果，在后续搜索过程中检索这个状态，如果重复，就返回

即：有重复，就返回

（详见洛谷P1036）：从n个整数中选k个整数相加，求和为素数共有多少种

输入：n，k，n个整数

输出：种类数

运用：可行性剪枝

#include
#include
#include
#define maxn 25
using namespace std;

int a[maxn];
int ans = 0;
int n, k;

bool isprime(int m)
{
	for (int i = 2; i <= sqrt(m); i++)
		if (m % i == 0) return false;
	return true;
}

void dfs(int start,int count,int sum)//当前第start个数，当前已选数个数，当前已选数和
{
	if(count+n-start+1> n >> k;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	
	dfs(1,0,0);
	cout << ans;
}

（详见洛谷P1433）：有n块奶酪，现在要把它们都吃掉，求最短的经过的距离(初始在原点处)

输入：奶酪数量n，每块奶酪的坐标

输出：最少距离（保留两位小数）

运用：可行性剪枝，最优性剪枝，记忆化剪枝

首先只加上可行性剪枝：

#include
#include
#include
#include
#define maxn 20
using namespace std;

double ans= 0x3f3f3f3f;
int n,visited[maxn];

struct POINT

{
	double x, y;
}a[maxn];


double dis(POINT& a, POINT& b)
{
	return sqrt(pow((a.x - b.x), 2)*1.0 + pow((a.y - b.y), 2)*1.0);
}

void dfs(int now,int count,double sum)//序号,吃掉数量,距离
{   
	if (count == n)
	{
		ans = min(ans, sum);
		return;//不可行，返回
	}

	for (int i = 1; i <= n; i++)
	{
		if (!visited[i])
		{
			visited[i] = 1;
			dfs(i, count+1, sum +dis(a[now],a[i]));
			visited[i] = 0;
		}
	}
}

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i].x >> a[i].y;
	a[0].x = 0;
	a[0].y = 0;
	dfs(0,0,0);
	cout <

#include
#include
#include
#include
#define maxn 20
using namespace std;

double ans= 0x3f3f3f3f;
int n,visited[maxn];

struct POINT

{
	double x, y;
}a[maxn];


double dis(POINT& a, POINT& b)
{
	return sqrt(pow((a.x - b.x), 2)*1.0 + pow((a.y - b.y), 2)*1.0);
}

void dfs(int now,int count,double sum)//序号,吃掉数量,距离
{
	if (sum >= ans)//最优性剪枝
		return;

	if (count == n)
	{
		ans = min(ans, sum);
		return;
	}

	for (int i = 1; i <= n; i++)
	{
		if (!visited[i])
		{
			visited[i] = 1;
			dfs(i, count+1, sum +dis(a[now],a[i]));
			visited[i] = 0;
		}
	}
}

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i].x >> a[i].y;
	a[0].x = 0;
	a[0].y = 0;
	dfs(0,0,0);
	cout <

#include
#include
#include
#include
#define maxn 20
using namespace std;

double ans= 0x3f3f3f3f;
int n,visited[maxn];
double map[maxn][maxn];

struct POINT

{
	double x, y;
}a[maxn];


double dis(POINT& a, POINT& b)
{
	return sqrt(pow((a.x - b.x), 2)*1.0 + pow((a.y - b.y), 2)*1.0);
}

void dfs(int now,int count,double sum)//序号,吃掉数量,距离
{
	if (sum >= ans)//最优性剪枝
		return;

	if (count == n)
	{
		ans = min(ans, sum);
		return;
	}

	for (int i = 1; i <= n; i++)
	{
		if (!visited[i])
		{
			if (map[now][i])//记忆化，提取之前记录过的距离
			{
				visited[i] = 1;
				dfs(i, count + 1, sum + map[now][i]);
				visited[i] = 0;
			}
			else
			{
			map[now][i] = dis(a[now], a[i]);//记忆
			visited[i] = 1;
			dfs(i, count+1, sum +map[now][i]);
			visited[i] = 0;
			}
		}
	}
}

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i].x >> a[i].y;
	a[0].x = 0;
	a[0].y = 0;
	dfs(0,0,0);
	cout <

#include
#include
#include
#include
using namespace std;

int n;
int a[110];

int maxm = 0, minm = 51;//小木棍最长长度，最短长度
int ans;//当前成功拼接的木棍数
int p = 0;//木棍总长度

void dfs(int x, int y, int z)//x:每根木棍期望长度，y：现在拼成长度，z：上一次使用的木棍长度
{
	if (ans * x == p)
	{
		cout << x;
		exit(0);//（最优性剪枝）
	}
	for (int i = z; i >= minm; i--)//从最长的小木棍开始拼（顺序剪枝）
	{
		if (a[i] && y + i <= x)//长度为a[i]的木棍拼接起来不会超过期望长度
		{
			y += i;
			a[i]--;
			if (y == x)
				ans++, y = 0;//拼接成功

			if (y == 0)
				dfs(x, y, maxm);//搜索下一个木棍
			else
				dfs(x, y, i);//搜索下一个小木棍

			//回溯
			a[i]++;
			if (ans > 0 && y == 0)y = x - i,ans--;
			else y -= i;

			if (y == 0) break;//拼接没有成功，返回（可行性剪枝）
			if (y + i == x)break;//到达上一根木棍拼接状态，返回
		}
	}
}

int main()
{
	cin >> n;
	
	for (int i = 1; i <= n; i++)
	{
		int temp;
		cin >> temp;
		if (temp <= 50)
		{	
			a[temp]++;//长度为temp的木棍数量+1
			p += temp;
			maxm = max(temp, maxm);
			minm = min(temp, minm);
		}
	}
	for (int i = maxm; i <= p / 2; i++)//小木棍木棍最长长度->总长度的一半
	{
		//木棍总长度也就是原始木棍长度一定能够整除单个木棍长度
		if(p%i==0)
		{ 
			ans = 0;
			dfs(i, 0, maxm);//期望长度=i,现在拼成长度=0,使用长度=maxm
		}
	}

	cout << p;//搜索不成功，全部拼成1根

}