分支限界法
算法定义
分支限界法（Branch and Bound Paradigm）是一种求解组合优化问题的有效算法。它通过不断分支（将问题分解为子问题）和限界（计算下界或上界以剪去不可能包含最优解的子问题）来高效搜索最优解。与回溯法不同，分支限界法通常采用广度优先或最佳优先策略搜索解空间，适合求解最大化或最小化问题。
算法思路
- 定义问题的解空间和目标函数
- 确定界函数（上界或下界），用于评估部分解的优劣
- 采用队列（FIFO）、优先队列（最佳优先）等数据结构管理活节点
- 从初始节点开始，不断分支生成子节点
- 计算每个子节点的界，剪去界不可能优于当前最优解的子节点
- 直到找到最优解或所有可能的节点都被处理
分支限界法的核心是通过限界函数有效剪枝，减少搜索空间。
算法复杂度
- 时间复杂度：
- 最好情况：O (n)，在早期就找到最优解并剪去所有其他分支
- 最坏情况：O (2ⁿ) 或 O (n!)，取决于问题的解空间大小和解的分布
- 平均情况：受限界函数效果影响较大，通常优于穷举法
- 空间复杂度：
- 通常为 O (2ⁿ)，需要存储大量活节点，具体取决于问题规模和搜索策略
优点和缺点
- 优点：
- 相比回溯法更适合求解优化问题
- 通过限界函数能有效剪去无效分支，提高搜索效率
- 可以找到全局最优解
- 适合并行计算
- 缺点：
- 空间复杂度较高，需要存储大量活节点
- 界函数设计困难，直接影响算法效率
- 对于大规模问题仍然可能效率低下
应用场景
- 旅行商问题（TSP）
- 0-1 背包问题
- 整数规划问题
- 图的最短路径问题
- 最大团问题
- 电路板排列问题
- 任务分配问题
Java 代码实现
下面以经典的 "0-1 背包问题" 和 "旅行商问题（TSP）" 为例，展示分支限界法的几种实现方式：
import java.util.*;
public class BranchAndBoundExamples {
// 1. 0-1背包问题：队列式分支限界法（FIFO）
static class KnapsackNode {
int level; // 当前处理的物品索引
int profit; // 当前利润
int weight; // 当前重量
double bound; // 界值（可能的最大利润）
KnapsackNode(int level, int profit, int weight) {
this.level = level;
this.profit = profit;
this.weight = weight;
}
}
public static int knapsackFIFO(int[] weights, int[] profits, int capacity) {
int n = weights.length;
// 按单位重量利润排序
sortByProfitDensity(weights, profits);
Queue<KnapsackNode> queue = new LinkedList<>();
// 初始节点
KnapsackNode root = new KnapsackNode(-1, 0, 0);
queue.add(root);
int maxProfit = 0;
while (!queue.isEmpty()) {
KnapsackNode current = queue.poll();
// 如果是叶子节点，跳过
if (current.level == n - 1) {
continue;
}
// 下一个物品索引
int nextLevel = current.level + 1;
// 考虑放入下一个物品
int newWeight = current.weight + weights[nextLevel];
int newProfit = current.profit + profits[nextLevel];
// 如果放入后不超重，更新最大利润
if (newWeight <= capacity && newProfit > maxProfit) {
maxProfit = newProfit;
}
// 计算放入下一个物品后的界值
double bound = calculateBound(newWeight, newProfit, nextLevel, weights, profits, capacity);
// 如果界值大于当前最大利润，则加入队列
if (bound > maxProfit) {
queue.add(new KnapsackNode(nextLevel, newProfit, newWeight));
}
// 考虑不放入下一个物品
bound = calculateBound(current.weight, current.profit, nextLevel, weights, profits, capacity);
if (bound > maxProfit) {
queue.add(new KnapsackNode(nextLevel, current.profit, current.weight));
}
}
return maxProfit;
}
// 2. 0-1背包问题：优先队列式分支限界法（最佳优先）
public static int knapsackBestFirst(int[] weights, int[] profits, int capacity) {
int n = weights.length;
// 按单位重量利润排序
sortByProfitDensity(weights, profits);
// 使用优先队列，按界值降序排列
PriorityQueue<KnapsackNode> pq = new PriorityQueue<>((a, b) -> Double.compare(b.bound, a.bound));
// 初始节点
KnapsackNode root = new KnapsackNode(-1, 0, 0);
root.bound = calculateBound(0, 0, -1, weights, profits, capacity);
pq.add(root);
int maxProfit = 0;
while (!pq.isEmpty()) {
KnapsackNode current = pq.poll();
// 如果当前节点的界值小于等于最大利润，剪枝
if (current.bound <= maxProfit) {
continue;
}
// 如果是叶子节点，跳过
if (current.level == n - 1) {
continue;
}
// 下一个物品索引
int nextLevel = current.level + 1;
// 考虑放入下一个物品
int newWeight = current.weight + weights[nextLevel];
int newProfit = current.profit + profits[nextLevel];
// 如果放入后不超重，更新最大利润
if (newWeight <= capacity && newProfit > maxProfit) {
maxProfit = newProfit;
}
// 创建子节点并计算界值
KnapsackNode child = new KnapsackNode(nextLevel, newProfit, newWeight);
child.bound = calculateBound(newWeight, newProfit, nextLevel, weights, profits, capacity);
// 如果界值大于当前最大利润，则加入队列
if (child.bound > maxProfit) {
pq.add(child);
}
// 考虑不放入下一个物品
child = new KnapsackNode(nextLevel, current.profit, current.weight);
child.bound = calculateBound(current.weight, current.profit, nextLevel, weights, profits, capacity);
if (child.bound > maxProfit) {
pq.add(child);
}
}
return maxProfit;
}
// 3. 旅行商问题（TSP）：优化实现
static class TSPNode implements Comparable<TSPNode> {
int level; // 当前城市数量
int[] path; // 当前路径
int cost; // 当前路径成本
int bound; // 下界
TSPNode(int level, int[] path, int cost) {
this.level = level;
this.path = path.clone();
this.cost = cost;
}
@Override
public int compareTo(TSPNode other) {
return Integer.compare(this.bound, other.bound);
}
}
public static int tsp(int[][] graph) {
int n = graph.length;
if (n == 0) return 0;
// 初始化起始节点（从城市0出发）
int[] initialPath = new int[n];
Arrays.fill(initialPath, -1);
initialPath[0] = 0;
TSPNode root = new TSPNode(0, initialPath, 0);
root.bound = calculateTSPBound(root, graph);
PriorityQueue<TSPNode> pq = new PriorityQueue<>();
pq.add(root);
int minCost = Integer.MAX_VALUE;
while (!pq.isEmpty()) {
TSPNode current = pq.poll();
// 如果当前下界大于等于已知最小成本，剪枝
if (current.bound >= minCost) {
continue;
}
// 如果到达最后一个城市，计算返回起点的总成本
if (current.level == n - 1) {
int totalCost = current.cost + graph[current.path[current.level]][0];
if (totalCost < minCost) {
minCost = totalCost;
}
continue;
}
// 扩展下一个可能的城市
for (int next = 0; next < n; next++) {
// 检查城市是否已访问
boolean visited = false;
for (int i = 0; i <= current.level; i++) {
if (current.path[i] == next) {
visited = true;
break;
}
}
if (!visited && graph[current.path[current.level]][next] > 0) {
// 创建新路径
int[] newPath = current.path.clone();
newPath[current.level + 1] = next;
// 计算新路径成本
int newCost = current.cost + graph[current.path[current.level]][next];
// 创建子节点
TSPNode child = new TSPNode(current.level + 1, newPath, newCost);
child.bound = calculateTSPBound(child, graph);
// 如果子节点下界小于当前最小成本，加入队列
if (child.bound < minCost) {
pq.add(child);
}
}
}
}
return minCost;
}
// 辅助方法：计算0-1背包问题的界值
private static double calculateBound(int currentWeight, int currentProfit, int level,
int[] weights, int[] profits, int capacity) {
if (currentWeight >= capacity) {
return 0;
}
double bound = currentProfit;
int remainingWeight = capacity - currentWeight;
int nextLevel = level + 1;
// 尽可能装入剩余物品
while (nextLevel < weights.length && weights[nextLevel] <= remainingWeight) {
remainingWeight -= weights[nextLevel];
bound += profits[nextLevel];
nextLevel++;
}
// 部分装入最后一个可装入的物品
if (nextLevel < weights.length) {
bound += (double) remainingWeight / weights[nextLevel] * profits[nextLevel];
}
return bound;
}
// 辅助方法：按单位重量利润排序
private static void sortByProfitDensity(int[] weights, int[] profits) {
int n = weights.length;
// 创建索引数组并排序
Integer[] indices = new Integer[n];
for (int i = 0; i < n; i++) {
indices[i] = i;
}
// 按单位重量利润降序排序
Arrays.sort(indices, (a, b) -> {
double ratioA = (double) profits[a] / weights[a];
double ratioB = (double) profits[b] / weights[b];
return Double.compare(ratioB, ratioA);
});
// 重新排列权重和利润数组
int[] sortedWeights = new int[n];
int[] sortedProfits = new int[n];
for (int i = 0; i < n; i++) {
sortedWeights[i] = weights[indices[i]];
sortedProfits[i] = profits[indices[i]];
}
System.arraycopy(sortedWeights, 0, weights, 0, n);
System.arraycopy(sortedProfits, 0, profits, 0, n);
}
// 辅助方法：计算TSP问题的下界
private static int calculateTSPBound(TSPNode node, int[][] graph) {
int n = graph.length;
int bound = node.cost;
boolean[] visited = new boolean[n];
// 标记已访问的城市
for (int i = 0; i <= node.level; i++) {
visited[node.path[i]] = true;
}
// 对已访问的中间节点，添加最小出边
for (int i = 0; i <= node.level; i++) {
int current = node.path[i];
int minEdge = Integer.MAX_VALUE;
// 对于起点和终点，只考虑一条边
if ((i == 0 && node.level != n - 1) || (i == node.level && node.level != n - 1)) {
continue;
}
for (int j = 0; j < n; j++) {
if (j != current && !visited[j] && graph[current][j] > 0 && graph[current][j] < minEdge) {
minEdge = graph[current][j];
}
}
if (minEdge != Integer.MAX_VALUE) {
bound += minEdge;
}
}
// 对未访问的节点，添加最小入边和最小出边的平均值
for (int i = 0; i < n; i++) {
if (!visited[i]) {
int minIn = Integer.MAX_VALUE;
int minOut = Integer.MAX_VALUE;
// 找最小入边
for (int j = 0; j < n; j++) {
if (j != i && (visited[j] || j == 0) && graph[j][i] > 0 && graph[j][i] < minIn) {
minIn = graph[j][i];
}
}
// 找最小出边
for (int j = 0; j < n; j++) {
if (j != i && !visited[j] && graph[i][j] > 0 && graph[i][j] < minOut) {
minOut = graph[i][j];
}
}
if (minIn != Integer.MAX_VALUE && minOut != Integer.MAX_VALUE) {
bound += (minIn + minOut) / 2;
}
}
}
return bound;
}
// 测试
public static void main(String[] args) {
// 测试0-1背包问题
int[] weights = {2, 3, 4, 5};
int[] profits = {3, 4, 5, 6};
int capacity = 5;
System.out.println("0-1背包问题 - 队列式分支限界法: " +
knapsackFIFO(weights.clone(), profits.clone(), capacity));
System.out.println("0-1背包问题 - 优先队列式分支限界法: " +
knapsackBestFirst(weights.clone(), profits.clone(), capacity));
// 测试TSP问题
int[][] graph = {
{0, 10, 15, 20},
{10, 0, 35, 25},
{15, 35, 0, 30},
{20, 25, 30, 0}
};
System.out.println("TSP问题最短路径成本: " + tsp(graph));
}
}
代码解析
上面的代码实现了分支限界法的几种典型写法，展示了不同的优化思路：
- 队列式分支限界法（FIFO）：
- 使用普通队列存储活节点，按先进先出原则处理
- 适合求解简单的优化问题，实现简单但效率一般
- 0-1 背包问题中，通过计算每个节点的上界来剪枝
- 优先队列式分支限界法（最佳优先）：
- 使用优先队列（最大堆或最小堆）存储活节点，按界值排序
- 优先处理更可能包含最优解的节点，通常效率更高
- 0-1 背包问题中，按上界降序排列，优先探索潜在利润更高的路径
- TSP 问题的优化实现：
- 采用下界计算函数，更精确地估计路径成本
- 使用优先队列按下界升序排列，优先探索成本更低的路径
- 通过精心设计的界函数，有效剪去大量无效分支
分支限界法的关键在于设计高质量的界函数，好的界函数能够更精确地估计目标函数值，从而剪去更多无效分支。在实现时，可以根据问题特点选择合适的搜索策略（FIFO 或最佳优先），并结合问题特性优化数据结构和界函数计算，以提高算法效率。
资料
https://zhuanlan.zhihu.com/p/36800491
五大常用算法之五：分支限界法 https://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741378.html
分支限界法——对解空间的一种策略搜索（广度优先搜索） https://www.jianshu.com/p/c738c8262087
回溯法套路模板 刷通leetcode https://zhuanlan.zhihu.com/p/112926891