目录
什么是剪枝
几种常见的剪枝
1.可行性剪枝
2.排除等效冗余
3.最优性剪枝
4.顺序剪枝
5.记忆化
运用实例
1.选数
2.吃奶酪
3.小木棍
什么是剪枝
剪枝：通过某种判断，避免一些不必要的遍历过程。搜索的时间复杂度通常很大，通过剪枝对搜索进行优化，可以大大提高程序运行的效率。
几种常见的剪枝
1.可行性剪枝
判断继续搜索是否能得到答案，如果不能，就返回
即：不可行，就返回
2.排除等效冗余
在搜索的几个分支中具有完全相同的效果时，选择其中一个走即可
即：有相同，选一个
3.最优性剪枝
和可行性剪枝有点相似，区别在于继续搜索可能得到答案，但一定不是最优
首先得到最优解：每搜索到一个解，和之前的解做对比，得到最优解
然后最优性剪枝：如果当前搜索到的解已经超过最优解，就返回
即：非最优，就返回
4.顺序剪枝
优化搜索顺序，更快得到解
即：先排序，再搜索
5.记忆化
记录每个状态的搜索结果，在后续搜索过程中检索这个状态，如果重复，就返回
即：有重复，就返回
运用实例
1.选数
（详见洛谷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 { return; } if (count == k) { if(isprime(sum)) ans++; return;//可行性剪枝 } for(int i=start;i<=n;i++) { dfs(i + 1, count + 1, sum + a[i]); } } int main() { cin >> n >> k; for (int i = 1; i <= n; i++) { cin >> a[i]; } dfs(1,0,0); cout << ans; } 2.吃奶酪 （详见洛谷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 < } 只能得到50分 现在加上最优性剪枝： #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 < } 恭喜，看来这道题不用dp是通过不了了的，然而我还不会dp，等以后再来解决吧 3.小木棍 （详见洛谷P1120）：有一些同样长的木棍被随意砍成几段，求原始木棍的最小可能长度 输入：分段后的小木棍个数n，每个小木棍的长度 输出：最小可能的长度 运用：可行性剪枝，最优性剪枝，顺序剪枝 #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根 } 推荐阅读
发表评论