每日算法 — 使用java实现分支限界法：组合优化问题的系统搜索与剪枝策略

算法概述

分支限界法（Branch and Bound）是求解组合优化问题的经典算法框架，由Ailsa Land和Alison Doig于1960年提出。与回溯法盲目搜索所有可能解不同，分支限界法通过维护当前最优解的上界（或下界），在搜索过程中主动剪除不可能产生更优解的分支，从而将指数级的时间复杂度在平均意义上大幅降低。该算法广泛应用于旅行商问题（TSP）、背包问题、作业调度问题等NP-hard组合优化场景。

核心思想

分支限界法包含三个关键机制：

1. 分支（Branch）：将问题的解空间划分为若干子空间，系统地枚举所有可能。

2. 限界（Bound）：为每个子空间计算一个边界值（上界或下界），判断该子空间是否可能包含更优解。

3. 剪枝（Prune）：若某子空间的边界值不优于当前最优解，则直接丢弃该分支，不再深入搜索。

对于最小化问题，维护当前最优解best，若某节点的下界lowerBound ≥ best，则剪枝；对于最大化问题则相反。

算法框架：以0-1背包问题为例

0-1背包问题是分支限界法的经典应用场景。给定n个物品，每个物品有重量weight[i]和价值value[i]，在背包容量为W的条件下，选择物品使总价值最大。

限界函数设计

按单位重量价值贪心排序后，对于当前节点，假设已选物品总价值为cv、已用容量为cw，剩余物品按贪心策略能装入的部分价值为bound：
– bound = cv + 剩余容量中能装下的最高单位重量价值物品的价值

若bound ≤ 当前最优值，则剪枝。

Java实现

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * 分支限界法求解0-1背包问题
 * 使用优先队列（最佳优先搜索）实现
 */
public class BranchAndBoundKnapsack {

    /**
     * 物品类，包含重量、价值和单位重量价值
     */
    static class Item implements Comparable<Item> {
        int weight;
        int value;
        double unitValue;
        int index;

        Item(int weight, int value, int index) {
            this.weight = weight;
            this.value = value;
            this.unitValue = (double) value / weight;
            this.index = index;
        }

        @Override
        public int compareTo(Item other) {
            // 按单位重量价值降序排列
            return Double.compare(other.unitValue, this.unitValue);
        }
    }

    /**
     * 搜索节点
     */
    static class Node implements Comparable<Node> {
        int level;          // 当前考虑的物品层级
        int currentValue;   // 当前已选物品总价值
        int currentWeight;  // 当前已选物品总重量
        double bound;       // 上界估计
        boolean[] taken;    // 物品选取状态

        Node(int level, int currentValue, int currentWeight, 
             double bound, boolean[] taken) {
            this.level = level;
            this.currentValue = currentValue;
            this.currentWeight = currentWeight;
            this.bound = bound;
            this.taken = taken.clone();
        }

        @Override
        public int compareTo(Node other) {
            // 按上界降序排列（优先扩展上界大的节点）
            return Double.compare(other.bound, this.bound);
        }
    }

    private Item[] items;
    private int capacity;
    private int n;
    private int bestValue;
    private boolean[] bestSolution;

    public BranchAndBoundKnapsack(int[] weights, int[] values, int capacity) {
        this.n = weights.length;
        this.capacity = capacity;
        this.items = new Item[n];
        for (int i = 0; i < n; i++) {
            items[i] = new Item(weights[i], values[i], i);
        }
        // 按单位重量价值降序排序
        Arrays.sort(items);
        this.bestValue = 0;
        this.bestSolution = new boolean[n];
    }

    /**
     * 计算上界：假设剩余物品可以按分数装包
     */
    private double calculateBound(Node node) {
        if (node.currentWeight >= capacity) {
            return 0;
        }

        double bound = node.currentValue;
        int remainingWeight = capacity - node.currentWeight;

        // 按贪心策略计算剩余价值上界
        for (int i = node.level; i < n && remainingWeight > 0; i++) {
            if (items[i].weight <= remainingWeight) {
                bound += items[i].value;
                remainingWeight -= items[i].weight;
            } else {
                // 分数装包，获取上界
                bound += items[i].unitValue * remainingWeight;
                remainingWeight = 0;
            }
        }

        return bound;
    }

