跳转至

第 21 章 归约与分解

原作：Josh Hug，UC Berkeley CS61B Spring 2021 配套读本。
中文翻译版，仅供非商业学习；采用 CC BY-NC-SA 4.0 许可。
原始网站：https://joshhug.gitbooks.io/hug61b/content/

21.1 拓扑排序与 DAG

到目前为止，我们学习了编程实践、IDE、数据结构设计、渐近分析、各种 ADT 的实现，以及图算法。这些知识的重要价值之一，是许多现实问题都可以被建模成我们已经会解决的标准结构。

本章将练习如何把复杂问题转化为已有算法能够处理的形式。

拓扑排序

假设有一组任务，其中某些任务必须在另一些任务之前完成。如何排列全部任务，使所有先决条件都得到满足？

把每个任务表示为顶点；若任务 \(v\) 必须先于任务 \(w\)，就添加有向边：

\[v\rightarrow w\]

问题于是转化为拓扑排序（topological sort）。

拓扑排序是顶点的一种线性顺序，使每条有向边 \(u\rightarrow v\) 的起点 \(u\) 都出现在终点 \(v\) 之前。

问题 21.1.1：给出图中的合法拓扑序。

示例答案包括：

[D, B, A, E, C, F]
[E, D, C, B, A, F]

拓扑序通常不唯一。

哪些图可以拓扑排序？

考虑含有有向环的图：

若 D 必须在 B 前，B 又必须经过一系列依赖回到 D 前，就不可能安排任何线性顺序。无向边也可以看作双向依赖，会立即形成长度为 2 的有向环。

因此拓扑排序只对有向无环图（Directed Acyclic Graph，DAG）定义。

拓扑排序是 DAG 顶点的一种排列，使每条边 \(u\rightarrow v\) 都满足 \(u\) 在 \(v\) 之前。

把顶点按拓扑序排成一行后，所有边都会从左指向右，因此拓扑排序也称图的线性化（linearization）。

  • 入度为 0 的顶点称为源点（source），它们可以作为拓扑序开头。
  • 出度为 0 的顶点称为汇点（sink），它们可以位于末尾。

基于 DFS 的算法

  1. 依次从每个尚未标记的顶点启动 DFS；不同启动之间不要清空标记。
  2. 在 DFS 中，先递归访问全部邻居，再把当前顶点加入后序列表。
  3. 反转后序列表，得到拓扑序。
topological(DAG):
    marked = 新的标记数组
    postOrder = 空列表

    for v in all vertices:
        if !marked[v]:
            dfs(v, marked, postOrder)

    return reverse(postOrder)


dfs(v, marked, postOrder):
    marked[v] = true
    for w in neighbors(v):
        if !marked[w]:
            dfs(w, marked, postOrder)
    postOrder.add(v)

为什么正确？

顶点 v 只有在所有可达后代都处理完之后，才进入后序列表。因此在后序中，后代位于 v 前面；反转后，v 就位于所有后代之前，满足每条有向边的先后约束。

运行时间与 DFS 相同：

\[O(V+E)\]

实际实现还应使用递归栈状态检测环；若发现指向当前递归路径中顶点的边，则输入不是 DAG。

基于入度的算法：Kahn 算法

也可以使用 BFS 风格的方法：

  1. 计算每个顶点的入度。
  2. 把所有入度为 0 的顶点加入队列。
  3. 取出一个顶点加入拓扑序，并“删除”它的所有出边。
  4. 每删除一条边，就把目标顶点入度减 1；若降为 0，则入队。
  5. 重复直到队列为空。

若最终输出顶点数少于 \(V\)，说明图中存在环。

若希望在多个合法顶点中始终选编号最小者，可使用最小优先队列代替普通队列。

总结

  • 拓扑排序把 DAG 线性化。
  • 合法拓扑序可能不唯一。
  • 反向 DFS 后序和 Kahn 入度算法都能在 \(O(V+E)\) 时间完成。

21.2 DAG 上的最短路径

DAG 是有向无环图。它当然可以使用 Dijkstra 求最短路径，但 DAG 的结构允许一个更简单、更快的算法，而且能够正确处理负权边。

Dijkstra 为什么会被负权边破坏？

Dijkstra 依赖一个关键结论：顶点从优先队列弹出后，其最短距离已经确定。负权边可能在之后把一个已确定顶点的距离进一步降低，因此该结论失效。

从 A 出发时，Dijkstra 可能先确定 C，再确定 B，从而错过通过负边 B -> C 得到的更短路线。

负边不代表 Dijkstra 每次都会失败：某些图上它碰巧仍能给出正确结果。

DAG 最短路径算法

核心方法只有两步：

  1. 求出 DAG 的一个拓扑序。
  2. 按拓扑序访问顶点，并松弛该顶点的所有出边。

松弛边 \(u\rightarrow v\)、权重为 \(w\)：

if distTo[u] + w < distTo[v]:
    distTo[v] = distTo[u] + w
    edgeTo[v] = u

初始化：

distTo[source] = 0
其他 distTo = infinity

为什么负边也没问题？

拓扑序保证每条边都从较早顶点指向较晚顶点。当轮到顶点 v 时，所有可能进入 v 的前驱都已经处理并完成松弛，因此关于 v 的全部信息都已到齐。

图中没有环，所以之后不会出现一条从“未来顶点”绕回来继续改善 v 的路径。边权可以为负，也不会破坏这个顺序。

复杂度

  • 拓扑排序：\(O(V+E)\)。
  • 每个顶点访问一次、每条边松弛一次：\(O(V+E)\)。

总复杂度：

\[O(V+E)\]

