搜索（一）——剪枝
参考文档：《搜索方法中的剪枝优化》——南开中学 齐鑫（见附件《剪枝》）
?
?
一、剪枝优化的核心问题是设计剪枝判断方法，即确定哪些枝条应当舍弃，哪些枝条应当保留的方法。
?
二、剪枝的原则：
1. 正确性：
即必须保证不丢失正确的结果，这是剪枝优化的前提。
为了满足这个原则，我们就应当利用“必要条件”来进行剪枝判断。也就是说，通过解所必须具备的特征、必须满足的条件等方面来考察待判断的枝条能否被剪枝。这样，就可以保证所剪掉的枝条一定不是正解所在的枝条。当然，由必要条件的定义，我们知道，没有被剪枝不意味着一定可以得到正解（否则，也就不必搜索了）。
?
2. 准确性：尽多剪枝
即能够尽可能多的剪去不能通向正解的枝条。
?
3. 高效性：权衡“剪枝判断开销”和“剪枝提速效果”
剪枝判断的副作用及其改善：[一般说来，设计好剪枝判断方法之后，我们对搜索树的每个枝条都要执行一次判断操作。然而，由于是利用出解的“必要条件”进行判断，所以，必然有很多不含正解的枝条没有被剪枝。这些情况下的剪枝判断操作，对于程序的效率的提高无疑是具有副作用的。为了尽量减少剪枝判断的副作用，我们除了要下功夫改善判断的准确性外，经常还需要提高判断操作本身的时间效率。]
然而这就带来了一个矛盾：我们为了加强优化的效果，就必须提高剪枝判断的准确性，因此，常常不得不提高判断操作的复杂度，也就同时降低了剪枝判断的时间效率；但是，如果剪枝判断的时间消耗过多，就有可能减小、甚至完全抵消提高判断准确性所能带来的优化效果，这恐怕也是得不偿失。很多情况下，能否较好的解决这个矛盾，往往成为搜索算法优化的关键。
?
三、可行性剪枝
在很多情况下，并不是搜索树中的所有枝条都能通向我们需要的结果，很多的枝条实际上只是一些死胡同。如果我们能够在刚刚进入这样的死胡同的时候，就能够判断出来并立即剪枝
?
四、最优性剪枝/上下界剪枝
在我们平时遇到的问题中，有一大类是所谓最优化问题，即所要求的结果是最优解。如果我们使用搜索方法来解决这类问题，那么，最优性剪枝是一定要考虑到的。
为了表述的统一，首先要作一些说明：我们知道，解的优劣一般是通过一个评价函数来评判的。这里定义一个抽象的评价函数——“优度”，它的值越大，对应的解也就越优（对于具体的问题，我们可以认为“优度”代表正的收益或负的代价等）。
然后，我们再来回顾一下搜索最优解的过程：一般情况下，我们需要保存一个“当前最优解”，实际上就是保存解的优度的一个下界。在遍历到搜索树的叶子节点的时候，我们就能得到一个新的解，当然也就得到了它的评价函数值，与保存的优度的下界作比较，如果新解的优度值更大，则这个优度值就成为新的下界。搜索结束后，所保存的解就是最优解。
那么，最优性剪枝又是如何进行的呢？当我们处在搜索树的枝条上时，可以通过某种方法估算出该枝条上的所有解的评价函数的上界，即所谓估价函数 。显然， 大于当前保存的优度的下界，是该枝条上存在最优解的必要条件，否则就一定可以剪枝。所以，最优性剪枝也可以称为“上下界剪枝”。同时，我们也可以看到，最优性剪枝的核心问题就是估价函数的建立。
?
例题：
?
1. POJ 2331 Water Pipe==> IDA* +剪枝
??? 语法注意：一般在使用memset()时，都不要将memset()放到子程序中初始化一个指针参数对应数组，直接在外面memset()就好了。避免出错! 参见“分类C/C++” ==> “指针常量，指针变量（sizeof使用注意）”
?
# include <cstdio># include <cstring># include <queue>using namespace std;int x1,y1,x2,y2;int k;int l[5];int c[5];int cmin;//(A*启发函数) h[i][j]是在假设有无限多每种型号的管道时，从(i,j)到目的点(x2,y2)至少还需要多少根管道int hx[1001];int hy[1001];void bfs(int *h, int endPos){queue<int> q;h[endPos]=0;q.push(endPos);int curPos;while(!q.empty()){curPos=q.front();q.pop();int i;//假设每种型号的管道取之不尽for(i=0;i<k;i++){if(curPos-l[i]>=1 && h[curPos-l[i]]==-1){h[curPos-l[i]]=h[curPos]+1;q.push(curPos-l[i]);}if(curPos+l[i]<=1000 && h[curPos+l[i]]==-1){h[curPos+l[i]]=h[curPos]+1;q.push(curPos+l[i]);}}}}bool dfs(int cur, int depth, int type){if(type==0){//剪枝if(depth+hx[cur]>cmin || hx[cur]==-1)return false;//x深搜到值后，继续深搜yif(cur==x2){return dfs(y1,depth,1); //注意：不是dfs_y(y1,depth+1)}int i;for(i=0;i<k;i++){if(c[i]==0) continue;if(cur<x2){if(cur+l[i]<=1000){ // 不要反复检查: && hx[curX+l[i]]!=-1){c[i]--;if(dfs(cur+l[i],depth+1,0))return true;c[i]++;}if(cur-l[i]>=1){c[i]--;if(dfs(cur-l[i],depth+1,0))return true;c[i]++;}}else{if(cur-l[i]>=1){c[i]--;if(dfs(cur-l[i],depth+1,0))return true;c[i]++;}if(cur+l[i]<=1000){c[i]--;if(dfs(cur+l[i],depth+1,0))return true;c[i]++;}}}}else{//剪枝if(depth+hy[cur]>cmin || hy[cur]==-1)return false;//y深搜到值if(cur==y2){return true;}int i;for(i=0;i<k;i++){if(c[i]==0) continue;//根据大致方向优先向某个方向扩展if(cur<y2){if(cur+l[i]<=1000){c[i]--;if(dfs(cur+l[i],depth+1,1))return true;c[i]++;}if(cur-l[i]>=1){c[i]--;if(dfs(cur-l[i],depth+1,1))return true;c[i]++;}}else{if(cur-l[i]>=1){c[i]--;if(dfs(cur-l[i],depth+1,1))return true;c[i]++;}if(cur+l[i]<=1000){c[i]--;if(dfs(cur+l[i],depth+1,1))return true;c[i]++;}}}}return false;}int main(void){scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&k);int i,depth_max=0;for(i=0;i<k;i++)scanf("%d",&l[i]);for(i=0;i<k;i++){scanf("%d",&c[i]);depth_max+=c[i];}//计算A*启发函数memset(hx,-1,sizeof(hx));memset(hy,-1,sizeof(hy));bfs(hx,x2);bfs(hy,y2);//迭代加深DFSfor(cmin=0;cmin<=depth_max;cmin++){//保证cmin在循环内部不被修改if(dfs(x1,0,0)) break;}if(cmin<=depth_max)printf("%d",cmin);elseprintf("%d",-1);return 0;}??
?
?
?