3 LTDP

第 3 节 LINEAR-TROPICAL DYNAMIC PROGRAMMING 精读

这一节要完成三件事：

把 DP 严格写成热带矩阵乘法（LTDP 定义）
引入前驱乘积（predecessor product），并证明它对"平行向量"不敏感
给出顺序 LTDP 算法（图 2），作为第 4 节并行算法的对照基线

下面逐块拆解。

一、LTDP 定义：什么样的 DP 才算 LTDP

1. 论文原定义

A dynamic programming problem is LTDP, if (1) the subproblems can be grouped into a sequence of stages such that the solution to a subproblem in a stage only depends on the solutions in the previous stage, and (2) this dependence is linear in the tropical semiring.

两个条件：

条件 1（分层依赖）：子问题能分成若干阶段，每个阶段只依赖前一个阶段。
条件 2（热带线性）：这种依赖是热带半环下的线性关系。

2. 递推公式

$s_i[j]$ , the solution to subproblem $j$ in stage $i$ of LTDP, is given by the recurrence equation
$s_i[j] = \max_{k}(s_{i - 1}[k] + A_i[j,k]) \quad (1)$

逐项解释：

符号	含义
$i$	阶段编号
$j$	当前阶段中的子问题编号
$k$	前一阶段中的子问题编号
$s_i[j]$	阶段 $i$ 中子问题 $j$ 的解
$s_{i-1}[k]$	前一阶段中子问题 $k$ 的解
$A_i[j,k]$	从 $k$ 到 $j$ 的"转移代价/权重"，由输入决定，与解无关

核心： $s_i[j]$ 等于"前一阶段所有解 $s_{i-1}[k]$ 加上对应权重 $A_i[j,k]$ "中的最大值。

3. 为什么这就是热带矩阵-向量乘法

把 $s_i$ 看成一个列向量， $A_i$ 看成一个矩阵。热带矩阵-向量乘法的定义是：

(A_i\odot\vec{s}_{i-1})[j]=\max_k\big(A_i[j,k]+\vec{s}_{i-1}[k]\big)

对比公式 (1)：

s_i[j]=\max_k\big(s_{i-1}[k]+A_i[j,k]\big)

两者逐项完全相同（加法可交换， $s_{i-1}[k]+A_i[j,k]=A_i[j,k]+s_{i-1}[k]$ ）。所以：

\boxed{\vec{s}_i=A_i\odot\vec{s}_{i-1}} \quad (2)

这就是"DP 写成热带矩阵乘法"的全部内容。 没有任何近似，是严格等价。

4. 一个具体例子：LCS 怎么变成 LTDP

以 LCS 为例，递推是：

C_{i,j}=\max\begin{cases} C_{i-1,j}+0\\ C_{i,j-1}+0\\ C_{i-1,j-1}+\delta_{i,j} \end{cases}

其中 $\delta_{i,j}=1$ 若两字符相同，否则 $0$ 。

分组：把每一行（或每一列）作为一个阶段。比如固定 $i$ ，让 $j$ 变化，那么阶段 $i$ 的向量是 $\vec{s}_i=[C_{i,0},C_{i,1},\ldots,C_{i,n}]^{\mathrm{T}}$ 。

问题： $C_{i,j}$ 依赖 $C_{i,j-1}$ ，这是同一阶段内的依赖，不满足"只依赖前一阶段"。

解决：把递推"展开"。 $C_{i,j}$ 依赖 $C_{i,j-1}$ ，而 $C_{i,j-1}$ 又依赖 $C_{i,j-2}$ ……最终 $C_{i,j}$ 可以写成只依赖第 $i-1$ 行的形式。展开后， $A_i[j,k]$ 就编码了"从第 $i-1$ 行的第 $k$ 个位置到第 $i$ 行的第 $j$ 个位置"的最优路径权重。

论文在 Section 6 说 LCS 有两种分组方式（反对角线分组、行/列分组），行分组就需要这种展开。这里不展开细节，只需理解：LTDP 定义不要求原始 DP 天然分层，允许通过展开/重分组把同阶段内依赖消掉。

5. 两个容易误解的点

(a) "线性"不是普通线性

这里说的"线性"是热带半环下的线性，即"max 和 +"意义下的线性，不是普通实数域的线性。所以不要用" $s_i=\sum A_{ij}s_j$ "去理解，而是" $s_i[j]=\max_k(s_{i-1}[k]+A_i[j,k])$ "。

