分支限界算法 (Branch and Bound)像“带导航的迷宫搜索”一样不仅会试探(分支)还会计算一个“预期代价”(限界)。如果某条路还没走完但预期代价已经超过了当前已知的最优解就直接放弃这条路(剪枝)优先去探索更有希望的路径。经典问题推演0-1背包问题(求最大价值)分支对每个物品产生“放入”和“不放入”两个分支结点。限界(计算上界)使用贪心思想假设剩余容量可以装下部分物品算出当前结点能达到的理论最大价值。剪枝如果某个结点的理论最大价值还不如我们已经找到的一个实际可行解的价值直接丢弃该结点。搜索策略总是优先扩展理论价值最高的结点(优先队列/最大堆)。旅行商问题 (Traveling Salesman Problem)问题描述给定 n 个城市以及它们两两之间的距离。一名推销员需要从起点出发访问每个城市恰好一次最后回到起点。请问如何规划路线使得总行驶距离最短示例4个城市距离矩阵如下。最优路线为 0 - 1 - 3 - 2 - 0总距离为 10 25 30 15 80。0 1 2 3 0 | 0 10 15 20 | 1 | 10 0 35 25 | 2 | 15 35 0 30 | 3 | 20 25 30 0 |为什么用分支限界法TSP 是一个著名的 NP-Hard 问题。如果用普通的回溯法(深度优先搜索)需要遍历所有的全排列时间复杂度是阶乘级\(O(n!)\)数据量稍微大一点就会算到地老天荒。而分支限界法通过计算“下界(乐观估计)”能够提前砍掉那些“注定不可能成为最优解”的分支从而极大提高搜索效率。核心思想分支、限界与优先队列分支(Branch)从当前城市出发将所有未访问的城市作为下一步的可能选择生成多个子节点。限界(Bound)为每个节点计算一个“下界”。下界 当前已走路径的成本 剩余未访问城市各自的最小出边之和。这是一个“极其乐观的估计”代表这条路未来最少还要花多少代价。优先队列(Priority Queue)不再像回溯那样一条路走到黑而是使用优先队列(最小堆)。每次总是优先扩展“下界最小(最有希望)”的节点。如果某个节点的下界已经大于等于当前已知的最优解直接将其丢弃(剪枝)。核心代码#include stdio.h #include stdlib.h #include limits.h #define N 4 // 节点结构体 typedef struct Node { int path[N]; // 当前走过的路径 int level; // 当前路径包含的城市数量 int cost; // 当前路径的实际成本 int bound; // 该节点的下界(乐观估计) } Node; // 辅助函数计算节点的下界 int computeBound(int path[], int level, int graph[N][N]) { int bound 0; // 1. 加上已经走过的实际路径成本 for (int i 0; i level - 1; i) { bound graph[path[i]][path[i 1]]; } // 2. 加上剩余未访问城市的最小出边(乐观估计) for (int i 0; i N; i) { int visited 0; for (int j 0; j level; j) { if (path[j] i) { visited 1; break; } } if (!visited) { int minEdge INT_MAX; for (int j 0; j N; j) { if (i ! j graph[i][j] minEdge) minEdge graph[i][j]; } bound minEdge; } } return bound; } // 优先队列的比较函数(下界越小优先级越高) int cmp(const void *a, const void *b) { return ((Node *)a)-bound - ((Node *)b)-bound; } // 分支限界法主函数 int tspBranchAndBound(int graph[N][N]) { Node pq[1000]; // 模拟优先队列 int pqSize 0; int minCost INT_MAX; // 记录全局最优解 // 初始化根节点(从城市0出发) Node root { {0}, 1, 0, 0 }; root.bound computeBound(root.path, root.level, graph); pq[pqSize] root; while (pqSize 0) { // 1. 取出优先级最高(bound最小)的节点 qsort(pq, pqSize, sizeof(Node), cmp); Node curr pq[--pqSize]; // 弹出队首 // 2. 限界剪枝如果当前节点的下界 已知最优解直接放弃 if (curr.bound minCost) continue; // 3. 分支尝试前往下一个未访问的城市 if (curr.level N) { // 走完了所有城市加上回起点的边 int finalCost curr.cost graph[curr.path[N-1]][0]; if (finalCost minCost) minCost finalCost; continue; } for (int i 0; i N; i) { int visited 0; for (int j 0; j curr.level; j) { if (curr.path[j] i) { visited 1; break; } } if (!visited) { Node newNode curr; newNode.path[curr.level] i; newNode.level; newNode.cost graph[curr.path[curr.level-2]][i]; newNode.bound computeBound(newNode.path, newNode.level, graph); // 只有下界小于当前最优解才加入队列继续探索 if (newNode.bound minCost) { pq[pqSize] newNode; } } } } return minCost; } int main() { int graph[N][N] {{0,10,15,20}, {10,0,35,25}, {15,35,0,30}, {20,25,30,0}}; printf(最短路径长度为%d\n, tspBranchAndBound(graph)); return 0; }示例推演以 4 个城市为例从城市 0 出发第 1 步初始化与根节点扩展目标建立初始搜索空间。根节点路径 [0]实际成本 0。计算下界剩余城市 {1, 2, 3} 的最小出边分别为 10, 15, 20。下界 0 10 15 20 45。分支生成子节点 0,1, 0,2, 0,3。分别计算它们的下界并放入优先队列。第 2 步优先队列调度与剪枝目标挑选最有希望的节点继续探索。从优先队列中弹出下界最小的节点假设是 [0,1]。检查限界如果 [0,1] 的下界已经 我们之前偶然找到的一个完整路径的成本直接丢弃(剪枝)。如果未剪枝继续分支从城市 1 出发生成 [0,1,2] 和 [0,1,3]计算下界后重新入队。第 3 步找到可行解与持续优化目标更新全局最优解加速后续剪枝。当某个节点扩展到包含所有 4 个城市时加上回 0 的边得到一个完整的环路成本。更新全局最优解 minCost。minCost 变小后之前队列中那些下界大于等于新 minCost 的节点将在下一次出队时被无情剪枝。最终结果优先队列被清空返回 minCost 80。核心提炼核心特征基于广度优先搜索(BFS)或最小/最大消耗优先核心动作是“分支 限界(剪枝)”。“用空间换时间用预估换效率”与回溯法的核心区别搜索方式回溯法是深度优先(DFS)分支限界法通常是广度优先(BFS)或最小耗费优先(优先队列)。求解目标回溯法旨在找出所有解或任意一个可行解分支限界法旨在快速找出最优解。节点扩展回溯法遇到死胡同会“回溯”分支限界法每个活节点只有一次成为扩展节点的机会不回头而是通过“限界”直接剪掉整棵子树。两大核心要素活结点表的数据结构通常使用优先队列(最小堆/最大堆)。限界函数(Bound)这是算法的灵魂。最小化问题算下界最大化问题算上界。限界函数越紧剪枝效果越好。