动态规划的表示几何

# 论动态规划的表示几何

来源：https://arxiv.org/html/2608.25034

Richard F\. M\. Lim  
邮箱：[rlim@bowdoin\.edu](mailto:rlim@bowdoin\.edu)  
所属机构：缅因州不伦瑞克市鲍登学院数学与计算机科学系  
所属机构：加利福尼亚州蒙特雷市海军研究生院运筹学系

Ruriko Yoshida  
邮箱：[ry@math\.aau\.dk](mailto:ry@math\.aau\.dk)  
所属机构：丹麦奥尔堡大学数学科学系  
所属机构：加利福尼亚州蒙特雷市海军研究生院运筹学系

###### 摘要

标准的神经网络架构常常无法泛化到动态规划（DP）目标的更长输入。我们从几何角度探究其困难所在。每个有限的最小加（min-plus）动态规划都是一个有向无环图（DAG）上的最短路径问题，等价于一个热带多项式，其扩展牛顿多面体编码了哪条路径获胜的决策边界。我们证明这三种描述（图、多项式、多面体）在两个层面——形式多项式及其计算函数——上构成同构的半环，并通过刻画所有结构冗余的运算相互关联。然后我们从几何上解决长度泛化问题：长度 T 的决策边界是否决定了长度 T+1 的决策边界？我们提出两个结构性的否定结果。该半环的两种原生降维方式（将变量分别设为各自的单位元）既非单射，在动态规划中也不总是封闭的。串联和并联组合无法从小子DAG构建出所有DAG拓扑结构，且即使是所有仅涉及终端的操作也无法捕获所有的DP组合。

## 1 引言

动态规划由一个不依赖输入规模的递归式定义，因此真正学会了该递归式的模型应在任意长度上都能运行。标准序列架构却做不到。在组合优化目标上训练后，它们能拟合训练长度，但超出后性能急剧下降，这一失败在循环模型和注意力模型中均有记录，且对规模变化具有鲁棒性（Delétang 等人, 2023；Anil 等人, 2022）。热带注意力（Tropical Attention）（Hashemi 等人, 2025）是一个显著的例外；它用最大加（max-plus，即热带）运算（\(\max, +\)）替换加法和乘法，在经典DP问题上实现了强大的长度分布外（OOD）泛化能力。

该前提是经典的。展开后，每个有限的最小加动态规划都是：(1) 一个单源 \(s\) 单汇 \(z\) 的决策DAG上的单对最短路径问题，我们称之为*双端*（Bellman, 1957; Gondran 和 Minoux, 1979）；(2) 一个热带多项式（Joswig, 2021）。为与最短路径公式对齐，我们始终在 \((\min, +)\) 半环 \(\mathbb{T} = \mathbb{R} \cup \{+\infty\}\) 下工作，它在取反下等价于 \((\max, +)\)（Joswig, 2021）。当我们强调半环结构时，记 \(a \oplus b = \min(a, b)\) 和 \(a \odot b = a + b\)。

我们的工作聚焦于长度泛化：一个学习者观察变量数最多为 T 的小图，必须预测之后的所有图。因此，我们通过以下问题来探究这是否可能：(1) 动态规划中何种代数结构使得算法能在任意长度上工作？(2) 此结构是否允许我们从较小实例推断较大实例？

将双端DAG串联组合会增加其路径长度；并联组合则取最小值（图3 见附录A）。我们首先通过三重半环同构（第2节）形式化图、多项式与几何之间的关系。多个*形式*多项式可能映射到相同的*函数*——\(\min(0, x, 2x) = \min(0, 2x)\) 对所有 \(x\) 成立，尽管它们的支集不同——因此我们在两个层面构建此形式化框架，并通过同余商关联它们。图的结构比其多项式更丰富，因此我们为每个热带多项式提供一个规范的*去共享*标准形，并列出遍历DAG等价类的一系列不变运算（第3节）。

将较大实例与较小实例关联的一个自然方法是在半环单位元处进行代换：将变量设为 \(+\infty\) 会将其从最短路径或背包问题实例中移除，而设为 \(0\) 则会将其从最小子数组或指派问题实例中移除。我们采用上述框架，从图、多项式、多面体以及*决策边界* \(\mathcal{T}(f)\)（称为*热带超曲面*（Zhang 等人, 2018））的角度，刻画代换下的长度恢复特性。我们在第4节证明，两种代换在DP中并非总是封闭的，且即使封闭时也无法恢复长度：第 \(T\) 个实例无法决定第 \(T+1\) 个实例。最后，第5节将串联和并联组合识别为决策DAG上Bellman方程的两面，并揭示了一种两层的拓扑不充分性：它们共同无法生成所有仅涉及终端的操作拓扑，而仅涉及终端的操作也无法捕获所有的DP组合。