(b) $A_i$ 不是"状态转移概率"

$A_i[j,k]$ 只是一个常数权重，由输入数据决定，与当前解无关。它编码的是"从 $k$ 到 $j$ 这一步的代价/收益"。在 Viterbi 里它是 log 转移概率，在 LCS 里它是 0 或 $\delta_{i,j}$ ，在序列比对里它是匹配分数或罚分。

6. 初始向量 $\vec{s}_0$

Also, $\vec{s}_0$ is the initial solution vector obtained from the base case of the recurrence equation.

$\vec{s}_0$ 是 DP 的边界条件。比如 LCS 中 $C_{0,j}=0$ 、 $C_{i,0}=0$ ，就是 $\vec{s}_0$ 的分量。整个计算从 $\vec{s}_0$ 出发，依次乘 $A_1,A_2,\ldots,A_n$ 。

二、前驱乘积：为什么需要它

1. 问题背景：DP 不只要"值"，还要"路径"

LTDP 算完所有 $\vec{s}_i$ 后，只得到了每个子问题的最优值。但很多 DP 问题最终要的是最优解本身（比如 LCS 的具体子序列、Viterbi 的具体状态路径）。要还原解，需要知道每个子问题的最优值是从哪个前驱子问题来的。

2. 前驱的定义

A predecessor of a subproblem is the subproblem for which the maximum in Equation (1) is reached.

在公式 (1) 中：

s_i[j]=\max_k(s_{i-1}[k]+A_i[j,k])

取到最大值的那个 $k$ ，就是子问题 $j$ 在阶段 $i$ 的前驱。

3. 前驱乘积的形式定义

We define the predecessor product of a matrix $A$ and a vector $\vec{s}$ as the vector $A\star \vec{s}$ such that
$(A\star \vec{s})[j] = \arg \max_{k}(\vec{s}[k] + A[j,k]).$

对比矩阵乘法：

(A\odot\vec{s})[j]=\max_k(\vec{s}[k]+A[j,k])

(A\star\vec{s})[j]=\arg\max_k(\vec{s}[k]+A[j,k])

唯一区别： $\odot$ 返回最大值， $\star$ 返回取到最大值的下标 $k$ 。

4. 一个手算例子

设

A=\begin{pmatrix}1&2\\3&0\end{pmatrix},\quad \vec{s}=\begin{pmatrix}5\\4\end{pmatrix}

计算 $A\star\vec{s}$ ：

$j=0$ ： $\max(A[0,0]+s[0],\ A[0,1]+s[1])=\max(1+5,\ 2+4)=\max(6,6)=6$ 。平局！论文说"ties in arg max are broken deterministically"，假设取较小下标，则 $\arg\max=0$ 。
$j=1$ ： $\max(A[1,0]+s[0],\ A[1,1]+s[1])=\max(3+5,\ 0+4)=\max(8,4)=8$ 。 $\arg\max=0$ 。

所以

A\star\vec{s}=\begin{pmatrix}0\\0\end{pmatrix}

而

A\odot\vec{s}=\begin{pmatrix}6\\8\end{pmatrix}

$\star$ 给出"走哪条路"， $\odot$ 给出"走这条路的值"。

5. 平局处理

We assume that ties in arg max are broken deterministically.

平局时必须有一致的规则（比如总取最小下标），否则并行计算时不同处理器可能选出不同前驱，导致结果不一致。这个假设在后面并行算法里很重要。

三、Lemma 3.1：前驱乘积对平行向量不敏感

这是第 3 节最重要的引理，也是第 4 节并行算法能成立的最后一环。

1. 引理内容

LEMMA 3.1. $\vec{u}\parallel \vec{v}\Rightarrow \forall A:A\star \vec{u} = A\star \vec{v}.$

翻译：如果两个向量平行（只差一个常数），那么对任意矩阵 $A$ ，它们的前驱乘积完全相同。

2. 证明

This follows from the fact that parallel vectors in the tropical semiring differ by a constant and that arg max is invariant when a constant is added to all its arguments.

展开证明：

设 $\vec{u}\parallel\vec{v}$ ，则存在常数 $c$ 使得

\vec{u}[k]=\vec{v}[k]+c\quad\forall k