    /**
     * 使用优先队列实现最佳优先的分支限界搜索
     */
    public int solve() {
        PriorityQueue<Node> pq = new PriorityQueue<>();

        // 根节点：尚未考虑任何物品
        boolean[] rootTaken = new boolean[n];
        Node root = new Node(0, 0, 0, 
            calculateBound(new Node(0, 0, 0, 0, rootTaken)), rootTaken);
        pq.offer(root);

        while (!pq.isEmpty()) {
            Node current = pq.poll();

            // 剪枝：如果上界不大于当前最优值
            if (current.bound <= bestValue) {
                continue;
            }

            // 到达叶子节点
            if (current.level == n) {
                if (current.currentValue > bestValue) {
                    bestValue = current.currentValue;
                    bestSolution = current.taken.clone();
                }
                continue;
            }

            // 分支1：选择当前物品
            if (current.currentWeight + items[current.level].weight <= capacity) {
                boolean[] takeTaken = current.taken.clone();
                takeTaken[current.level] = true;
                Node takeNode = new Node(
                    current.level + 1,
                    current.currentValue + items[current.level].value,
                    current.currentWeight + items[current.level].weight,
                    0, takeTaken
                );
                takeNode.bound = calculateBound(takeNode);
                if (takeNode.bound > bestValue) {
                    pq.offer(takeNode);
                }
            }

            // 分支2：不选当前物品
            boolean[] skipTaken = current.taken.clone();
            Node skipNode = new Node(
                current.level + 1,
                current.currentValue,
                current.currentWeight,
                0, skipTaken
            );
            skipNode.bound = calculateBound(skipNode);
            if (skipNode.bound > bestValue) {
                pq.offer(skipNode);
            }
        }

        return bestValue;
    }

    /**
     * 获取最优解的物品选取状态
     */
    public boolean[] getBestSolution() {
        return bestSolution;
    }

    /**
     * 打印最优解详情
     */
    public void printSolution() {
        System.out.println("最优总价值: " + bestValue);
        System.out.println("选取的物品（按排序后索引）:");
        int totalWeight = 0;
        for (int i = 0; i < n; i++) {
            if (bestSolution[i]) {
                System.out.printf("  物品%d: 重量=%d, 价值=%d%n", 
                    items[i].index, items[i].weight, items[i].value);
                totalWeight += items[i].weight;
            }
        }
        System.out.println("总重量: " + totalWeight + " / 容量: " + capacity);
    }

    public static void main(String[] args) {
        // 测试用例
        int[] weights = {2, 3, 4, 5, 9};
        int[] values = {3, 4, 5, 8, 10};
        int capacity = 20;

        BranchAndBoundKnapsack solver = new BranchAndBoundKnapsack(weights, values, capacity);
        int maxValue = solver.solve();

        System.out.println("分支限界法求解0-1背包问题");
        System.out.println("=========================");
        solver.printSolution();

        // 验证：与动态规划结果对比
        int dpResult = knapsackDP(weights, values, capacity);
        System.out.println("动态规划验证结果: " + dpResult);
        System.out.println("结果一致: " + (maxValue == dpResult));
    }

    /**
     * 动态规划验证（O(n*W)）
     */
    private static int knapsackDP(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        int[] dp = new int[capacity + 1];
        for (int i = 0; i < n; i++) {
            for (int w = capacity; w >= weights[i]; w--) {
                dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
            }
        }
        return dp[capacity];
    }
}

分支限界法的两种搜索策略

本文实现的是优先队列策略（最佳优先搜索），在平均情况下能更快找到较优解，从而提升剪枝效率。

复杂度分析

最坏情况下，分支限界法仍需遍历2^n个节点，时间复杂度为O(2^n)。但在实际应用中，优秀的限界函数可以使剪枝率在90%以上。限界函数越精确，剪枝越早，实际运行时间越接近多项式级别。

应用场景

分支限界法广泛应用于运筹学和工业优化领域：
– 旅行商问题（TSP）：使用最小生成树或指派问题的解作为下界
– 作业调度问题：最小化总完成时间或最大延迟
– 整数线性规划：在单纯形法基础上进行分支
– 图着色问题：寻找最少颜色数
– 电路板布线：寻找最短连接路径

掌握分支限界法的核心在于针对具体问题设计高效的限界函数，这是决定算法性能的关键。