Data-Structure/Algorithm/Exam/8.md

第八章 分支限界法 (Branch and Bound Method)

目录总览

本章主要包含以下七个部分的内容：

• 8.1 一般方法：介绍分支限界法适用的问题特点、基本思想、抽象化描述、检索方式及FIFO检索。

• 8.2 LC-检索：讲解智能选择结点的LC-检索的优点、成本函数量化方法、定义及成本估计函数。

• 8.3 15-谜问题：通过经典实例分析状态空间树、函数定义、判定定理及不同检索方式的对比。

• 8.4 求最小成本的分支限界法：探讨如何利用成本估计函数与最优解上界 U 加速寻找最优解，并给出抽象算法（FIFOBB、LCBB）。

• 8.5 带有期限的作业调度问题：具体实例的解空间构造、约束函数、成本估计及算法运行过程。

• 8.6 货郎担问题（TSP）：具体实例的成本下界函数设计及LC-分支限界法的实例运行。

• 8.7 小结：总结分支限界法与回溯法的异同及核心掌握点。

---

8.1 一般方法

1. 方法适用的问题特点

• 适用范围：与回溯法类似，分支限界法同样适用于求解组合数较大的问题，特别是组合优化问题（即求最优解的问题）。

• 基本概念继承：在分支限界法中，解向量的表达、显式约束条件、隐式约束条件、解空间和解空间树等概念均与回溯法相同。

• 主要区别：两者的主要区别在于 E-结点（即扩展结点）的处理方式不同。

• 学术观点：清华大学出版社出版的屈婉玲等编著的《算法设计与分析》中认为：“分支限界是回溯算法的变种”。

2. 分支限界法的基本思想

• 准备工作：针对问题定义解空间树结构（元组、显式约束、隐式约束），并检验问题是否满足多米诺性质，以寻找一个可行解。

• 搜索规则：假设当前寻找一个答案结点，按下列方式搜索解空间树：

• 如果根结点 T 是答案结点，则输出 T 并结束操作；否则令 T 成为当前的扩展结点（E-结点）。

• 生成 E-结点的所有儿子结点，并对每个儿子结点 X 进行判断：

• 如果 X 是答案结点，输出到根结点的路径，操作结束；

• 如果 X 满足约束函数 $B$，则将 X 添加到活结点表中；否则直接舍弃（剪枝） $X$。

• 从活结点表中选出下一个结点成为新的 E-结点，重复上述操作。如果活结点表为空，则算法以失败结束。

• 约束函数剪枝作用：避免生成那些不包含可行解的子树。

3. 算法8.1 分支限界法的抽象化描述

• 核心伪代码逻辑：

procedure BB(T)
    if T是答案结点 then 输出T; return endif
    E ← T
    将活结点表初始化为空
    loop
        for E的每个儿子X do
            if X是答案结点 then 输出从X到T的那条路径; return; endif
            if B(X) then call ADD(X); PARENT(X) ← E endif
        repeat
        if 表中不再有活结点 then print("no answer node"); return; endif
        call LEAST(E)
    repeat
end BANDB

• 辅助函数含义：ADD(X) 用于将结点 X 添加到活结点表中；LEAST(E) 用于从活结点表中选中一个结点赋值给 $E$，并从表中删除该结点。
• 思考题：如果想获得所有可行解，算法该怎样设计？

4. 分支限界法的不同检索方式

根据活结点的检索次序，分支限界策略主要分为以下两种：

• 顺序队列式：
  • 活结点依赖进入活结点表的先后顺序从表中被选出。
  • 最常见的是先进先出方式（FIFO），活结点表采用队列实现。若 LEAST 遵循 FIFO，算法即为 FIFO-检索。
• 优先队列式：
  • 活结点依赖成本估计函数 $\hat{c}$，\hat{c} 最小或最大的活结点优先从表中被选出。
  • 活结点表采用极小堆或极大堆实现。若 LEAST 遵循极小堆优先队列，算法即为 LC-检索。

5. 理解FIFO-检索（以4-皇后问题为例）