现在计算 $(A\star\vec{u})[j]$ ：

(A\star\vec{u})[j]=\arg\max_k\big(\vec{u}[k]+A[j,k]\big)

代入 $\vec{u}[k]=\vec{v}[k]+c$ ：

=\arg\max_k\big(\vec{v}[k]+c+A[j,k]\big)

=\arg\max_k\big(\vec{v}[k]+A[j,k]+c\big)

因为 $c$ 是与 $k$ 无关的常数，给所有候选值加同一个 $c$ 不改变谁最大：

=\arg\max_k\big(\vec{v}[k]+A[j,k]\big)=(A\star\vec{v})[j]

所以 $A\star\vec{u}=A\star\vec{v}$ 。 $\square$

3. 直观理解

前驱乘积只关心"谁最大"，不关心"最大值是多少"。

平行向量 $\vec{u}$ 和 $\vec{v}$ 的每个分量都差同一个常数 $c$ 。
给所有候选值同时加 $c$ ，最大值的位置不变。
所以前驱相同。

类比：三个人比赛跑步，给每个人同时加 10 秒，排名不变。前驱乘积只记录"排名"，不记录"成绩"。

4. 为什么这是并行算法的"最后一环"

回顾第 4 节的思路：

秩收敛保证：从任意初始向量出发，经过足够多阶段，得到的解向量 $\vec{s}_i'$ 平行于真实解 $\vec{s}_i$ 。
但 $\vec{s}_i'\neq\vec{s}_i$ ，数值不同。
如果最终要的是前驱路径（LCS 的具体子序列、Viterbi 的具体路径），平行向量够不够？

Lemma 3.1 回答：够。 因为前驱乘积对平行向量不敏感，所以用 $\vec{s}_i'$ 算出的前驱和用 $\vec{s}_i$ 算出的前驱完全一样。最终路径也完全一样。

没有 Lemma 3.1，秩收敛只能保证"值差一个常数"，不能保证"路径正确"，整个方法就不成立。 这是第 3 节埋下的最关键伏笔。

5. 注意：Lemma 3.1 只对 $\star$ 成立，对 $\odot$ 不成立

\vec{u}\parallel\vec{v}\Rightarrow A\star\vec{u}=A\star\vec{v}\quad\checkmark

\vec{u}\parallel\vec{v}\Rightarrow A\odot\vec{u}=A\odot\vec{v}\quad\times

因为 $A\odot\vec{u}$ 和 $A\odot\vec{v}$ 也会差一个常数 $c$ ，但数值不同。所以：

值（ $\odot$ ）会差常数，需要修正。
路径（ $\star$ ）完全相同，不需要修正。

这就是为什么第 4 节的 fix-up 阶段只修正"值"，不修正"路径"。

四、顺序 LTDP 算法（图 2）：并行算法的对照基线

1. 论文给出的伪代码

