分支限界法（Branch and Bound）

1. 核心思想

分支限界法在问题的解空间树上搜索，但与回溯法的深度优先不同，它采用广度优先或最小耗费（最大效益）优先的策略扩展结点。每一个活结点只有一次机会成为扩展结点：一旦成为扩展结点，就一次性产生其所有儿子结点，并用限界函数估算这些儿子结点的上界或下界：

• 若某儿子结点的估值不可能产生比当前最优解更好的解，直接舍弃该子树；
• 其余儿子结点加入活结点表，等待被选取为下一个扩展结点。

2. 两种常见的活结点表组织方式

方式	数据结构	扩展顺序	特点
队列式（FIFO）分支限界法	队列	先进先出，即广度优先	实现简单，但搜索盲目，结点数多
优先队列式分支限界法	堆（最小堆/最大堆）	按结点估值选取	每次扩展最有希望的结点，通常能更快收敛到最优解

常见的「最小耗费优先」又称 LC（Least Cost）分支限界法。

3. 与回溯法的对比

对比项	回溯法	分支限界法
搜索顺序	深度优先（一条路走到底再回退）	广度优先 / 优先队列
活结点存储	栈	队列 / 优先队列
结点扩展方式	每个活结点多次成为扩展结点（先深入再回退）	每个活结点最多一次成为扩展结点
求解目标	所有解 / 任一解	最优解
典型剪枝	约束函数 + 限界函数	限界函数（与当前最优解比较）
内存占用	较小（只存当前路径）	较大（需保存大量活结点）

4. 算法要点

1. 定义解空间树：确定是子集树还是排列树。
2. 设计限界函数：给出以该结点为根的子树中可能达到的解的上界（求最大值问题）或下界（求最小值问题），要求计算简单且尽可能紧。
3. 确定搜索策略：FIFO 还是优先队列。
4. 维护当前最优解：搜索过程中不断更新最优解，并用它来剪枝。

5. 典型问题

问题	解空间树	搜索策略	限界函数
0-1 背包	子集树	优先队列（最大价值上界优先）	当前价值 + 剩余物品按单位价值装满的上界
装载问题	子集树	队列式 / 优先队列	当前载重 + 剩余集装箱总重
旅行商问题	排列树	优先队列（最小耗费优先）	已走路径长度 + 最小出边下界
单源最短路径	子集树	优先队列（最小耗费优先）	当前路径长度
最大团问题	子集树	优先队列	当前团大小 + 剩余顶点数
批处理作业调度	排列树	优先队列	已完成作业时间下界