• 运行分析：在4-皇后问题中，FIFO-分支限界法顺次处理了31个结点（结点选择盲目，按层序生成，处理顺序为2, 18, 34, 50, 8, 13, 29, 35, 51, 56, 14, 30, 38, 54...），而回溯法（深度优先）一共仅处理了16个结点。这说明纯粹的FIFO检索在某些问题上搜索效率并不高。

---

8.2 LC-检索（Least Cost Search）

1. LC-检索的优点

• 盲目性问题：在 FIFO-分支限界法中，对下一个 E-结点的选择是死板且盲目的，没有给可能快速检索到答案结点的活结点赋予任何优先权。
• 智能化改进：理想状态下，对活结点表使用一个“有智力的”成本函数来选取下一个 E-结点，给那些可能导致答案结点的活结点赋予优先次序，从而加快到达答案结点的检索速度。

2. 成本函数 c 的量化方法

令 X 是当前结点，c(X) 定义为以 X 为根的子树中的最小成本值。常见的量化方法有三种：

• 方法1：寻找生成数目最少的答案结点（基于生成答案结点之前需要生成的结点数定义）。
• 方法2：寻找路径长度最短的答案结点（基于答案结点的路径长度定义）。
• 方法3：寻找使目标函数取极值的答案节点，即最优解（基于问题描述中的目标函数定义）。
• 注：本章中，当问题不存在目标函数时，默认采用方法2（路径长度）来定义函数。

3. 成本函数定义

• 真实成本：对状态空间树里的解结点 X 定义真实成本函数 $\text{cost}(X)$，当 X 是答案结点时其值为从根到 X 的真实代价（如路径长度、目标函数值），当 X 不是答案结点时其值为 $\infty$。
• 上帝视角成本函数 $c(X)$： c(X) = \begin{cases} \text{cost}(X) & \text{叶节点} X \text{是答案节点} \\ \min\{\text{cost}(P) \mid \text{答案节点} P \in \text{子树} X\} & \text{子树} X \text{中包含答案节点} \\ \infty & \text{子树} X \text{不包含答案节点} \end{cases}
• 思考题：在什么样的状态空间树中会出现答案结点 X 不是叶结点的情况？（答：$k$-元组表达时）。
• 实例：设 c(X) = 到达答案结点的最短路径长度。蓝色结点表示不能到达任何答案结点（$c=\infty$），叶结点10（路径长度3）和11（路径长度4）是答案结点，则 $c(10)=3$，$c(8)=3$，$c(3)=3$。基于对活结点表的检索，可快速找到结点10。

4. 成本函数的问题与解决策略

• 面临问题：要精确得到函数 c 非常困难。因为 c(X) 基于答案结点的真实成本定义，为了求出该值，必须先生成整棵状态空间树，其计算工作量与原问题具有相同的复杂度。
• 替代方案：引入一个易于计算的成本估计函数 $\hat{c}(X)$ 来替代 c(X) 对活结点表进行检索。定义 \hat{c}(X) 时需要满足：
  1. 很容易确定根结点到 X 已经产生的成本；
  2. 很容易估计从 X 到一个答案结点可能会产生的成本。

5. 成本估计函数 \hat{c} 的定义与要求

• 数学公式： \hat{c}(X) = f(h(X)) + \hat{g}(X)
  • $h(X)$：根结点到结点 X 的实际成本。
  • $\hat{g}(X)$：从 X 到最小成本答案结点的估计（未来）成本。
  • $f$：非负函数，用于调整 h 和 \hat{g} 在成本估计函数中的影响比例。
• 对 \hat{c}(X) 的硬性要求：
  1. 易于计算，能够替代对活结点表的检索。
  2. 必须满足下界性质：$\hat{c}(X) \le c(X)$。
  3. 当答案节点 X 是叶节点时，满足 $\hat{c}(X) = c(X)$。

6. LC-检索与特殊情况

