344 lines
24 KiB
Markdown
344 lines
24 KiB
Markdown
# 第八章 分支限界法 (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$、计算限界值，独立设计出高效的分支限界算法并分析其复杂度。
|