剪枝优化

定义

剪枝，是一种减少搜索树规模、尽早排除搜索树中不必要分支的方法。

理解

搜索是对一个问题不断地寻找可行方案，从初始状态开始，经过一系列状态转移，寻找目标状态或者最优状态。这是一种「通用解题方法」，但是大部分情况下搜索所需的时间复杂度都很高。

一般的深度优先搜索问题都要用到回溯思想，每次不能遍历下去时，回溯到上一个点，继续遍历，整个搜索过程可以抽象成一个「搜索树」。为了降低时间复杂度，需要优化搜索过程，尽可能减少生成的状态数，尽早排除不可能得到最优解的分支。形象地说，类似剪掉了搜索树的枝条，因此称为「剪枝」。

剪枝方法

优化搜索顺序

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

排除等效冗余

在搜索过程中，如果我们能够判定从搜索树的当前状态沿着几条不同分支展开搜索，后续的搜索过程都是等效的，那么就只需要对其中的一条分支执行搜索，避免重复搜索同一状态空间。

可行性剪枝

在搜索过程中，及时对当前状态进行检查，如果发现分支已经无法到达目标状态，就执行回溯，不再执行后续搜索。

最优性剪枝

对于最优化问题的搜索，如果当前的结果已经比当前搜索到的最优解更差，那么后续一定不会得到更优的答案，可以直接停止对当前分支的搜索。

具体应用

数的划分

给定一个正整数 n，将其分成 k 个正整数，使得这些正整数的和恰好是 n。
任意两个方案不能相同（不考虑顺序），例如：n = 7，k = 3，下面三种分法被认为是相同的：1, 1, 5; 1, 5, 1; 5, 1, 1。
问有多少种不同的分法。

问题的初始状态是有 0 个正整数并且总和为 0，目标状态是有 k 个正整数并且和为 n。目标状态可能有多个，目标状态的数量即为答案。
考虑一个一个增加正整数，每个步骤就是增加一个正整数 x，并且总和增加 x。

考虑剪枝方法：

  1. 优化搜索顺序
    为了避免出现重复的方案，考虑从小到大枚举每个步骤增加的正整数。换句话说，如果当前步骤增加了正整数 x，之后的步骤只能增加大于等于 x 的正整数，从而保证最终方案中的 k 个正整数是从小到大排列的。
  2. 可行性剪枝
    如果第 i 个步骤增加了正整数 x，按照第一种剪枝方法的约定，之后的步骤只能增加大于等于 x 的正整数。假设后续增加的正整数都是 x，并且这种方案最终的总和超过了 n，那么说明当前步骤增加正整数 x 一定会导致最终的总和超过 n，这种方案是不可行的，可以直接剪枝。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int n, k;
int ans = 0; // 记录最终答案

// 当前已经选定了 step 个正整数，正在选择第 step + 1 个正整数
// 已经选定的正整数的总和是 sum
// 上一个选定的正整数是 lst
void dfs(int step, int sum, int lst){
    if(step >= k){ // 如果已经选定的正整数个数大于等于 k 个，说明找到一种方案
        if(sum == n){ // 如果总和恰好是 sum，说明找到一种合理的方案
            ans++;
        }
        return;
    }
    // 优化搜索顺序，当前可选择的正整数范围是 [lst, n]
    for(int i = lst; i <= n; i++){
        // 可行性剪枝，如果当前选择正整数 i，最终总和一定会超过 n，则直接剪枝
        // 并且当前同样不可能选择大于 i 的正整数，也可以一并剪枝
        if(sum + i * (k - step) > n) break;
        
        // 继续执行后续搜索
        dfs(step + 1, sum + i, i);
    }
}

dfs(0, 0, 1);

子集划分

给出一个整数数组 a1,a2,...,ana_1, a_2, ... , a_n 和一个正整数 k，判断是否有可能将这个数组分成 k 个非空子集，使得每个子集中元素的和都相等。

问题可以转化成，将 n 个数放入 k 个桶中，使得每个桶中数的总和相同。由于整数数组 a 是固定的，可以计算出数组中所有数的总和 sum，则每个桶中数的总和即为 tgt = sum / k 。
转换后问题的初始状态是 k 个桶都为空，目标状态是 k 个桶中每个桶都放入了若干个数，并且每个桶中数的总和为 tgt。
考虑将整数数组 a 中的数一个一个放入对应的桶，每个步骤就是将数组 a 中一个数放入某一个桶。

考虑剪枝方法：

  1. 可行性剪枝
    如果数组中第 i 个数放入第 j 个桶后，对应桶中数的总和超过 tgt，那么这种方案是不可行的，可以直接剪枝。
  2. 等效性剪枝
    当数组中第 i 个数尝试放入第 j 个桶时，如果放入前第 j 个桶和前一个桶中数的总和相同，由于桶是没有顺序的，因此第 i 个数放入第 j 个桶，效果和放入前一个桶完全一致，即等效的，不用重复搜索，可以直接剪枝。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int n, k;
vector<int> a(n); // 整数数组

int tgt; // 每个子集中数的总和
vector<int> bucket(k); // 记录每个子集中数的总和

// 当前正在尝试将数组 a 中第 cur 个数放入某个子集
bool dfs(int cur){
    // 从 a[0] 到 a[n - 1] 的 n 个数都已经放入对应子集，说明找到一种合理的方案
    if(cur >= n) return true;

    // 尝试将数组 a 中第 cur 个数放入第 i 个子集
    for(int i = 0; i < k; i++){
        // 等效性剪枝，如果放入前第 i 个子集和前一个子集中数的总和相同，无需重复搜索
        if(i > 0 && bucket[i] == bucket[i - 1]) continue;

        // 可行性剪枝，如果放入后当前桶中数的总和超过 tgt，直接剪枝
        if(bucket[i] + a[cur] <= tgt){
            bucket[i] += a[cur]; // 将 a[cur] 放入第 i 个子集
            if(dfs(cur + 1)) return true;
            bucket[i] -= a[cur]; // 还原现场，从第 i 个子集中拿出 a[cur]
        }
    }

    // 尝试将数组 a 中第 cur 个数放入 k 个子集中都失败，则搜索失败
    return false;
}


if(sum % k != 0){
    cout << "no" << endl;
}

tgt = sum / k;
if(dfs(0)) cout << "yes" << endl;
else cout << "no" << endl;