LTDP_Seq (vector s0, matrix A1..An) {
 vector pred[1..n]; vector res;
 // forward
 s = s0;
 for i in (1..n) {
   pred[i] = A_i ★ s;   // pred[i] = p_i
   s = A_i ⊙ s;          // s = s_i
 }
 // backward
res[n+1] = 0;           // res = r
for i in (n..1) {
  res[i] = pred[i][res[i+1]];
return res;
}

注：论文原文伪代码有 OCR 错误（A1 应为 A_i，A1 * s 应为 A_i ★ s 和 A_i ⊙ s），这里按语义修正。

2. 逐行解释

输入：

$\vec{s}_0$ ：初始解向量。
$A_1,\ldots,A_n$ ：各阶段的变换矩阵。

Forward 阶段（第 4–8 行）：

行	操作	含义
4	`s = s0`	从初始向量开始
5	`for i in (1..n)`	依次处理每个阶段
6	`pred[i] = A_i ★ s`	计算阶段 $i$ 的前驱：每个子问题的最优前驱下标
7	`s = A_i ⊙ s`	计算阶段 $i$ 的解向量

注意第 6 行和第 7 行用的是同一个 s（即 $\vec{s}_{i-1}$ ），所以：

\vec{p}_i=A_i\star\vec{s}_{i-1},\quad \vec{s}_i=A_i\odot\vec{s}_{i-1}

先算前驱，再更新解向量。

Backward 阶段（第 10–13 行）：

行	操作	含义
10	`res[n+1] = 0`	从最后一个阶段的第 0 个子问题开始回溯
11	`for i in (n..1)`	从后往前遍历阶段
12	`res[i] = pred[i][res[i+1]]`	查表：阶段 $i+1$ 的前驱是 `res[i+1]`，那么阶段 $i$ 的前驱就是 `pred[i][res[i+1]]`

第 12 行是关键：pred[i] 是一个向量，pred[i][res[i+1]] 表示"取 pred[i] 的第 res[i+1] 个元素"。这实现了"沿前驱链回溯"。

3. 为什么假设"最后一个阶段的第 0 个子问题"包含答案

The algorithm assumes that the first subproblem in the last stage, $\vec{v}_n[0]$ , contains the desired solution to the underlying optimization problem.

不同 DP 问题的"答案位置"不同：

LCS：答案是表格右下角 $C_{m,n}$ 。通过重分组/加辅助阶段，可以把答案挪到"最后一个阶段的第 0 个位置"。
Viterbi：答案是最后一列的最大值。论文 Section 6 说，加一个额外阶段 $n+1$ ，每个子问题都是阶段 $n$ 的最大值，这样答案就在阶段 $n+1$ 的第 0 个位置。
Smith-Waterman：答案是全表最大值。加一个"running maximum"子问题，跟踪当前阶段及之前所有阶段的最大值。

所以这个假设不是限制，而是一种规范化：任何 LTDP 都可以通过加辅助阶段/辅助子问题，把答案放到固定位置。

4. 算法复杂度

Forward： $n$ 次矩阵-向量乘法 + $n$ 次前驱乘积。
Backward： $n$ 次查表。
总时间 $O(n\cdot \text{cost of one matrix-vector multiply})$ 。

这是纯顺序的：阶段 $i$ 必须等阶段 $i-1$ 算完。第 4 节要打破的就是这个顺序依赖。

5. 实现细节被隐藏了

An implementation does not need to represent the solutions in a stage as a vector and perform matrix-vector operations. It might statically know that the current solution depends on some of the subproblems in the previous stage (a sparse matrix) and only access those.

伪代码用"稠密矩阵-向量乘法"表达，但实际实现中：

$A_i$ 通常是稀疏的（LCS 每格只依赖 3 个邻居）。
实现可以只访问非零项，不真的构造矩阵。
可以用波前并行加速阶段内计算。

这些实现细节与"跨阶段并行"是正交的，第 4 节的并行方法不关心阶段内怎么算。

五、这一节的逻辑链

把第 3 节串起来：

LTDP 定义
  │  条件1：阶段间只依赖前一阶段
  │  条件2：依赖是热带线性的
  ↓
递推公式 s_i[j] = max_k(s_{i-1}[k] + A_i[j,k])
  │  逐项对应热带矩阵-向量乘法
  ↓
s_i = A_i ⊙ s_{i-1}          （值）
p_i = A_i ★ s_{i-1}          （前驱）
  │
  ├──→ Lemma 3.1：平行向量前驱相同
  │       ū∥v̄ ⇒ A★ū = A★v̄
  │       这是第 4 节"秩收敛后路径仍正确"的依据
  │
  └──→ 顺序算法（图 2）
          Forward：逐阶段算 p_i 和 s_i
          Backward：沿 p_i 回溯
          这是第 4 节并行算法的对照基线

六、每个概念"后面会用在哪里"

本节概念	后续用途
LTDP 定义（公式 1）	第 4 节所有并行方法的前提；第 6 节验证四个问题属于 LTDP
矩阵形式 $\vec{s}_i=A_i\odot\vec{s}_{i-1}$	第 4.1 节：把 $\vec{s}_n$ 写成 $A_n\cdots A_1\odot\vec{s}_0$ ，用结合律拆开
前驱乘积 $A\star\vec{s}$	第 4.6 节并行 backward 阶段；第 5 节 Delta 方法也用它
Lemma 3.1（平行→前驱相同）	第 4.2 节秩收敛论证的最后一环；没有它，并行算法只能算值不能算路径
顺序算法图 2	第 4.3 节图 3(a) 的对照；第 4.4 节 Rank-1 方法就是把它并行化
"答案在最后阶段第 0 个位置"假设	第 6 节 Viterbi/Smith-Waterman 通过加辅助阶段满足这个假设

七、最容易踩的坑

$\odot$ 和 $\star$ 的区别。 $\odot$ 返回值（max 的结果）， $\star$ 返回下标（argmax 的结果）。两者输入相同，输出类型不同。读伪代码时注意第 6 行用 $\star$ 、第 7 行用 $\odot$ 。
Lemma 3.1 只对 $\star$ 成立。平行向量代入 $\odot$ 会得到"平行但不同"的结果，代入 $\star$ 才得到"完全相同"的结果。这是"值需修正、路径不需修正"的根源。
"线性"是热带线性。不是普通线性代数意义下的线性。不要试图用"矩阵的列空间"去理解 $A_i$ ，要用"max-plus 加权转移"去理解。
$A_i$ 与解无关。 $A_i[j,k]$ 完全由输入决定，计算过程中不变。变的是 $\vec{s}_{i-1}$ 。所以 $A_i$ 可以预先算好、稀疏存储。
"答案在最后阶段第 0 个位置"是规范化，不是限制。任何 LTDP 都能通过加辅助阶段满足它。Viterbi 加一个"取最大值"阶段，Smith-Waterman 加一个"running max"子问题。
平局必须确定性处理。否则并行时不同处理器可能选出不同前驱，导致结果不一致。论文明确假设"ties in arg max are broken deterministically"。
顺序算法不是"低效算法"。它可以用波前并行加速阶段内计算。第 4 节要加的是跨阶段并行，不是替代阶段内并行。两者正交、可叠加。

八、一句话总结第 3 节

LTDP 就是"阶段间只依赖前一阶段、且依赖是热带线性"的 DP，其递推严格等价于热带矩阵-向量乘法 $\vec{s}_i=A_i\odot\vec{s}_{i-1}$ ；前驱乘积 $A\star\vec{s}$ 返回 argmax 下标，且对平行向量完全不敏感（Lemma 3.1），这保证了"从任意初始向量出发、只要最终解平行于真实解，前驱路径就完全正确"；顺序算法先 Forward 算值和前驱、再 Backward 沿前驱回溯，是第 4 节并行算法的对照基线。

下一步进入 第 4 节 THE PARALLEL RANK-1 METHOD。这是全文的核心章节，需要重点理解：

4.1 打破阶段依赖：为什么直接做矩阵-矩阵乘法不实用
4.2 秩收敛：为什么从任意初始向量出发，结果会平行于真实解
4.3–4.4 Rank-1 方法：Forward 阶段怎么并行、fix-up 循环怎么工作
4.5 All-Non-Zero 不变性：为什么初始向量不能有 $-\infty$
4.6 并行 Backward：怎么用同样的思路并行回溯
4.7 秩收敛的直观解释：高速公路类比

其中 4.2 和 4.4 是难点，需要结合第 2、3 节的工具（秩不增、Lemma 2.2、Lemma 3.1）一起理解。

第 3 节 LINEAR-TROPICAL DYNAMIC PROGRAMMING 精读

一、LTDP 定义：什么样的 DP 才算 LTDP​

1. 论文原定义​

2. 递推公式​

3. 为什么这就是热带矩阵-向量乘法​

4. 一个具体例子：LCS 怎么变成 LTDP​

5. 两个容易误解的点​

6. 初始向量 s⃗0\vec{s}_0s0​​

二、前驱乘积：为什么需要它​

1. 问题背景：DP 不只要"值"，还要"路径"​

2. 前驱的定义​

3. 前驱乘积的形式定义​

4. 一个手算例子​

5. 平局处理​

三、Lemma 3.1：前驱乘积对平行向量不敏感​

1. 引理内容​

2. 证明​

3. 直观理解​

4. 为什么这是并行算法的"最后一环"​

5. 注意：Lemma 3.1 只对 ⋆\star⋆ 成立，对 ⊙\odot⊙ 不成立​

四、顺序 LTDP 算法（图 2）：并行算法的对照基线​

1. 论文给出的伪代码​

2. 逐行解释​

3. 为什么假设"最后一个阶段的第 0 个子问题"包含答案​

4. 算法复杂度​

5. 实现细节被隐藏了​

五、这一节的逻辑链​

六、每个概念"后面会用在哪里"​

七、最容易踩的坑​

八、一句话总结第 3 节​