搜索的剪枝技巧之三个原则

上一篇中说到的剪枝的三个原则不是很详细，这篇在重新说一下。

原则一：正确性

我们知道，剪枝方法之所以能够优化程序的执行效率，正如上一篇说的，它能够“剪去”搜索树中的一些“枝条”。然而，倘若在剪枝时将有正确的答案的情况去掉了，那么我们做的优化也都是白费力气，可能还保龄！所以，我们在剪枝的时候一定要确保答案的正确性，如果答案是错的，还不如不剪枝。

原则二：准确性

如果答案正确了，那么，接下来就要考虑准确性了，我们要尽可能多地排除错误的答案（枝条），但是，要确保正确性！！！如果我们的剪枝准确性高，能准确地排除错误的方向，才能让剪枝达到尽量好的效果。

原则三：高效性

一般来说，涉及好剪枝判断方法后之后，我们对搜索树的每个枝条都要执行一次判断操作。然而，由于是利用解出的判断条件进行判断，所以，必然有很多错误解没有被舍去，在这样的情况下进行剪枝，结果往往会适得其反。所以，为了尽量减少剪枝判断的副作用，我们除了要下功夫改善判断的准确性外，经常还需要提高判断操作本身的时间复杂度。

然而这就带来了一个矛盾：我们为了加强优化的效果，就必须提高剪枝判断本身的准确性，因此，常常不得不提高判断操作的复杂度，也就同时降低了剪枝判断的时间效率；但是，如果剪枝判断的时间消耗过多，就有可能降低、甚至完全抵消提高判断准确性所带来的优化效果，这恐怕会得不偿失。很多情况下，能否较好地解决这个矛盾，成为了搜索优化算法的关键。

所以，我们在做剪枝优化的时候一定要注意：正确、准确、高效

做道题目：

LOJ #10018. 「一本通 1.3 例 1」数的划分

一本通题库 1440

洛谷 P1025 [NOIP2001 提高组] 数的划分

题面：

题目描述

将整数 $n$ 分成 $k$ 份，且每份不能为空，任意两个方案不相同（不考虑顺序）。

例如： $n = 7$ ， $k = 3$ ，下面三种分法被认为是相同的。

$1, 1, 5$ ;
$1, 5, 1$ ;
$5, 1, 1$ .

问有多少种不同的分法。

输入格式

$n, k$ （ $\le 200$ ， $\le k \le 6$ ）

输出格式

$1$ 个整数，即不同的分法。

样例 #1

样例输入 #1

7 3

样例输出 #1

提示

四种分法为：
$1, 1, 5$ ;
$1, 2, 4$ ;
$1, 3, 3$ ;
$2, 2, 3$ .

【题目来源】

NOIP 2001 提高组第二题

题目解法：

为了确保出现过的方案不重复，可以规定在后面的分组中的数必须要大于前面分组中的数， $n o w$ 代表上一个出现过的数，初值为 $1$ ，只要让下一个数从 $n o w$ 开始循环，便可达成上述方案。

$p a r t$ 代表还需多少次递归，即要分成几份，初值为 $k$ ，递归 $k$ 次，即分为 $k$ 份后便可退出循环。

$n u m$ 代表到此次还剩多大的数可以分，初值定为 $n$ 。

同时循环最大只能进行到 $\large\frac{t}{s}$ ，避免出现因前面的数过大而导致后面的数无法取的情况，其实这就是剪枝的方法。

下面就放代码了：

#include<bits/stdc++.h>

using namespace std;

int n,k;

int dfs(int num,int part,int now)//剩余待分的数，分的个数，要选出的数
{
    if(part==1) return 1;
    int cnt=0;
    for (int i=now;i<=num/part;i++) cnt+=dfs(num-i,part-1,i);
    return cnt;
}

int main()
{
    scanf("%d%d",&n,&k);
    printf("%d",dfs(n,k,1));
    return 0;
}