• LC-检索的决策：每次均选取成本估计函数 \hat{c}(X) 的值最小的活结点作为下一个 E-结点。
• BFS（广度优先）的本质：当 f(h(X)) = \text{根到结点} X \text{的路径长度} 且 \hat{g}(X) = 0 时，BFS就是LC-检索的一种特殊情况。
• 思考题：只用 \hat{g}(X) 为结点排序是否适合（即 $f(h(X))=0$）？
  • 后果分析：当 \hat{c}(X) = \hat{g}(X) 时，假设子树 X 的儿子结点是 $Y$，很容易存在 $\hat{g}(Y) \le \hat{g}(X)$。若活结点表中其他结点估计值均大于 $\hat{g}(X)$，则 X 成为 E-结点后，Y 紧接着也会成为新的 E-结点。该过程会导致算法一直纵深方向检索，直到子树 X 全部检索完毕才可能跳出。
  • 结论：只考虑未来可能的代价，属于“乐观的冒进”，可能会丢失掉更靠近根的答案结点，导致结果不理想。
• 总结：LC-检索通过 \hat{c} 进行优先选择，使得算法倾向于选择更靠近答案结点，同时又离根结点较近的结点。

---

8.3 15-谜问题

1. 问题描述

• 在一个分成16格的方形棋盘上放有15块编了号码的牌，要求通过一系列合法的移动（将邻接空位置的牌移入空位），将初始排列转换成指定的目标排列。

2. 状态空间树

• 问题状态：每一个棋牌布局都是一个状态。
• 树结构：棋牌每移动一次，就会产生一个新的布局。当前结点 X 的儿子结点是 X 通过一次合法移动到达的布局状态。整棵树由所有可从初始状态经过一系列合法移动到达的状态构成。
• 移动顺序：边表示为空格的一次合法移动，按 上、右、下、左 的顺序进行。
• 注：只有初始状态满足某些条件时，才能达到目标状态。

3. 函数定义与判定定理

• 基础定义：对棋盘方格按目标状态的顺序编上1~16号（空格位是16）。
  • $\text{POSITION}(i)$：牌面 i 在初始状态时的位置号（$1 \le i \le 16$）。
  • $\text{LESS}(i)$：牌面上满足 j < i 且 \text{POSITION}(j) > \text{POSITION}(i) 的 j 的数目（即逆序数）。
• 初始状态判定定理：在初始状态下，如果空格在阴影位置中（按国际象棋盘交替染色），则令 $X=1$；否则令 $X=0$。当且仅当初始状态的 \sum_{i=1}^{16} \text{LESS}(i) + X 是偶数时，目标状态才是可达的。

4. 不同检索方式在15-谜问题中的表现

• FIFO-检索：按层序千篇一律地移动。虽然能找到离根最近的答案结点，但不管开局如何，搜索顺序十分呆板，不关心问题的具体实例。
• 深度优先检索：总是采取由根开始的最左路径。呆板而盲目，在搜索过程中极有可能越走越远，远离目标。
• LC-检索的设计：
  • c(X) 定义：从初始排列到达目标排列时，棋牌的最少移动次数。
  • \hat{c}(X) 定义：$\hat{c}(X) = f(X) + \hat{g}(X)$。
    • $f(X)$：从初始排列到状态 X 时，棋牌已经移动的次数。
    • $\hat{g}(X)$：不在其目标位置的非空白棋牌数目。
  • 优势：在这种设计下，LC-检索几乎和使用精确函数 c 一样有效，其选择性比很多盲目检索方法强得多。

---

8.4 求最小成本的分支限界法

1. 算法改进的背景

• 基础BB算法的缺陷：在常规的分支限界法中，算法一旦判断出儿子结点 X 是答案结点，就会打印路径并直接结束。
• LC-检索的局限：基于LC-检索的算法不一定能直接找到具有最小成本的答案结点。除非对 \hat{c} 追加极其苛刻的要求：对于每一对结点 $X, Y$，当 c(X) < c(Y) 时必须有 $\hat{c}(X) < \hat{c}(Y)$。由于这很难实现，因此必须改进算法。
• 改进思路：改变判断时机。基于LC-检索从活结点表中选出 E-结点后，再判断 E 是否是答案结点，如果是则结束操作。该思路适用于 $n$-元组表达。

2. 算法8.2 找出最小成本答案结点的LC算法

• 伪代码逻辑：

procedure LC(T, ĉ)
E ← T, 将活结点表初始化为空
loop
if E是答案结点 then 输出从E到T的那条路径; return; endif // 取出后判断
for E的每个儿子X do
if B(X) then call ADD(X); PARENT(X) ← E; endif
repeat
if 表中不再有活结点 then print("no answer node"); return; endif
call LEAST(E) // 选择ĉ最小的
repeat
end LC

