← 线性规划网络流 · 最大流、最小割与建模归约 / 撤销与回溯：反向边的另一种读法 待审核 13 / 13
反向边 = undo · 不必回溯 · 归约

撤销与回溯：反向边的另一种读法

残量网络里那条反向边，最大流与残量网络 是当作「可撤销的额度」介绍的。换个角度看，它是一个关于撤销的设计选择，而这个选择决定了整族算法要不要回溯。本页把这条线单独拉出来讲，也顺带对照本站另外两个系列处理撤销的方式。

1 · 反向边就是撤销

反向边的残量等于该边已推的流量，也就是「可以退回多少」。走一条反向边，等价于把原边上的流量减掉相应的量。

要紧的不是它能撤销，而是撤销被表示成了图上的一条边。于是撤销和前进变成同一种操作：bfsAugment 找路时不区分正向边与反向边，pushFlow 推流时也不区分。算法根本不知道自己正在撤销什么。

图 1-1 · 关掉反向边会发生什么。可切换网络与选路策略，并开关「允许走反向边」；底部矩阵给出七张网在两种选路下、撤销开与关的四种结果，⚠ 标记拿不到最大流的格子。

经典小网上的对照最直接：DFS 选路时若禁用撤销，算法停在流量 4 上，而这张网的最大流是 5。差的那 1 单位卡在中间边 a→b 上——第一次贪心把它占了，没有反向边就退不回来。

底部那张矩阵有一个原先没料到的结果：七张网里有三张会因禁用撤销而变差，而它们全部落在 DFS 那一列。换成 BFS 选最短增广路，这七张网即便禁用撤销也照样跑满。原因不难理解，Edmonds-Karp 之所以改用 BFS，本就是为了避免 DFS 那种「绕远路顺手占掉关键边」的坏选择；选路策略越好，需要撤销的场合越少。

这不等于说最短增广路策略不需要反向边。反向边对整个 Ford-Fulkerson 家族的正确性是必需的，本页只是没有构造出让最短增广路也退化的网络——这批教学网太温和，而刻意构造这样的反例需要让所有等长的最短路都「占错」，我没找到足够小又足够清楚的例子。

2 · 三种撤销范式

本站另外两个系列各自处理过撤销，机制完全不同。

范式 怎么撤销 撤销后的状态 出处
回滚 记下反向操作，精确恢复 回到过去某个状态 Dancing Links 的 cover / uncover
重放 撤销历史中某个操作，重算它之后的一切 改写历史再前进 CRDT 树的 undo-do-redo
补偿 发一个净效果抵消的新操作 从不回到过去 残量网络的反向边

Dancing Links 的双向链表删除与恢复是标准的回滚，它必须配合回溯搜索：试一个候选、失败、精确恢复、换下一个。这种撤销的代价直接体现为搜索树上的重复试探，branch & bound 讲的就是怎么用界把这些分支剪掉。

网络流走的是第三条路，而且走到了尽头：补偿操作与正常操作用同一套原语表达。它不需要操作日志、不需要状态栈，也不需要「失败」这个概念。工程上这一范式对应补偿事务 [4]，用一笔账面上抵消的新交易替代状态恢复。

3 · 为什么可以不回溯

能这样做不是实现技巧，而是问题结构给的许可。

增广路定理 一个可行流 ff 是最大流，当且仅当残量网络中不存在 s→ts \to t 的增广路。

反过来读这句话：只要还没到最大流，就一定存在一条增广路。任何一次糟糕的局部选择，都能靠一次局部修正补救，永远不必推翻重来。经典小网就是现成的例子：朴素 DFS 先走 s→a→b→ts\to a\to b\to t 占用了中间边，看着像走进死胡同，但不需要退回重选，再找一条经过反向边 b→ab\to a 的增广路即可把流量从 4 补到 5。

配合这一点的是单调性：每次增广的净效果都是流值严格增加瓶颈那么多，即使这次增广用了反向边。算法只往一个方向走，所以不必记住来路。

更深一层的解释在 线性规划与对偶：最大流的可行域是凸多面体，凸性意味着局部最优即全局最优，「顺着改进方向走」永远够用。而 SAT、图着色这类问题的解集离散且不连通，局部修正不够，只能搜索加回溯。二分图最大匹配 里匈牙利算法的「交替路取反」，是同一件事在匹配语言里的说法。

4 · 本系列内部真正回退的地方

说网络流不回溯，需要一处限定：搜索状态是会回退的，解不会。

注 · 三处看着像回退的地方，回退的都不是流。

ISAP 的 retreat 回退的是 DFS 路径栈，流量一步都不退；而且每次 retreat 都伴随距离标号抬高，标号是单调不减且有上界的势函数，所以回退次数有界。

Dinic 的当前弧优化恰恰是把重复回溯剪掉：一条边被判定走不通就在本相位内永久跳过。

HLPP 把超额退回源点看着像回滚，实际是沿反向边前进，高度势能同样单增。

区分这两者的实际意义是复杂度：解的回退会让代价变成指数(搜索树的分支数)，搜索状态的回退只要配上单调的势函数就仍是多项式。势能法因此列在 数学预备 的前置里。

5 · 归约的隐含收益

把一个问题归约成网络流，除了拿到现成的算法，还顺带丢掉了回溯。建模与归约 那页的每个套路都有这层收益：任务分派本可以是「贪心加回溯」，归约成二分图匹配之后变成增广；项目取舍本要枚举 $2^n$ 个子集，归约成最小割之后变成一次最大流。

图 5-1 · 同一批二分图匹配用例，朴素回溯搜索与增广路的代价对照。回溯的「试探」与增广路的「访问边」同量纲，末列给出两者之比。单击任一行切换下方的匹配网图示。

这张表里有一个把我原先的说法推翻的结果。原以为回溯的代价一定更高，实测下来在能配满的用例上并非如此：漏斗争抢那一行，带上界剪枝的回溯只试探 5 次，而增广路访问了 10 条边——回溯反而更省。差距要到配不满的用例上才出现：七个左点抢两个右点时，上界剪枝失效，回溯把组合穷举了 40 次，增广路仍是 2 次增广收工。

所以网络流的优势不该说成「在小例子上更快」。它稳的地方在于代价与结构无关：四个用例里增广次数恒等于匹配大小，不随争抢的激烈程度变化；而回溯的试探次数在 3 到 40 之间摆动，取决于剪枝这次灵不灵。归约值得做，是因为它把结果从赌运气换成了可预期。

6 · 参考文献

  1. Ford, L. R., & Fulkerson, D. R. (1956). Maximal flow through a network. Canadian Journal of Mathematics, 8, 399–404.
  2. Knuth, D. E. (2000). Dancing links. In J. Davies, B. Roscoe, & J. Woodcock (Eds.), Millennial Perspectives in Computer Science (pp. 187–214). Palgrave.
  3. Papadimitriou, C. H., & Steiglitz, K. (1982). Combinatorial Optimization: Algorithms and Complexity. Prentice Hall.
  4. Garcia-Molina, H., & Salem, K. (1987). Sagas. ACM SIGMOD Record, 16(3), 249–259.