浅谈深搜剪枝优化

文章目录

• 一、引入
• 二、深搜的剪枝
• 三、迭代加深
• 四、双向搜索
• 五、例题
• • 1.数的划分
  • 2.小木棍

一、引入

在《深搜与栈浅谈》中&＃xff0c;我曾提到过深搜一般效率很低&＃xff0c;因此需要优化。这里我给大家简单介绍一下深搜的常见剪枝方法、迭代加深思想以及双向搜索的思路。最后以几道比较经典的例题讲解一下实际题目中的优化。

二、深搜的剪枝

在深搜每次扩展中&＃xff0c;我们到达一个新的决策点B&＃xff0c;在访问完B及其所有子决策点后&＃xff0c;便回到其父决策点A。当决策点没有重复时&＃xff0c;所有的父子关系A->B便构成了一棵树。有重复时&＃xff0c;我们也一样把它看成一棵树。在遍历中&＃xff0c;如果发现沿着某一条路径无法到达目的时&＃xff0c;便可以提前退出。形象地可以把这种提前退出搜索的方法看成把树中的某一条树枝“剪掉”。选取合适的剪枝可以大大提高搜索效率。如果选用不正确的剪枝&＃xff0c;可能会导致错误。因此选用合理的剪枝十分重要。

像这样一棵搜索树&＃xff0c;在在到某个决策点时&＃xff0c;如果剪枝正确&＃xff0c;就会大大提升效率。

如果采用错误的剪枝&＃xff0c;就会出现下图情况&＃xff0c;找出错误答案或判断为无解。

1.优化搜索顺序
对于某些过程&＃xff0c;按照某些顺序能更方便快捷地解决问题。一般地可以将元素从小到大或从大到小排序&＃xff0c;再在每个循环中逐个枚举。
2.可行性剪枝
在某种状态&＃xff0c;可以通过数学的方法判断沿着这条路径是否能到达终点。如果不能&＃xff0c;那就直接退出。
3.上下界剪枝
再循环中&＃xff0c;如果发现到达某一个值之前或之后都是无解的&＃xff0c;就可以不枚举那些值。不难发现&＃xff0c;上下界剪枝是一种特殊的可行性剪枝。
4.排除等效冗余
有时后&＃xff0c;先解决A后解决B与先解决B后解决A是等效的&＃xff0c;这样便把一个过程重复执行了两遍&＃xff0c;因此可以在枚举到后者时直接跳过。一般地&＃xff0c;通过自行加一些限制&＃xff08;如限制从小到大取值&＃xff09;达到这个剪枝。
5.最优性剪枝
如果当前总代价已经超出了之前找到的最小代价&＃xff0c;直接退出。
一般要根据实际情况选择合适的剪枝&＃xff0c;下面1、2两道题是关于深搜剪枝的。

三、迭代加深

考虑下面这幅图的情况&＃xff1a;

其中蓝色结点表示当前路径&＃xff0c;红色表示终点。然而终点的深度非常小&＃xff0c;有的路径扩展出来的结点深度大&＃xff0c;这样就会影响效率。

但如果我们限制深度搜索&＃xff0c;&＃xff08;这里标蓝的点为访问终点前所有要访问的点&＃xff09;尽管每个深度都要搜一遍&＃xff0c;但在判断终点深度足够小的前提下&＃xff0c;可以避免一直往深度大且错误的路径寻找&＃xff0c;从而大大提高效率。

四、双向搜索

在起点和终点都确定的前提下&＃xff0c;可以采用双向搜素。
分别从起点和终点出发&＃xff0c;按照一定深度扩展出所有结点。当我们发现从起点扩展出来的结点与终点扩展出来的结点可以互相到达时&＃xff0c;便能够找到正确路径。

图中&＃xff0c;两个小圆分别表示起点和终点&＃xff0c;大圆表示分别扩展出来的结点的集合。其中中间重叠部分的结点可以相互到达&＃xff0c;这样便能找到正确路径&＃xff08;绿色那条&＃xff09;。而两个大圆之外的部分便不用枚举&＃xff08;即不用走类似上图的所有红色路径&＃xff09;&＃xff0c;这样就可以大大提升效率。

五、例题

1.数的划分

将整数n分成k份&＃xff0c;且每份不能为空&＃xff0c;任意两个方案不相同(不考虑顺序)。问有多少种不同的分法。

用dfs(rst,tot)表示把数rst分成tot所需方案数&＃xff0c;如果枚举i表示这次取出的数&＃xff0c;那么&＃xff0c;dfs可以由所有的dfs(rst-i,tot-1)得到。但这样效率不高&＃xff0c;我们考虑剪枝。
剪枝一&＃xff1a;&＃xff08;排除等效冗余&＃xff09;如果在rst中要取a和b两个数&＃xff08;a&＃43;b<&＃61;rst&＃xff09;&＃xff0c;那么先取那个数都是一样的&＃xff0c;因此要限制从小到大取数。记录lst表示上一次取的数。
剪枝二&＃xff1a;&＃xff08;上下界剪枝&＃xff09;如果当前取的数是i&＃xff0c;根据剪枝一&＃xff0c;后面取的数最小不能小于i&＃xff0c;即后面的数总和不小于itot。此时应有itot<&＃61;rst才能保证得出正确答案。
事实上&＃xff0c;这个过程中有重复的结点&＃xff0c;故还可以加上记忆化。

