分支限界法（Branch and Bound）
1. 核心思想
分支限界法在问题的解空间树上搜索，但与回溯法的深度优先不同，它采用广度优先或最小耗费（最大效益）优先的策略扩展结点。每一个活结点只有一次机会成为扩展结点：一旦成为扩展结点，就一次性产生其所有儿子结点，并用限界函数估算这些儿子结点的上界或下界：
- 若某儿子结点的估值不可能产生比当前最优解更好的解，直接舍弃该子树；
- 其余儿子结点加入活结点表，等待被选取为下一个扩展结点。
2. 两种常见的活结点表组织方式
| 方式 | 数据结构 | 扩展顺序 | 特点 |
|---|
| 队列式（FIFO）分支限界法 | 队列 | 先进先出，即广度优先 | 实现简单，但搜索盲目，结点数多 |
| 优先队列式分支限界法 | 堆（最小堆/最大堆） | 按结点估值选取 | 每次扩展最有希望的结点，通常能更快收敛到最优解 |
常见的「最小耗费优先」又称 LC（Least Cost）分支限界法。
3. 与回溯法的对比
| 对比项 | 回溯法 | 分支限界法 |
|---|
| 搜索顺序 | 深度优先（一条路走到底再回退） | 广度优先 / 优先队列 |
| 活结点存储 | 栈 | 队列 / 优先队列 |
| 结点扩展方式 | 每个活结点多次成为扩展结点（先深入再回退） | 每个活结点最多一次成为扩展结点 |
| 求解目标 | 所有解 / 任一解 | 最优解 |
| 典型剪枝 | 约束函数 + 限界函数 | 限界函数（与当前最优解比较） |
| 内存占用 | 较小（只存当前路径） | 较大（需保存大量活结点） |
4. 算法要点
- 定义解空间树：确定是子集树还是排列树。
- 设计限界函数：给出以该结点为根的子树中可能达到的解的上界（求最大值问题）或下界（求最小值问题），要求计算简单且尽可能紧。
- 确定搜索策略：FIFO 还是优先队列。
- 维护当前最优解：搜索过程中不断更新最优解，并用它来剪枝。
5. 典型问题
| 问题 | 解空间树 | 搜索策略 | 限界函数 |
|---|
| 0-1 背包 | 子集树 | 优先队列（最大价值上界优先） | 当前价值 + 剩余物品按单位价值装满的上界 |
| 装载问题 | 子集树 | 队列式 / 优先队列 | 当前载重 + 剩余集装箱总重 |
| 旅行商问题 | 排列树 | 优先队列（最小耗费优先） | 已走路径长度 + 最小出边下界 |
| 单源最短路径 | 子集树 | 优先队列（最小耗费优先） | 当前路径长度 |
| 最大团问题 | 子集树 | 优先队列 | 当前团大小 + 剩余顶点数 |
| 批处理作业调度 | 排列树 | 优先队列 | 已完成作业时间下界 |
评论