• $n$-元组与 $k$-元组的处理区别：
  • $n$-元组表达：答案结点一定是叶结点，在叶结点处满足等式 $\hat{c}(\cdot) = c(\cdot) = \text{cost}(\cdot)$。由于活结点表中所有结点 L 都有 $\hat{c}(E) \le \hat{c}(L)$，因此 \text{cost}(E) 一定是最小成本，算法一定能终止于最小成本答案结点。
  • $k$-元组表达：答案结点可能不是叶结点，只能满足不等式 $\hat{c}(\cdot) \le c(\cdot) \le \text{cost}(\cdot)$，因此算法不一定能终止于最小成本答案结点。为了解决通用性，需要引入剪枝能力更强的界限算法。

3. 加速寻找最小成本的思想（引入限界 $U$）

• 基本思想：在寻找最优解过程中，如果发现某个结点 X 不可能导致比当前已知可行解更好的解，则不必再搜索子树 $X$，直接将其剪枝（最优解剪枝）。
• 具体设计：
  • 设置一个全局的最小成本上界 $U$，表示当前最小成本不会大于 $U$。
  • 如果某个结点的 $\hat{c}(X) > (\text{或} \ge) U$，则无需检索以 X 为根的子树。
  • 分支限界法求极小化问题时，问题转化为在解空间树中寻找最小成本答案节点：将目标函数作为成本函数 $c$，约束条件作为约束函数 $B$，设计下界估计函数 \hat{c}(X) \le c(X) 和上界 U 进行搜索。

4. 最小成本上界 U 与成本上界函数 u(X)

• 全局上界 U 的特征：
  • 含义：它是当前算法生成过的所有状态结点对最小成本上界估计的最小值。
  • 取值：初值设为 $\infty$（或通过启发式方法得到），随着结点的访问不断被改小。
  • 作用：检查结点的死活，通过剪枝加快找到最优解。
• 成本上界函数 u(X) 的特征：
  • 含义：它是从根出发到 X 的这条指定路径下的最小成本上界估计值。
  • 构成：由“根到 X 的真实成本”和“ X 到最小成本答案结点的成本上界估计”两部分构成。
  • 要求：易于计算，且满足 $\hat{c}(X) \le c(X) \le u(X)$，在叶子答案结点处 $c(X) = u(X)$。

5. 界 U 的改值、剪枝及设计技巧

• U 的改值时机：
  1. 发现一个答案结点 X 且 \text{cost}(X) < U 时，令 $U \leftarrow \text{cost}(X)$；
  2. 发现一个状态结点 X 且 u(X) < U 时，令 $U \leftarrow u(X)$。
• U 的剪枝规则：
  • 若 U 的值来自真实成本（已找到具体可行解），则 \hat{c}(X) \ge U 的活结点都可以杀死。
  • 若 U 的值来自成本上界（仅确定存在该上界的解，尚未实际找到），则 \hat{c}(X) > U 的活结点可以杀死。
• 统一剪枝技巧：为了应对 U 来源不同导致剪枝策略不同的问题，引入一个足够小的正常数 $\epsilon$。当 U 从 u(X) 获取数值时，调高一点：$U \leftarrow u(X) + \epsilon$；从 \text{cost}(X) 获取时保持不变：$U \leftarrow \text{cost}(X)$。此时统一剪枝策略为：当前结点若满足 $\hat{c}(X) \ge U$，则直接杀死。

6. 核心限界算法描述（算法8.3、8.4、8.5）

• 算法8.3 界函数 UB(X, U, ans)：

procedure UB(X, U, ans)
if ĉ(X) > U or (ans有结点 and ĉ(X) == U) then return false endif // 界定杀死
if X是答案节点 and cost(X) < U then U ← cost(X); ans ← X endif    // 更改U为真实成本
if u(X) < U then U ← u(X); ans ← 0 endif                         // 更改U为估计上界
return true
end UB

