5.4.3 经典分支限界问题

0-1背包问题（分支限界解法）

旅行商问题（分支限界解法）

问题描述：

给定n个城市和城市之间的距离，求解访问每个城市恰好一次并返回起点的最短路径。这是一个著名的NP-Hard问题，对于大规模问题，无法在多项式时间内求得精确解。

生活例子：

想象你是一名快递员，需要在一天内送货到城市的多个地点。你希望规划一条路线，从公司出发，依次访问所有送货点，最后回到公司，同时希望总行驶距离最短，以节省时间和燃料。

分支限界法思路：

分支限界法通过以下步骤解决旅行商问题：

1. 使用优先队列管理搜索空间，按下界排序（这是最小化问题，所以按下界升序排序）
2. 从起始城市开始，逐步构建路径
3. 对于每个节点，尝试将未访问的城市添加到当前路径中
4. 使用下界函数剪枝，如果节点的下界大于当前已知的最小成本，则不再探索该节点

下界计算方法：

下界是对最优解的估计，通常是一个比实际最优解更乐观的值。对于旅行商问题，下界计算方法为：

1. 已确定路径的成本
2. 对于每个未访问的城市，添加其连接到其他城市的最小成本边

图解过程：

假设有4个城市，距离矩阵如下：

    0   1   2   3
0 | 0  10  15  20 |
1 | 10  0  35  25 |
2 | 15 35   0  30 |
3 | 20 25  30   0 |

从城市0出发的搜索树：

                      [0]（起点）
                    /    |     \
                  /      |       \
               [0,1]   [0,2]    [0,3]
              /   \     /  \     /   \
           [0,1,2] [0,1,3] ... ... ... 
           /      \  
      [0,1,2,3]  [0,1,3,2]

代码实现：

public static int tspBranchAndBound(int[][] graph) {
    int n = graph.length;  // 城市数量
    
    // 创建根节点
    Node root = new Node();
    root.level = 0;  // 已访问城市数量（包括起点）
    root.path.add(0);  // 从城市0开始
    root.bound = computeBound(root, graph, n);  // 计算下界
    
    // 使用优先队列，按下界排序（最小化问题，所以按下界升序排序）
    PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> Integer.compare(a.bound, b.bound));
    pq.add(root);  // 将根节点加入优先队列
    
    int minCost = Integer.MAX_VALUE;  // 当前找到的最小成本
    
    // 当优先队列非空时，继续搜索
    while (!pq.isEmpty()) {
        // 取出队首节点（下界最小的节点）
        Node node = pq.poll();
        
        // 剪枝：如果下界大于等于当前最小成本，则跳过
        if (node.bound >= minCost) continue;
        
        // 如果已经访问了所有城市
        if (node.level == n - 1) {
            // 添加最后一个未访问的城市
            int lastCity = -1;
            for (int i = 0; i < n; i++) {
                if (!node.path.contains(i)) {
                    lastCity = i;
                    break;
                }
            }
            
            node.path.add(lastCity);  // 添加最后一个城市
            
            // 计算完整路径的总成本（包括回到起点）
            int currentCost = 0;
            for (int i = 0; i < n; i++) {
                currentCost += graph[node.path.get(i)][node.path.get((i + 1) % n)];
            }
            
            // 更新当前找到的最小成本
            minCost = Math.min(minCost, currentCost);
            continue;
        }
        
        // 尝试访问每个未访问的城市
        for (int i = 0; i < n; i++) {
            if (!node.path.contains(i)) {  // 如果城市i尚未访问
                // 创建新节点
                Node newNode = new Node();
                newNode.level = node.level + 1;  // 已访问城市数量加1
                newNode.path.addAll(node.path);  // 复制当前路径
                newNode.path.add(i);  // 添加新城市
                newNode.bound = computeBound(newNode, graph, n);  // 重新计算下界
                
                // 如果下界小于当前最小成本，则加入队列继续探索
                if (newNode.bound < minCost) {
                    pq.add(newNode);
                }
            }
        }
    }
    
    return minCost;
}

// 计算节点的下界
private static int computeBound(Node node, int[][] graph, int n) {
    // 计算下界的方法：已经确定的路径成本 + 剩余城市的最小出边
    int bound = 0;
    
    // 1. 已确定路径的成本
    for (int i = 0; i < node.path.size() - 1; i++) {
        bound += graph[node.path.get(i)][node.path.get(i + 1)];
    }
    
    // 2. 对于每个未访问的城市，添加最小出边
    // 这是一个乐观估计，假设每个城市都能以最小成本连接
    for (int i = 0; i < n; i++) {
        if (!node.path.contains(i)) {  // 如果城市i尚未访问
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < n; j++) {
                if (i != j) {  // 不考虑自环
                    min = Math.min(min, graph[i][j]);  // 找出最小边
                }
            }
            bound += min;  // 将最小边加入下界
        }
    }
    
    return bound;
}

// 搜索树节点类
static class Node {
    int level;         // 当前访问的城市数量
    List<Integer> path = new ArrayList<>();  // 当前路径
    int bound;         // 下界（对最优解的估计）
}

时间复杂度分析：

最坏情况下，分支限界法需要探索所有可能的排列，时间复杂度为O(n!)。但在实际应用中，由于有效的剪枝策略，通常可以大大减少搜索空间。

空间复杂度分析：

O(n²)，主要用于存储优先队列中的节点和路径信息。

与其他解法的比较：

应用场景：

• 物流配送路线规划
• 电路板钻孔问题
• 网络路由优化
• 机器人路径规划