第 59A 章热带半环基础¶

前置：图论基础 (Ch27) · 矩阵运算 (Ch02) · 最优化基础 (Ch25)

本章脉络：热带半环 $(\mathbb{R} \cup \{\infty\}, \oplus, \otimes)$ 定义 $\to$ 运算规则：加法为 $\min$，乘法为标量加法 $\to$ 代数性质（单位元、分配律、无加法逆元） $\to$ 热带矩阵乘法 $\to$ 热带线性方程组 $\to$ 热带特征值与特征向量（最大平均环路） $\to$ Maslov 去量子化视角 $\to$ 应用：最短路径问题（Bellman-Ford 算法的代数本质）、动态规划、排程理论

延伸：热带半环是“将加法变为求极值、将乘法变为加法”的奇异世界；它将离散的最优化问题（如最短路径）完美转化为线性的代数问题，是热带几何 (Ch59B) 的纯代数地基

如果我们将传统的算术规则修改为：加法取两数中的较小者，乘法变为两数的加法，会发生什么？欢迎来到热带半环（Tropical Semiring，又称 $(\min, +)$ 代数）。在这个世界里，多项式变成了分段线性凸函数，而矩阵乘法直接对应于图中的路径搜索。本章将探索这一连接代数、几何与组合最优化的独特领域。

59A.1 热带半环的定义¶

定义 59A.1 (热带半环 $\mathbb{T}$)

定义实数集扩充符号 $\infty$ 为热带半环 $\mathbb{T} = \mathbb{R} \cup \{\infty\}$。其上的基本运算定义为： 1. 热带加法 $\oplus$：$a \oplus b = \min(a, b)$。 2. 热带乘法 $\otimes$：$a \otimes b = a + b$。 单位元：加法单位元为 $\infty$（因为 $\min(a, \infty)=a$），乘法单位元为 $0$（因为 $a+0=a$）。

59A.2 热带矩阵运算¶

定义 59A.2 (热带矩阵乘法)

设 $A, B$ 是热带矩阵。它们的乘积 $C = A \otimes B$ 的条目定义为： $$c_{ij} = \bigoplus_{k=1}^n (a_{ik} \otimes b_{kj}) = \min_{k} \{a_{ik} + b_{kj}\}$$ 物理意义：若 $A$ 是图的边权矩阵，则 $A \otimes B$ 对应于经过中间节点的最短路径权重。

59A.3 热带特征值¶

定理 59A.1 (特征值与环路)

方阵 $A$ 的热带特征值 $\lambda$ 满足 $A \otimes \mathbf{v} = \lambda \otimes \mathbf{v}$。对于连通图，该特征值是唯一的，且等于图中最大平均环路权重的负值（或在 $\max$ 代数下为最大平均环路）。

59A.4 Maslov 去量子化¶

对数变换视角

热带半环可以看作是标准算术在对数尺度下的极限： $$\lim_{h \to 0} h \ln(e^{a/h} + e^{b/h}) = \max(a, b)$$ 这一过程称为 Maslov 去量子化，揭示了极值问题与经典分析之间的深层连续性。

练习题¶

参考答案

 $3 \otimes 5 = 3 + 5 = 8$。

参考答案

 第二项：$\min(5+1, 1+3) = 4$。

结果为 $(1, 4)^T$。

参考答案

本章小结¶

热带半环是处理极值结构的终极代数工具：

****：通过将“求和”升级为“选择”，热带半环将非线性的最优化逻辑固化为线性的代数演算，实现了计算范式的转换。

****：热带矩阵幂完美封装了所有路径搜索算法，证明了图论中的动态规划本质上是特定代数结构下的矩阵乘法。

****：作为经典代数的“冰冷极限”，热带半环揭示了离散组合结构如何从连续的解析函数中脱颖而出，为解决 NP-困难问题提供了代数上的启发。

第 59A 章 热带半环基础¶

59A.1 热带半环的定义¶

59A.2 热带矩阵运算¶

59A.3 热带特征值¶

59A.4 Maslov 去量子化¶

练习题¶

本章小结¶

第 59A 章热带半环基础¶