## 2 三重性：一个问题，三种语言

附录B详述了全文所用的热带几何背景。一个 \(d\) 变量的*形式热带多项式*是若干单项式的有限热带和，\(f(x) = \bigoplus_{\alpha} c_{\alpha} \odot x^{\odot \alpha} = \min_{\alpha} (c_{\alpha} + \langle \alpha, x \rangle)\)，其中指数 \(\alpha \in \mathbb{Z}_{\geq 0}^d\)，系数 \(c_{\alpha} \in \mathbb{T}\)（\(c_{\alpha} = +\infty\) 表示该项缺失）。其*支集*为 \(S(f) = \{\alpha : c_{\alpha} \neq +\infty\}\)，其*提升支集* \(\widehat{S}(f) = \{(\alpha, c_{\alpha}) : \alpha \in S(f)\}\) 将每个点提升到其系数高度。共享相同指数的项仅保留较小的系数，\((c \oplus c') \odot x^{\odot \alpha}\)；称此按指数最小化为 \(\backslash \text{vmin}\)（垂直最小值），并称 \(f\) 在经此约化、每个指数仅有一个系数后即处于*标准形*。标准形提升支集 \(\mathcal{L}_d\)（\(\mathbb{Z}_{\geq 0}^d \times \mathbb{R}\) 的有限子集，每个指数上方至多一个点）在 \(\backslash \text{vmin}(\cdot \cup \cdot)\) 和闵可夫斯基加法下构成一个交换幂等半环（命题9）。*扩展牛顿多面体*为 \(\Gamma(f) = \operatorname{conv}(\widehat{S}(f)) + \mathbb{R}_{\geq 0} \, e_{d+1}\)，即提升支集的凸包向上延伸。两个多项式计算相同的函数当且仅当它们的扩展牛顿多面体一致（Joswig, 2021）。因此，凸性是第二个商，而 \(\backslash \text{vmin}\) 变为 \(\operatorname{conv}\)。通常的*牛顿多面体* \(\mathcal{N}(f) = \operatorname{conv}(S(f))\) 是其垂直投影，由单项式构造但不依赖其系数。

每个双端加权DAG \(G\) 计算一个最小加*路径多项式*。可通过枚举从源 \(s\) 到汇 \(z\) 的路径 \(\pi\) 来构造：\(f_G = \min_{\pi: s \to z} \sum_{e \in \pi} w_e\)，即 \(s\) 到 \(z\) 路径的最小值，结果处于标准形。对于DAG \(A\) 和 \(B\)，有 \(f_{A;B} = f_A + f_B\) 且 \(f_{A \| B} = \min(f_A, f_B)\)（命题14）。然而，两个图可能拓扑不同但计算出完全相同的最短路径函数，因此我们定义等价关系以精确消除此冗余：\(G \approx_{\mathrm{f}} G'\) 当且仅当 \(\widehat{S}(f_G) = \widehat{S}(f_{G'})\)，且 \(G \approx_{\mathrm{v}} G'\) 当且仅当 \(f_G, f_{G'}\) 计算相同的函数。

两者都是同余关系（与 \(\|; ;\) 兼容）。以下定理表明，每个商产生的半环与其关联的多项式和多面体同构：在每个层面，图、代数和几何是*相同的*半环。

###### 定理 1。

下述交换幂等半环的图表可交换；水平映射是同构，垂直映射是满同态。

\[\begin{CD}
\mathrm{DAGs}/\approx_{\mathrm{f}} @>>>{\text{formal trop. polynomials}}>> \mathcal{L}_d \\
@VVV @VVV \\
\mathrm{DAGs}/\approx_{\mathrm{v}} @>>> \mathbb{T}^d \to \mathbb{T}
\end{CD}\]

\[\begin{CD}
(\|; ;) @. (\min, +) @. (\backslash \text{vmin}(\cdot \cup \cdot), +) \\
@. @. \\
(\|; ;) @. (\min, +) @. (\operatorname{conv}(\cdot \cup \cdot), +)
\end{CD}\]

映射关系：  
\([G] \mapsto f_G \cong f \mapsto \widehat{S}(f)\)  
\([G] \mapsto f_G \cong f \mapsto \Gamma(f)\)  
\(\approx_{\mathrm{v}}\) 同函数  
\(S \mapsto \operatorname{conv}(S) + \mathbb{R}_{\geq 0} \, e_{d+1}\)

证明见附录D。实际推论是，一个论断可在三种语言中最易于表述和检验的那种中进行，然后转换到其他语言。

