深搜剪枝技巧
一、什么是剪枝
首先应当明确的是，“剪枝”的含义是什么。我们知道，搜索的进程可以看作是从树根出发，遍历一棵倒置的树——搜索树的过程。而所谓剪枝，顾名思义，就是通过某种判断，避免一些不必要的遍历过程，形象的说，就是坚强搜索树中的某些“枝条”，故称剪枝。
我们在编写搜索程序的时候，一般都要考虑剪枝。显而易见，应用剪枝优化的核心问题是设计剪枝判断方法，即确定哪些枝条应当舍弃，哪些枝条应当保留。设计好的剪枝判断方法，往往能够使程序的运行时间大大缩短；否则，可能适得其反。
二、剪枝的原则
1.正确性：
我们知道，剪枝方法之所以能够优化程序的执行效率，正如前文所述，是因为它能够“剪去”搜索树中的一些“枝条”。然而，如果在剪枝的时候，将“长有”我们所需要的解的枝条也剪掉了，那么，一切优化也就失去了意义。所以，对剪枝的第一个要求就是正确性，即必须保证不丢失正确的结果，这是剪枝优化的前提。
2.准确性：
在保证正确性的基础上 ，对剪枝判断的第二个要求就是准确性，即能够尽可能多地剪去不能通向正确的枝条。剪枝方法只有在具有了较高的准确性的时候，才能真正收到优化的效果。
3.高效性：
一般来说，设计好剪枝判断方法之后，我们对搜索树的每个枝条都要执行一次判断操作。然而，由于是利用出解的“必要条件”进行判断，所以，必然是有很多不含正解的枝条没有被剪枝。这些情况下的剪枝判断操作，对于程序的
效率提高无疑是具有副作用的。为了尽量减少剪枝判断的副作用，我们除了要下功夫改善判断的准确性之外，经常还需要提高判断操作本身的时间效率。
然而这就带来了一个矛盾：我们为了加强优化效果，就必须提高剪枝判断的准确性，因此，常常不得不提高判断操作的复杂度，也就同时降低了剪枝判断的时间效率；但是，如果剪枝判断的时间消耗过多，就有可能降低、甚至完全抵消
提高判断准确性所能带来的优化效果，这恐怕会得不偿失。很多情况下，能否较好地解决这个矛盾，往往成为搜索算法优化的关键。
综上所述:我们可以把剪枝优化的主要原则归结为六个字：正确、准确、高效。
三、深度优先搜索的优化技巧
1.优化搜索顺序
在一些搜索问题中，搜索树的各个层次、各个分支之间的顺序不是固定的。不同的搜索顺序会产生不同的搜索树形态，其规模大小也相差甚远。
2.排除等效冗余
在搜索过程中，如果我们能够判断从搜索树的当前节点上沿着某几条不同分支到达的子树是等效的，那么只需要对其中的一条分支执行搜索。
3.可行性剪枝
在搜索过程中，及时对当前状态进行检查，如果发现分支已经无法到达递归边界就及时回溯。这就好比我们在道路上行走时，远远看到前方是一个死胡同，就应该立即折返，走到路的尽头再返回。
某些题目条件的范围限制是一个区间，此时可行性剪枝也被称为上下界。
4.最优性剪枝
在最优化问题的搜索过程中，如果当前花费的代价已经超过当前搜到的最优解，那么取多么优秀的策略到达递归边接，都不可能更新答案，此时可以停止对当前分支的搜索回溯。
5.记忆化
可以记录每个状态的搜索结果，在重复遍历一个状态时直接搜索并返回。这好比我们进行深度优先遍历时，标记一个节点是否已经被访问过。
四、例题
【问题描述】
将整数n分成k份，且每份不能为空，问有多少种不同的分法？当n=7，k=3时，下面三种分法是被认为是相同的：1，1，5；
1，5，1；5，1，1。
【输入格式】
输入文件只有一行，为两个整数n和k。（6<n<=200， 2<=k<=6）
【输出格式】
输出文件仅有一行，为一个整数，即不同的分法数。
【样例输入】
7 3
【样例输出】
4
【样例解释】
四种分法为：1，1，5；1，2，4；1，3，3；2，2，3；
【数据规模】
对100%的数据，6<=n<=200, 2<=k<=6
【题目分析】
本题就是求把数字n无序划分为k份的方案数。也就是求方程x1+x2+...+xn=n; 的解数。
搜索的方法是依次枚举x1,x2... ...xn的值，然后判断。如果这样直接搜索，程序的运行速度是非常慢的。但是由于本题的数据规模比较小，如果控制
号扩展结点的“上界”和“下界"，也是能够快速得求出解的。
约束条件：
①由于分解数不考虑顺序，因此我们设定分解数依次递增，所以扩展结点时的”下界“应是不小于前一个扩展结点的值。即 a[i-1]<=a[i]
②假设我们将n已经分成了a[1]+a[2]+...+a[i-1],则a[i]的最大值为将i~k这 k-i+1份平均划分，即设m=n-(a[1]+a[2]+...+a[i-1]),
则a[i]<=m/(k-i+1)，所以扩展结点的”上界“是 m/ (k-i+1)。
(adsbygoogle = window.adsbygoogle || []).push({});