分支界限法

介绍

分支界限法（Branch and Bound）是一种在搜索问题中用于优化解空间搜索的算法。它可以在搜索过程中动态地生成子问题，通过一定的策略选择最具有潜力的子问题进行求解，并且可以快速排除那些不能优化目标的子问题，从而缩小搜索空间，提高求解效率。

通俗来讲，分支界限法就是在搜索问题时，通过先生成一个大问题，再把它分成许多小问题，然后一步一步地解决这些小问题，找到最优解。在这个过程中，我们还会根据当前的解空间来确定哪些问题没有必要再去尝试，从而加快搜索的速度。

总之，分支界限法是一种高效的搜索算法，可以在很多优化问题中发挥重要的作用。

示例求解

考虑如下 0 - 1背包问题

n = 4, w = [3, 5, 2, 1], v = [9, 10, 7, 4], c = 7

求解问题一定要明确自己再干什么，分支界限法实际上是一种剪枝的过程，而不是造树的过程，树已经造好了，做到心中有树，我们要把满二叉树尽可能的剪枝，然后求得最优解

如何剪枝？

  1. 如果生成不了最优解，那么舍弃，考虑把当前位置以及之后的全部物品全选，看看能不能超过当前最优解
  2. 如果放不下，那么舍弃
  3. 选择过程中直接更新最大值，而不是在每一层的选择完毕才更新，这样做能加速1的步骤

代码

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
37
38
39
40
41
42
43
44
45
46
47
48
49
import java.util.*;

public class BranchBound {
    static class State {
        int i, cv, rc;

        public State(int i, int cv, int rc) {
            this.i = i;
            this.cv = cv;
            this.rc = rc;
        }
    }

    public int knapsack(int n, int[] w, int[] v, int c) {
        int res = 0;
        // 前缀和，方便计算一整段的价值和
        int[] s = new int[n + 1];
        for (int i = 1; i <= n; i++) s[i] = s[i - 1] + v[i - 1];
        Queue<State> q = new LinkedList<>();
        q.offer(new State(0, 0, c));
        while (!q.isEmpty()) {
            State now = q.poll();
            // 本状态接下来要对下标为 i 的物品进行决策，决策前更新最大值，（注意，当前状态仍然是合理的）
            int i = now.i, cv = now.cv, rc = now.rc;
            // 如果要决策的下标越界了，说明当前已经把最后一层树决策完成了，退出
            if (i >= n) break;
            // 否则计算 不选 该物品之后的所有价值 和 选择 该物品之后的所有价值
            int rp0 = s[n] - s[i + 1], rp1 = s[n] - s[i];
            // 对于选的，体积不能超，上界要趋向最优
            if (rc >= w[i] && rp1 + cv > res) {
                q.offer(new State(i + 1, cv + v[i], rc - w[i]));
                res = Math.max(res, cv + v[i]);
            }
            // 对于不选的，只要求上界趋向最优
            if (rp0 + cv > res) {
                q.offer(new State(i + 1, cv, rc));
                res = Math.max(res, cv);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        BranchBound solve = new BranchBound();
        int[] w = {3, 5, 2, 1};
        int[] v = {9, 10, 7, 4};
        System.out.println(solve.knapsack(4, w, v, 7));
    }
}