## 3 DAG等价上的不变运算完整演算

我们现在给出关联两个 \(\approx\) 等价图的运算。*去共享标准形* \(D_{\mathrm{f}}(G)\) 是为 \(f_G\) 的每个单项式提供其自身 \(s\) 到 \(z\) 路径的平行链束，边按变量顺序排列：这是多项式作为单项式之 \(\min\) 的图语言规范形。然后通过删除被支配的链（中值删除）得到*函数标准形* \(D_{\mathrm{v}}(G)\)。四个局部运算，每个实现一个半环性质（附录E表1），可将任何图化归到这些标准形。

###### 定理 2。

对所有双端DAG \(G, G'\)：

- (i) *约化*：一系列形式化操作可将 \(G\) 运到 \(D_{\mathrm{f}}(G)\)，每个路径交点使用一次顶点分裂（引理16）。然后，中值删除（引理18）将 \(D_{\mathrm{f}}(G)\) 运到 \(D_{\mathrm{v}}(G)\)。
- (ii) *规范性*：\(D_{\mathrm{f}}(G) = D_{\mathrm{f}}(G')\) 当且仅当 \(G \approx_{\mathrm{f}} G'\)，且 \(D_{\mathrm{v}}(G) = D_{\mathrm{v}}(G')\) 当且仅当 \(G \approx_{\mathrm{v}} G'\)；\(D_{\mathrm{v}}(G)\) 的链正是 \(\Gamma(f_G)\) 的顶点。因此，两个同余关系都是可判定的。

连通性随之而来：两个图通过形式化操作相连当且仅当它们 \(\approx_{\mathrm{f}}\)，通过形式化操作加中值删除相连当且仅当它们 \(\approx_{\mathrm{v}}\)，因为每侧都可以约化到其标准形。完整论证在附录E。

## 4 代换几何

为了关联长度，我们需要一个在同余类上、跨三种语言定义良好且能减少变量数的运算。半环提供两种单位元代换：记 \(P_i\) 为 \(x_i \mapsto +\infty\)（\(\min\) 单位元），\(Q_i\) 为 \(x_i \mapsto 0\)（\(+\) 单位元）。在一个域上，两个切片加上减法可恢复对一个坐标的仿射依赖；热带语境中没有减法，因此一个切片只能限制。这种限制是否足够？我们提出两种识别失败的机制。

###### 命题 3。

设 \(f_G\) 为 \(t+1\) 个变量的热带多项式。记 \(\pi_i\) 为删除坐标 \(i\)，\(\hat{\pi}_i\) 为其保高度的提升，则 \(P_i\) 和 \(Q_i\) 通过跨三种语言的单一变换作用，且 \(Q_i(f_G) \leq P_i(f_G)\) 逐点成立（一个面位于阴影内部）：

\[\begin{CD}
x_i \mapsto +\infty @. \text{删除所有 } x_i \text{ 边} @. \text{限制到忽略位置 } i \text{ 的策略} \\
x_i \mapsto 0 @. \text{将所有 } x_i \text{ 边重新加权为 } 0, \text{ 然后合并} @. \text{在 } x_i=0 \text{ 处切片穿过边界}
\end{CD}\]

两行图分别承载了开篇段落的两条路径：对于 \(P_i\)，“删除所有 \(x_i\) 边”下降到同余类；对于 \(Q_i\)，“将所有 \(x_i\) 边重新加权为 \(0\)，然后合并”是去共享规范形上的规则，因为在一般图上收缩可能创建或破坏 \(s\) 到 \(z\) 路径。超曲面行读取热带超曲面 \(\mathcal{T}(f_G)\)（DP的决策边界，第1节；Zhang 等人, 2018）上的相同运算：\(P_i\) 限制到忽略位置 \(i\) 的策略，而 \(Q_i\) 在 \(x_i=0\) 处切片穿过边界。两种代换均非单射，且偶尔不*封闭*；在图1中，\(P_i\) 或 \(Q_i\) 均未将真子集实例映射到真子集实例。精确的纤维在推论21（附录F）中计算。

图示（略，参见原文图表）：两个长度3的问题，任何代换都无法区分。(L) 最小子集和，支集 \(\{0,1\}^3\)；(R) 同样但仅限于真子集，支集 \(\{0,1\}^3 \setminus \{(1,1,1)\}\)。中间面板显示决策边界（正半轴在后，虚线）。全1单项式不在坐标面上且在投影下冗余，因此 \(P_3\) 和 \(Q_3\) 应用于任一问题都产生相同的长度2对象（底部）。

## 5 超越……

（后续内容未提供，翻译至当前给定部分）