• 算法8.4 求最小成本的 FIFO-分支限界算法 (FIFOBB)：利用队列存储活结点。子结点入队时必须通过 B(X) 检验和 UB 检验；出队时若满足 $\hat{c}(E) < U$（或无答案结点且相等）则允许扩展，否则跳过。
• 算法8.5 求最小成本的 LC-分支限界法 (LCBB)：利用极小堆存储活结点。当表空，或者堆顶结点的 $\hat{c} > U$（或有答案结点且相等）时，算法结束，此时的 U 即为最小成本，从 ans 核心回溯输出路径。

7. 极大化问题的转化方法

很多问题需要求目标函数的极大值，可以通过以下两种方式解决：

• 方法1（相反数法）：取目标函数的相反数作为成本函数 $c$，将问题转化为极小化问题。
• 方法2（镜像修改法）：把目标函数直接作为成本函数 $c$，转化为寻找最大成本答案结点。此时满足 $u(X) \le c(X) \le \hat{c}(X)$，全局界 U 作为下界会不断增大，\hat{c}(X) < U 的结点被杀死。

8. 总结最优解分支限界法

• 剪枝依据：约束函数 $B$（限定是否存在可行解）；成本估计函数 \hat{c}(X) 和界 $U$（界定是否存在最优解）。
• 剪枝发生点：X 入活结点表时（接受 B 和 U 检验）；X 出活结点表时（接受 U 检验）。
• 终止条件：活结点表为空；或者活结点表中再没有能通过 U 检验的结点。
• 思考题：用回溯法解决最优解问题时，\hat{c}(X) 和界 U 能否用于提高算法效率？（答：能，即深度优先的分支限界法）。

---

8.5 带有期限的作业调度问题

1. 问题描述与实例

• 问题定义：n 个作业和一台处理机，每个作业 i 表示为三元组 $(p_i, d_i, t_i)$（分别代表罚款、期限、处理时间）。若在期限 d_i 前未完成，则需交付 p_i 的罚款。目标是选择一个子集 J 使得选中的作业能在期限内完成，且未选中的作业罚款总数最小（极小化问题）。
• 实例参数：$n=4$，作业分别为：$(5,1,1)$、$(10,3,2)$、$(6,2,1)$、$(3,1,1)$。
• 解空间表达：采用不定长 $k$-元组 $(X_1, \dots, X_k), k \le n$。显式约束：选中的作业下标严格递增 $X_i < X_{i+1}$。隐式约束：作业能在期限前完成。整个解空间树包含 2^n=16 个结点。

2. 约束与限界函数设计

• 约束函数 B：通过检验作业完成的可行性，实例中最终有10个活结点通过 B 检验，最优解为 ${2, 3}$，根结点成本 $c(1)=8$。
• 成本估计函数 \hat{c}(X) 设计：
  • 设 S_X 是根结点到结点 X 时选中的作业集合，令 $m = \max{i \mid i \in S_X}$。
  • 若 X 是可行解，则 $\hat{c}(X) = \sum p_i \quad (i < m, \text{且} i \notin S_X)$；若 X 不可行，则 $\hat{c}(X) = \infty$。
• 成本上界函数 u(X) 设计：
  • $u(X) = \sum p_i \quad (i \notin S_X)$，全局上界 $U = \min{u(X)}$。
  • 实例中 U 的改值轨迹为 $24 \rightarrow 19 \rightarrow 14 \rightarrow 9 \rightarrow 8$。在 FIFO 检索下考虑 U 的剪枝作用，最终只有 5 个活结点通过了 U 检验，其余结点均被 kill。
• 运行结果：算法结束时队列为空，最终全局最小成本 $U=8$，ans 对应的最优解结点编号为 9。

---

8.6 货郎担问题（TSP）

1. 问题描述与实例

• 问题定义：售货员要周游 n 个城市，已知各城市之间的有向边成本 $c_{ij} > 0$，求一条每个城市只经过一次并回到起点的最小成本周游路线。
• 复杂度：动态规划求解的时间复杂度是 $O(n^2 2^n)$。分支限界法最坏情况也是 $O(n^2 2^n)$，但对许多具体实例，能花费较少的时间。
• 问题实例：$n=4$，从城市1出发，经过 \{2,3,4\} 的排列后再回到1。
• 解空间表达：固定长 3-元组 $(X_1, X_2, X_3)$。显式约束：X_i \in \{2,3,4\} 且互不相同。隐式约束：相邻两点之间必须有边存在。状态空间树共有 3! = 6 个叶结点。