这比使用二叉堆的 Dijkstra：

\[O((V+E)\log V)\]

更快。

若图不是 DAG 且可能含负边，可使用 Bellman–Ford 算法；它还能检测从源点可达的负权环，但不属于本课程重点。

21.3 最长路径

一般图中的最长简单路径

目标是从一个起点出发，找到到其他顶点的最长简单路径，即路径中不能重复顶点。

在一般图中，这个问题非常困难；已知通用精确算法在最坏情况下需要指数时间。

不能简单地把所有边权取负后运行普通最短路径算法，因为一般图可能出现负环。若允许绕环，就可以无限次降低取负后的路径代价，对应原图中无限增大路径权重；而“简单路径”限制又使问题变成组合搜索。

DAG 上的最长路径

DAG 没有环，因此问题容易得多。可以把已有 DAG 最短路径算法当作黑盒：

  1. 构造图 \(G'\)，把原图每条边权取相反数。
  2. 在 \(G'\) 上运行 DAG 最短路径算法。
  3. 将得到的 distTo 全部再取相反数。
  4. edgeTo 已经给出原图最长路径，不需要改变。

更直接的实现是仍按拓扑序处理顶点，但把松弛条件改为选择更大的距离：

if distTo[u] + w > distTo[v]:
    distTo[v] = distTo[u] + w
    edgeTo[v] = u

不可达顶点初始值应设为负无穷大，源点设为 0。

复杂度仍为：

\[O(V+E)\]

把“最长路径”转换为“取负权后的最短路径”，展示了一种重要的问题求解方法：使用已有算法作为黑盒解决新问题。这称为归约（reduction）。

21.4 归约与分解

上一节为解决 DAG 最长路径，我们先构造一个边权取反的新图 \(G'\)，把它交给 DAG 最短路径算法，再解释输出。

这个过程称为归约（reduction）。因为 DAG 最短路径算法能够被用来解决 DAG 最长路径问题，所以说：

DAG 最长路径归约到 DAG 最短路径。

归约的正式含义

若任务 Q 的任意正确子程序都可以被用来解决任务 P，就说 P 归约到 Q。

通常包含三步：

  1. 预处理：把 P 的输入 \(x\) 转换成 Q 的输入 \(y\)。
  2. 黑盒调用：运行 Q 的算法得到结果。
  3. 后处理：把 Q 的输出转换成 P 的答案。

一个问题可能归约到多种不同问题。现实类比中，“爬上山”可以归约为乘缆车、骑车或其他能够把人送上山的任务。

示例：3SAT 归约到独立集

下面展示两个表面上不同的问题之间的联系。

独立集问题

图的独立集（independent set）是一组顶点，其中任意两个都不相邻。

独立集判定问题：给定图和整数 \(k\)，是否存在大小至少为 \(k\) 的独立集？

3SAT 问题

3SAT 输入由若干子句组成，每个子句是三个文字（变量或变量的否定）的 OR，全部子句再用 AND 连接。例如：

(x1 || x2 || !x3)
&& (x1 || !x1 || x1)
&& (x2 || x3 || x4)

问题是：是否存在一组布尔变量赋值，使所有子句都为真？

术语：

  • 文字（literal）：x1 或 !x1 这样的变量/否定变量。
  • 子句（clause）：三个文字的析取（OR）。
  • 整个公式要求所有子句同时满足（AND）。

构造归约

主张：3SAT 归约到独立集。

设 3SAT 公式有 \(m\) 个子句。

1. 预处理为图

  • 对每个子句创建三个顶点，分别代表三个文字。
  • 同一子句的三个顶点两两相连，形成三角形。
  • 若两个顶点表示互相矛盾的文字，例如 x 与 !x，在它们之间添加边。

2. 调用独立集算法

询问构造出的图是否存在大小为 \(m\) 的独立集。

3. 后处理

若找到大小为 \(m\) 的独立集，把选中的文字设为真，并给其余变量补充任意一致赋值，就能得到原 3SAT 公式的满足解。

为什么这个构造正确？

  • 每个子句内部是三角形，独立集最多从其中选择一个顶点。
  • 独立集总大小要求为 \(m\)，而一共有 \(m\) 个子句，因此必须恰好从每个子句选一个文字。
  • 互相否定的文字之间有边，所以独立集不能同时选择 x 和 !x。
  • 因此，选中的 \(m\) 个顶点正好对应一组彼此一致、每个子句至少一个为真的文字。

反过来，若公式存在满足赋值，就可从每个子句挑一个为真的文字。由于赋值一致，不会同时挑到某变量及其否定；这些顶点构成大小为 \(m\) 的独立集。

所以：

3SAT 可满足  <=>  构造图存在大小为子句数的独立集

归约不一定涉及图；它是一种普遍的问题转换思想。

归约与复杂度

归约不仅能复用算法，也能比较问题难度：

  • 若 P 能高效归约到 Q，且 Q 有高效算法，那么 P 也有高效算法。
  • 若一个已知困难问题 P 能高效归约到 Q，那么 Q 至少和 P 一样困难；否则 Q 的快速算法也会解决 P。

这是 NP 完全性理论的核心语言。

分解

整门课程中我们也一直在做类似的事：

  • List 的实现分解为数组或链表操作。
  • 渗流问题可借助并查集维护连通性。
  • 优先队列分解为堆及其上浮、下沉操作。

这些不一定都是严格意义上的“归约”，因为往往不是只把另一个完整算法当作黑盒。更合适的词是分解（decomposition）：把复杂任务拆成较小、边界清晰的部分，并用抽象隐藏底层细节。

归约、分解与抽象共同构成计算机科学解决问题的核心方式。