本文共 1882 字，大约阅读时间需要 6 分钟。

        众所周知，搜索的算法时间复杂度大多是指数级的。即使是简单的不加优化的搜索，其时间效率也低得让人无法忍受，难以满足我们竞赛时对程序的运行时间的要求。所以建立算法结构之后，有一种对程序进行优化的基本方法——剪枝。

一、剪枝策略的寻找的方法

1）微观方法：从问题本身出发，发现剪枝条件。

2）宏观方法：从整体出发，发现剪枝条件。

3）注意提高效率，这是关键，最重要的。  

总之，剪枝策略，属于算法优化范畴；通常应用在DFS 和 BFS 搜索算法中；剪枝策略就是寻找过滤条件，提前减少不必要的搜索路径。

二、剪枝优化三原则

正确、准确、高效.原则  搜索算法,绝大部分需要用到剪枝.然而,不是所有的枝条都可以剪掉,这就需要通过设计出合理的判断方法,以决定某一分支的取舍. 在设计判断方法的时候,需要遵循一定的原则.

 1） 正确性  正如上文所述,枝条不是爱剪就能剪的. 如果随便剪枝,把带有最优解的那一分支也剪掉了的话,剪枝也就失去了意义. 所以,剪枝的前提是一定要保证不丢失正确的结果.  

2）准确性  在保证了正确性的基础上,我们应该根据具体问题具体分析,采用合适的判断手段,使不包含最优解的枝条尽可能多的被剪去,以达到程序“最优化”的目的. 可以说,剪枝的准确性,是衡量一个优化算法好坏的标准.

3）高效性 设计优化程序的根本目的,是要减少搜索的次数,使程序运行的时间减少. 但为了使搜索次数尽可能的减少,我们又必须花工夫设计出一个准确性较高的优化算法,而当算法的准确性升高,其判断的次数必定增多,从而又导致耗时的增多,这便引出了矛盾. 因此,如何在优化与效率之间寻找一个平衡点,使得程序的时间复杂度尽可能降低,同样是非常重要的. 倘若一个剪枝的判断效果非常好,但是它却需要耗费大量的时间来判断、比较,结果整个程序运行起来也跟没有优化过的没什么区别,这样就太得不偿失了.

三、深度优先搜索的优化技巧

1 优化搜索顺序：在一些搜索问题中，搜索树的各个层次，各个分支之间的顺序是不固定的。不同的搜索顺序会产生不同的搜索树形态，其规模大小也相差甚远。

2 排除等效冗余：在搜索过程中，如果我们能够判定从搜索树的当前节点上沿着某几条不同分支到达的子树是等效的，那么只需要对其中的一条分支执行搜索。

3 可行性剪枝（上下界剪枝）：该方法判断继续搜索能否得出答案，如果不能直接回溯。        在搜索过程中，即使对当前状态进行检查，如果发现分支已经无法到达递归边界，就执行回溯。

4 最优性剪枝：最优性剪枝，是一种重要的搜索剪枝策略。它记录当前得到的最优值，如果当前结点已经无法产生比当前最优解更优的解时，可以提前回溯。

5 记忆化：可以记录每个状态的搜索结果，再重复遍历一个状态时直接检索并返回。这好比我们对图进行深度优先遍历时，标记一个节点是否已经被访问过。

徐不可说：以下为一个上下界剪枝的一个例子！

数的划分

时间限制: 1 Sec  内存限制: 128 MB

题目描述

将整数n分成k份，且每份不能为空，任意两种划分方案不能相同(不考虑顺序)。

1 5 1

5 1 1

输入

n，k (6<n<=200，2<=k<=6)  

输出

一个整数，即不同的分法

样例输入

7 3

样例输出

4

徐不可说：本题就是要求把数字n无序划分为k份的方案数。 也就是x1+x2+……xk=n(x1<=x2……<=xk)的解数。搜索的方法是依次枚举x1,x2……xk的值，然后判断。 但是这样直接搜索，程序运行速度非常慢，以下是不进行剪枝的操作

#include
   
    using namespace std;int n,k,d[205][8];int main(){	scanf("%d%d",&n,&k);	d[0][0]=1;	for(int i=1;i<=n;i++)		for(int j=1;j<=i&&j<=k;j++)			d[i][j]=d[i-1][j-1]+d[i-j][j];		printf("%d\n",d[n][k]);		return 0;}
   

所以要控制好扩展结点的上界和下界，以下为进行剪枝的操作：

#include
   
    using namespace std;int dfs(int n,int k){	if(n==0||n
    
     >n>>k;	int x=dfs(n,k);	cout<
     
      <<"\n";	return 0;}
     
    
   

转载地址：http://natgn.baihongyu.com/