2. 成本函数与下界函数设计

• 成本函数 $c(X)$：若 X 是叶结点，为该周游路线的真实总成本；若 X 是非叶结点，为其子树中最小成本叶结点的成本。例如，路径 1-2-4-3-1（对应结点12）的成本为 $c_{12}+c_{24}+c_{43}+c_{31} = 10+10+9+6 = 35$。
• 成本下界函数 \hat{c}(X) 设计：
  • 公式：$\hat{c}(X) = f(X) + \hat{g}(X)$。
  • $f(X)$：已选定的路线（如 $1, X_1, \dots, X_k$）的实际成本和。
  • $\hat{g}(X)$：经过剩余结点回到1的最短距离估计。
  • 计算方法：设 S = V - \{1, X_1, \dots, X_k\} 为剩余结点集合，l_d 表示从城市 d 出发的最小边成本（不关心具体到达哪个城市）。则当 k < n-1 时，$\hat{g}(X) = l_{X_k} + \sum_{d \in S} l_d$。
  • 根结点（结点1）的下界计算实例：$f(\text{空})=0$，$S={2,3,4}$，从各点出发的最小边之和为 $10+19=29$，故 $\hat{c}(1)=29$。
• 成本上界 U：初始值可通过贪心法获得（实例从1出发通过贪心求得初始 $U=39$）。本例中未额外设计 u(X) 函数。

3. LC-分支限界法实例运行过程

• 算法维护一个优先队列（min-堆），初始根结点下界为29。
• 依次扩展 \hat{c} 最小的结点：扩展1产生2（$\hat{c}=29$）、3（$\hat{c}=34$）、4（$\hat{c}=39$，等于 U 直接舍弃）。
• 接着扩展2，产生5（$\hat{c}=33$）、6（$\hat{c}=34$）。
• 持续选择堆顶元素，当遇到叶子结点12时，发现其路线成本为35，优于当前 $U=39$，故将 U 更新为35，ans 记录为12。
• 最终，堆顶结点的 \hat{c} 值（如结点8的 $\hat{c}=35$）等于全局上界 $U$，满足退出条件，算法成功结束，最优总成本为35，路径由 ans=12 导出。

---

8.7 本章小结

1. 分支限界法与回溯法的异同点

• 相同点：
  • 同样适用于求解组合数较大的问题或多阶段决策问题。
  • 都是在解空间树上搜索答案结点。
  • 都会借助约束函数 B 进行可行性剪枝。
• 不同点：
  • 最本质的区别：E-结点的处理方式不同（回溯法是深度优先单道深入；分支限界法是一次性产生所有儿子，利用队列或堆进行跳跃式扩展）。
  • 效率差异：分支限界法可以基于成本估计函数 \hat{c} 智能选择下一个结点，在求解最优解问题时效率显著更高。
  • 存储空间：分支限界法需要额外维护一个规模可能很大的活结点表（队列或堆），而回溯法不需要，因此分支限界法通常更消耗内存。

2. 分支限界法求最优解的一般流程

• 极小化问题：目标函数作为成本函数 c \rightarrow 约束条件作为约束函数 B \rightarrow 设计下界估计函数 \hat{c}(X) \le c(X) \rightarrow 设计成本上界 U \rightarrow 结合进行限界搜索。
• 极大化问题：将目标函数取相反数转化为极小化问题；或者做镜像修改（目标函数作为 c 寻找最大成本，满足 $u \le c \le \hat{c}$，U 作为下界不断增大并杀死更小估计值的结点）。
• 剪枝的两大发生点：一是 X 进入活结点表时（接受 B 和 U 检验），二是 X 离开活结点表准备作为E-结点时（接受最新更新的 U 检验）。

3. 课程大纲要求的核心掌握点

• 掌握分支限界法的设计思想、问题特点及不同检索方式的差异。
• 掌握结点成本函数 $c$、下界估计函数 \hat{c} 的定义，并能以15-谜问题、作业调度、TSP问题为例，熟练地构造解空间、设计约束函数 $B$、计算限界值，独立设计出高效的分支限界算法并分析其复杂度。