动态规划（六）——分治优化DP 算法设计与分析 国科大

本文内容紧接动态规划（五），讨论如何优化序列对齐算法

Hirschberg算法

上文最后提到的解决方案，是维护一个OPT矩阵，那么它的空间开销就变成了O(mn)，而Hirschberg 算法通过分治策略，将序列对齐问题的空间复杂度从基础动态规划算法的O(mn)（m、n 为两个序列的长度），降低至 O(m+n)。

我们先回顾最优得分4是怎么来的：其上方的0、右侧的0、和右上的3综合得到的，实际上，它只用到了自己所在的一列和前一列。下面我们验证一下：

首先初始化了第一列和第一行，这时我们能得到第二列的所有数字吗？显然是可以的。每个数字实际上只依赖自己附近的三个数。

由此我们可知，只需要用两个一维数组存储当前得分和前一列的得分即可，将空间复杂度极大的降低了。

问题

这种方法没有存储之前的路径，虽然降低了内存开销，但会丢失回溯所需的完整矩阵信息，导致无法恢复具体的最优对齐路径（仅能得到得分）。如何解决这个问题呢？

后缀对齐替代前缀对齐

在解决这个问题前，我们先介绍如何后缀对齐替代前缀对齐，非常容易理解

实际上只是把T和S从尾到头对齐而已，这也告诉我们，序列对齐不仅可以基于 “前缀（prefixes，即序列的前 k 个字符）” 进行，也可以基于 “后缀（suffixes，即序列的后 k 个字符）” 进行，且最终能得到与前缀对齐完全一致的最优得分和对齐形式。

下面尝试用分治的方法来解决：

假设已得到最优对齐，通过以下步骤拆分问题以恢复对齐路径：

• 选取 S 的中间位置（第 n/2 位），确定该位置对齐到 T 的哪个位置（记为 q）；
• 将 S 拆分为 “前 n/2 位” 和 “后 n/2 位”，将 T 拆分为 “前 q 位” 和 “后 m-q 位”；
• 最优得分满足线性拆分关系：OPT(T,S) = OPT(T[1..q], S[1..]) + OPT(T[q+1..m], S[+1..n])

文字可能不好理解，下面用一个例子来进行演示：

核心目标：确定 S 的中间位置在 T 中对应的最优对齐位置 q，为后续分治拆分问题做准备。

首先我们确定S的一半（向下取整）是5，根据S将序列对齐分为了两个子问题，其中左侧是前缀序列对齐，右侧是后缀序列对齐。

分别计算得分，最终由绿色列可以推出紫色列。

由于最优得分满足线性拆分关系：OPT(T,S) = OPT(T[1..q], S[1..]) + OPT(T[q+1..m], S[+1..n])，因此将紫色列相加得到黄色列，最大得分用红色标出，这个值正是 S 与 T 全局对齐的最优得分 OPT(S,T)，对应的位置即为S 中间位置在 T 中的最优对齐点 q。

后续可递归执行相同逻辑，最终在低空间复杂度下得到全局最优对齐。这样就可以恢复完整的最优对齐路径。

下面再通过一个完整的递归过程来展示一下恢复

1. 对齐位置对数组 A

数组 A = [<5,4>, <3,2>, <1,1>, <4,3>, <7,6>, <6,5>, <8,7>, <9,8>]是T（记为 X）与 S（记为 Y）的字符对齐位置对：每个<a,b>表示 “T 的第 a 个字符与 S 的第 b 个字符对齐”，这些位置对是递归拆分过程中得到的子问题对齐结果。

2. 分治递归的树状拆分结构

• 根节点：对应完整序列的对齐 ——X={OCCURRENCE}（正确序列 T）、Y={OCURRANCE}（错误序列 S），对齐位置对为<5,4>（此前找到的 S 中间位置在 T 中的对齐点）。
• 子问题拆分：根节点拆分为两个子问题，再递归拆分至最小单元：
  • 左分支：X={OCCUR} 与 Y={OCUR} 对齐（位置对<3,2>），进一步拆分为 {OCC} 与 {OC}、{UR} 与 {UR} 等子问题；
  • 右分支：X={RENCE} 与 Y={RANCE} 对齐（位置对<7,6>），进一步拆分为 {RA} 与 {RE}、{NCE} 与 {NCE} 等子问题。

3. 最终最优对齐结果

所有子问题的对齐结果拼接后，得到完整的最优对齐形式：

• X' = {OCCURRENCE}\)：T（正确序列）的对齐形式（无空格）；
• Y' = {O-CURRANCE}\)：S（错误序列）的对齐形式（通过插入空格 “-” 与 T 匹配）。

这种方法极大的优化了空间复杂度，且未改变时间复杂度（仍为O(mn)）

Hirschberg 提出的 “分治技术” 并非仅适用于序列对齐问题，而是几乎可以推广到所有动态规划算法中，其分治思路具有广泛的适配性。对于任意一个 “能够计算出最优解数值” 的 DP 算法，借助 Hirschberg 的分治逻辑，通常可以在不增加原算法时间、空间复杂度的前提下，进一步构造出最优解的具体形式。

改进——J. Ian Munro 算法

该算法是对Hirschberg算法的改进，相较于之前，其额外维护了一个R矩阵（实际上每步仍然是只记录两列），来帮助快速恢复。

基于最优对齐得分 OPT[i,j]的推导来源，R_{i,j} 的取值分 4 种情况：

• 当时：R_{i,j} = i此时 j 恰好是 S 的中间列，对齐路径经过该列时对应的行号为 i。
• 当，且 OPT[i,j] 由 OPT[i-1,j] 推导（对应删除操作）：R_{i,j} = R_{i-1,j}
• 当，且 OPT[i,j] 由 OPT[i-1,j-1] 推导（对应匹配 / 突变操作）：R_{i,j} = R_{i-1,j-1}
• 当，且 OPT[i,j] 由 OPT[i,j-1] 推导（对应插入操作）：R_{i,j} = R_{i,j-1}

下面看一个例子

1. 左侧矩阵：得分矩阵（OPT 矩阵）矩阵的行对应正确序列 T（字符为O、C、C、U、R…），列对应错误序列 S（字符为O、C、U、R、R…），存储的是 “T 前 i 个字符与 S 前 j 个字符” 的最优对齐得分（即 OPT[i,j]）；其中绿色列是 S 的中间列。
2. 右侧矩阵：R 矩阵存储的是此前定义的 R_{i,j}（“T 前 i 个字符与 S 前 j 个字符的最优对齐路径，经过 S 中间列时的行号”）。矩阵中绿色部分是计算后的 R_{i,j} 值。
3. 确定初始 q：对于完整序列的对齐，通过 R 矩阵可得到：最优对齐路径经过 S 中间列时，对应的 T 的行号为 5，因此 q = 5（即 S 中间位置在 T 中的对齐位置）。

接下来与之前的解决方案一致，可以通过不断分治，来完成序列对齐的恢复。

对于序列对齐任务，衍生出非常多的优化算法，后续还有Banded DP等，将在下文进行介绍