#include
#include
using namespace std;
int n,k;
int dfs(int rst,int tot,int lst){if(tot&＃61;&＃61;0&&rst&＃61;&＃61;0) return 1; //已经取了k个数且n被取完&＃xff0c;成功if(tot&＃61;&＃61;0&&rst!&＃61;0) return 0; //已经取了k个数但n未取完&＃xff0c;失败int ans&＃61;0;for(int i&＃61;lst;i*tot<&＃61;rst;i&＃43;&＃61;1){ //限制范围枚举ians&＃43;&＃61;dfs(rst-i,tot-1,i);}return ans;
}
int main(){scanf("%d%d",&n,&k);printf("%d\n",dfs(n,k,1)); //有时候求方案数要加上long longreturn 0;
}


2.小木棍

乔治拿来一组等长的木棒&＃xff0c;将它们随机的砍掉&＃xff0c;得到若干根小木棍&＃xff0c;并使每一节小棍的长度都不超过50个单位。然后他又想把这些木棍拼接起来&＃xff0c;恢复到裁剪前的状态&＃xff0c;但他忘记了初始时有多少木棒以及木棒的初始长度。请你设计一个程序&＃xff0c;帮助乔治计算木棒的可能最小长度&＃xff0c;每一节木棍的长度都用大于零的整数表示。

先枚举木棒长度&＃xff0c;再深搜判断是否可以取到。以vi[i]表示木棍i是否被用过&＃xff0c;dfs(now,tot)表示目前拼出长度为now的木棒且已经用了tot根木棍的方案数。如果下一个要拼上木棍编号为i&＃xff0c;则转化为求解dfsd(now&＃43;a[i],tot&＃43;1)&＃xff0c;同时标记vi[i]&＃61;1。当now&＃61;&＃61;len时&＃xff0c;令now&＃61;0即重新拼另一根木棒即可。
剪枝一&＃xff1a;&＃xff08;优化搜索顺序&＃xff09;将木棍从大到小排序。根据贪心先把用处小的长木棍先拼了。
剪枝二&＃xff1a;&＃xff08;排除等效冗余&＃xff09;当一根木棒拼法确定&＃xff0c;拼的顺序无所谓&＃xff0c;那么限制从大到小取木棍。
剪枝三&＃xff1a;&＃xff08;可行性剪枝&＃xff09;如果新木棒在第一轮中拼接失败&＃xff0c;也就是说当前剩下最长的木棍取不了&＃xff0c;这就意味着它永远取不到&＃xff0c;那么直接返回失败。
剪枝四&＃xff1a;&＃xff08;可行性剪枝&＃xff09;如果刚拼完一根木棒后&＃xff0c;搜索失败&＃xff0c;直接退出。那是因为在接下来如果找到另一种拼完当前木棒的方法&＃xff0c;那么长的木棒被保留了下来。既然在较短的木棒无法找到合适的拼法&＃xff0c;那么较长的木棒更找不到合适的拼法了。
剪枝五&＃xff1a;&＃xff08;排除等效冗余&＃xff09;如果下一步拼接长度为a[i]的木棒&＃xff0c;但最终结果是失败时&＃xff0c;直接跳过所有长度为a[i]的木棒。我们以数组v[i]记录当前情况中长度为i的木棒是否已被取过。

#include
#include
#include
using namespace std;
int n,m,a[66],vi[66];
bool cmp(int x,int y){return x>y;
}
int dfs(int now,int tot,int len,int lst){int v[51];for(int i&＃61;1;i<&＃61;n;i&＃43;&＃61;1) v[a[i]]&＃61;0;if(tot&＃61;&＃61;n) return 1;if(now&＃61;&＃61;len) now&＃61;0,lst&＃61;0;for(int i&＃61;lst&＃43;1/*剪枝二*/;i<&＃61;n;i&＃43;&＃61;1){if(vi[i]||v[a[i]]) continue; //剪枝五if(now&＃43;a[i]<&＃61;len){ //可以拼vi[i]&＃61;1;v[a[i]]&＃61;1;if(dfs(now&＃43;a[i],tot&＃43;1,len,i)) return 1;vi[i]&＃61;0;if(now&＃61;&＃61;0||len-now&＃61;&＃61;a[i]) break; //剪枝三、四}}return 0;
}
int main(){scanf("%d",&n);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃61;1){scanf("%d",&a[i]);m&＃43;&＃61;a[i];}sort(a&＃43;1,a&＃43;n&＃43;1,cmp); //剪枝一for(int i&＃61;1;i<&＃61;m;i&＃43;&＃61;1){if(m%i!&＃61;0) continue; //所有木棒总长度应该能被木棍长度整除if(dfs(0,0,i,0)){printf("%d\n",i); //第一个找到的便是最优解break;}}return 0;
}