跳至主要內容

3.8 分支限界算法

分支限界算法（Branch and Bound Algorithm）是一种用于求解组合优化问题的精确算法。它通过系统地搜索问题的解空间，并使用剪枝策略以避免搜索无效的解，从而在有限时间内找到最优解或满足特定条件的解。

分支限界算法通常用于解决以下类型的问题：

  1. 组合优化问题：如旅行商问题（TSP）、背包问题、作业调度等。

  2. 最优化问题：求解线性规划、整数规划等。

算法的基本思想是将问题空间分解为一个树形结构，每个节点表示对问题的一个局部解或子问题的状态。算法通过在问题空间中搜索并逐步扩展解的候选集合，同时使用一些启发式方法来评估候选解的潜在价值，并通过剪枝策略去除无效的候选解，从而减少搜索空间。

分支限界算法的主要步骤包括：

  1. 初始化：构建初始节点表示问题的初始状态。

  2. 搜索：使用深度优先搜索、广度优先搜索或优先级队列等搜索策略遍历问题空间，并生成子问题。

  3. 剪枝：对于生成的每个子问题，使用上界和下界等方法对其进行评估，从而决定是否保留该子问题。

  4. 回溯：在搜索过程中，如果无法继续扩展当前节点，则回溯到上一个节点，继续搜索其他分支。

  5. 终止条件：当找到最优解或满足特定条件时，终止搜索。

通过不断地搜索、剪枝和回溯，分支限界算法可以在有限时间内找到最优解或者接近最优解。与贪婪算法不同，分支限界算法能够保证找到最优解，但是其复杂度通常比贪婪算法高，特别是对于大规模问题。

0-1背包问题

0-1背包问题是一个经典的组合优化问题，也是计算机科学中常见的问题之一。在这个问题中，给定一个固定容量的背包，以及一组物品，每个物品有自己的重量和价值。要求在不超过背包容量的前提下，选择一些物品放入背包中，使得放入背包的物品的总价值最大。

具体来说，0-1背包问题有以下特点：

  1. 每个物品只能选择放入一次（0-1性质）。
  2. 背包有一个固定的容量限制。
  3. 每个物品有自己的重量和价值，要求在放入背包时尽可能增加总价值，而不超过背包的容量限制。

这个问题可以形式化地描述为：给定一个整数容量 C，一组物品，其中每个物品 i 有一个重量 w[i] 和一个价值 v[i]，找到一个解决方案 S，使得 S 中的物品总重量不超过 C，且 S 中物品的总价值最大。

0-1背包问题是一个NP-完全问题，意味着在一般情况下，没有已知的多项式时间算法可以解决它。下面是一个使用分支限界算法解决 0-1 背包问题的 Java 代码示例：

import java.util.Arrays;

public class BranchAndBound {

    static class Item implements Comparable<Item> {
        int weight;
        int value;
        double ratio;

        public Item(int weight, int value) {
            this.weight = weight;
            this.value = value;
            this.ratio = (double) value / weight;
        }

        @Override
        public int compareTo(Item other) {
            return Double.compare(other.ratio, this.ratio);
        }
    }

    public static int knapsack(int capacity, int[] weights, int[] values) {
        int n = weights.length;
        Item[] items = new Item[n];
        for (int i = 0; i < n; i++) {
            items[i] = new Item(weights[i], values[i]);
        }
        Arrays.sort(items);

        return knapsackHelper(capacity, items, 0, 0, 0);
    }

    private static int knapsackHelper(int capacity, Item[] items, int index, int currentWeight, int currentValue) {
        if (index >= items.length || currentWeight >= capacity) {
            return currentValue;
        }

        // 判断剩余物品的总价值是否有可能超过当前最优解
        int remainingValue = 0;
        int remainingWeight = capacity - currentWeight;
        for (int i = index; i < items.length; i++) {
            if (items[i].weight <= remainingWeight) {
                remainingValue += items[i].value;
                remainingWeight -= items[i].weight;
            } else {
                remainingValue += (int) (remainingWeight * items[i].ratio);
                break;
            }
        }

        // 如果剩余总价值不可能超过当前最优解，就不再继续扩展该节点
        if (currentValue + remainingValue <= currentValue) {
            return currentValue;
        }

        // 尝试选择当前物品
        int valueWithItem = knapsackHelper(capacity, items, index + 1, currentWeight + items[index].weight,
                currentValue + items[index].value);

        // 尝试不选择当前物品
        int valueWithoutItem = knapsackHelper(capacity, items, index + 1, currentWeight, currentValue);

        // 返回选择当前物品和不选择当前物品中的最大值
        return Math.max(valueWithItem, valueWithoutItem);
    }

    public static void main(String[] args) {
        int[] weights = {10, 20, 30};
        int[] values = {60, 100, 120};
        int capacity = 50;
        int maxValue = knapsack(capacity, weights, values);
        System.out.println("Maximum value that can be obtained: " + maxValue);
    }
}

在这个示例中，我们使用分支限界算法来解决 0-1 背包问题。在 knapsack 方法中，我们首先将物品按照单位重量价值（价值/重量）降序排列，然后调用 knapsackHelper 方法来递归搜索解空间。在 knapsackHelper 方法中，我们根据剩余物品的总价值和当前最优解的情况，判断是否需要继续扩展当前节点。最后，我们比较选择当前物品和不选择当前物品两种情况下的价值，返回较大值作为当前节点的最优解。

上次编辑于: