计算机基础问题，最大流问题获突破性进展：新算法「快得离谱」

这篇新论文称得上是「扣篮大赛中最精彩的扣篮」。

这个问题在网络流理论中非常基础。「新算法快的离谱。其实，我本来坚信这个问题不可能存在这么高效的算法，」来自耶鲁大学的 Daniel Spielman 说道。

自 20 世纪 50 年代以来，人们一直在研究最大流量，当时研究最大流是为了建模研究前苏联铁路系统。

「对它的研究甚至比计算机科学理论还古老，」来自谷歌加州山景城研究中心的 Edith Cohen 这样说。

这个问题通向很多应用：互联网数据流、航空公司日程安排，甚至包含将求职者与空缺职位进行匹配。这篇新论文既处理了最大流量问题，也处理了更一般的问题，即处理最大流同时还希望最小化成本。多年来，这两个问题激发了算法技术的许多重大进步。Spielman 说：“这几乎就是我们一直耕耘算法领域的原因。“

新算法在「近似线性」的时间内解决了这两个问题，就是说该算法的运行时间基本与记录网络细节所需的时间正比。对于所有可能的网络，解决这些问题的其他算法都无法达到如此快的速度。加州大学伯克利分校的 Satish Rao 表示，这个结果让他跳了起来：「简直太棒了。」

Spielman 则认为，我们已经找到如此快的算法，现在是时候着手思考解决之前没有想过的各种应用问题了。

目前，新方法主要是理论上的提升，因为算法速度的提升还只适用于比现实世界中遇到的大得多的网络，对于这些网络，最大流量问题已经可以很快地得到答案（至少在不考虑代价最小化的情况下）。加拿大滑铁卢大学的 Richard Peng 预计，新算法可能在一年内得到实际应用，他是该算法的六位创造者之一。

有研究人员认为，在未来几年里，计算机科学家可能会找到方法使其更实用，甚至可能更快。

麻省理工学院的 Aleksander Mądry 说，未来即使有所改进，但这篇新论文也是「扣篮大赛中最精彩的扣篮」。他说，这基本上是最好的」。

一次一条路径

Richard Peng 表示，很多计算机科学家在研究最大流问题，以至于在会议上讨论过去的工作就像过电影最后的鸣谢部分。但大多数人都同意第一个形式化算法是 1956 年由 Lester Ford 和 Delbert Fulkerson 应用贪心算法求解最大流，这种方法在每一步都使用最容易得到的对象。

你可以这样理解这种方法：首先，设想一个高速公路网络，你希望在给定的时间内将尽可能多的送货卡车从洛杉矶运送到纽约市。Ford 和 Fulkerson 的算法从选择从洛杉矶到纽约的一条路径开始，并沿着这条路径安排尽可能多的卡车。该方法通常不会利用该特定道路上所有道路的全部通行能力：如果道路的是五车道公路，但它通过一架两车道的桥梁，那么你在任何时候都只能启动两辆卡车。

接下来，该算法修改这些路段的通行能力，以反映现在使用了部分路段的通行能力：它从路段的通行能力中减去发送的卡车数量，因此五车道公路现在通行能力是 3，而双车道桥的通行能力为零。同时，该算法在反向方向上为这些公路的通行能力增加了 2，因此，如果我们愿意，我们可以稍后撤销部分流量。

然后，该算法找到一条从洛杉矶到纽约的新路径，该路径可以容纳一些卡车，沿着该路径发送尽可能多的卡车，并再次更新容量。经过有限数量的这些步骤后，从洛杉矶到纽约的道路将无法容纳更多的卡车，到这里算法就完成了：我们只要将构建的所有流量合并，就可以通过获得网络最大可能的流量。

Ford 和 Fulkerson 的算法并不试图在这一过程中做出聪明的选择。如果它选择了一条切断其他有用路径的路径，那是算法之后要处理的问题。在该算法发表后的几十年里，研究人员试图通过让算法做出更明智的选择来加速运行时间，例如总是使用最短的可用路径或可用容量最大的路径。

1970 年，Yefim Dinitz 发现了一种在一步中使用网络中所有最短路径的有效方法。这一算法在低容量网络中的运行时间，由 Shimon Even 和 Robert Tarjan 证明为 m^1.5 (m: 网络中的链接数，相比之下，Ford-Fulkerson 算法在低容量网络中需要多个 m^2）。

近 30 年后，Rao 和 Andrew Goldberg 对高容量网络得出了类似的结果。但没有人能击败 m^1.5 指数。这篇新论文的作者之一、多伦多大学的苏珊特・萨赫德瓦（SushantSachdeva）说：「进入 21 世纪……m^1.5 的壁垒根深蒂固。」为了取得更大进展，计算机科学家必须寻找完全不同的方法。

从组合到微积分

到目前为止，所有这些算法都采用了组合方法，即在每个步骤中寻找某种类型的结构，并使用该结构来更新流。但在 2003 年，南加州大学的 Spielman 和 ShangHua Teng 开启了一扇完全不同的「优化」方法之门，在这种方法中，使用微积分技术为指导寻找最优解。

Spielman 和 Teng 开发了一种快速优化算法，该算法解决的不是最大流量问题，而是一个密切相关的问题，即通过每根具有给定电阻的导线网络找到能量最低的电流。Sachdeva 说，Spielman 和 Teng 的进步是「关键时刻」。

创建确定网络最大流量和最小成本的超快速算法团队成员 (从左上角顺时针开始):Yang Liu、 Li Chen、Rasmus Kyng、Maximilian Probst Gutenberg、Richard Peng、Sushant Sachdeva。

研究人员很快开始探索如何将这一进展应用于最大流问题。可以把公路网想象成由电线组成的网络，在没有太多可用容量的公路上增加电阻，阻止电子穿过公路。由于 Spielman 和 Teng 的工作，我们可以快速计算通过这些电线的电流，这个模型具有通过高速公路的最大车辆流量的粗略属性。（它们不会完全相同，因为电流问题对导线的容量没有任何硬性限制。）

然后，在产生了这个初始流量之后，我们可以像 Ford 和 Fulkerson 的组合算法一样重新调整容量。接下来，可以重置每条导线的电阻，以反映这些变化的量，并解决新生成的电路问题。

与一次改变一个网络块的组合方法不同，Spielman 和 Teng 的优化方法每次完成整个网络的扫描。这使得每一步都更加有效，因此达到最大值需要的总步骤更少。2008 年，谷歌的 Samuel Daitch 和 Spielman 使用了这种方法，基本上与之前的最大流量 m^1.5 的界限相近。在 2013 年，Mądry 进一步推进了该方法，以突破低容量网络的 m^1.5，将运行时间提高到大约 m^1.43 的倍数。「这太令人震惊了，」Rao 表示。

接下来的几年里，研究人员进一步扩展了这种方法，但他们的结果仍停留在 m^1.33。他们开始怀疑这个指数是否是一个基本极限。

对于最大流算法来说，最快的可想象运行时间应该是 m 倍（即 m^1.0），因为写下一个网络需要 m 个步骤的倍数。这被称为线性时间。但对许多研究人员来说，这样一个极快的算法似乎是不可想象的。「没有任何充分的理由，能让我们相信能做到这一点，」Spielman 说到。

缩小、重用、回收

这篇新论文的作者认为，Daitch 和 Spielman 的方法有更多的优点。Mądry 曾用它来减少解决最大流问题所需的步骤数，但这种减少是有代价的：在每一步中，整个网络都必须重写，并且必须从头开始解决电力流问题。

这种方法将 Spielman 和 Teng 的算法视为黑盒 —— 不管算法内部在做什么。六位研究人员决定深入研究该算法的核心，并根据最大流量问题调整其各个组成部分。他们怀疑，这些组件甚至可能让他们解决更难的「最低成本问题，在这个问题是寻找最便宜的方式来运输给定数量的材料。计算机科学家早就知道，任何最小成本算法都可以解决最大流问题。

与其他优化方法一样，研究人员提出了流的「能量」概念即链接成本和容量的函数。将流量从昂贵的低容量链路转移到廉价的高容量链路会降低系统的总能量。

为了弄清楚如何快速地将流移向低能状态，研究人员将这种优化方法与旧的组合观点相结合。后者一次只更改网络的一部分，提供了重用前面步骤中的一些工作的可能性。

在每一步中，算法都会寻找一个可以减少能量的循环，即开始和结束是同一个点的路径。基本想法很简单：假设你创建了一条从芝加哥到纽约的收费公路，然后你发现有一条更便宜的高速公路。这时把纽约添加进循环，沿着昂贵的道路运行到芝加哥，然后沿着较便宜的路线返回，形成一个循环，从而替换掉昂贵的路径，从而降低了流量的总成本。

加拿大维多利亚大学的 Valerie King 说，这种方法使用的步骤比「电气方法」多得多，所以乍一看听起来「像是在倒退」。为了进行补偿，算法必须在每一步都以难以置信的速度找到优质的循环，比检查整个网络所需的速度还要快。

这就是 Spielman 和 Teng 的算法的工作原理。他们的算法提供了一种使用「低延伸生成树」的新方法，这种树是算法的关键，它可以捕获网络的许多最显著的特征。给定这样一个树，通过在树外添加一个链接，总是可以构建至少一个良好的循环。因此，拥有一个低伸缩的生成树可以大大减少需要考虑的循环数。

即便如此，为了让算法快速运行，团队也无法在每一步都构建一个全新的生成树。相反，他们必须确保每个新周期在生成树中只产生较小的涟漪效应，以便重用以前的大部分计算。该论文作者之一、斯坦福大学研究生 Yang Liu 表示，实现这种控制水平是「核心难点」。

最终，研究人员创建了一种在「几乎线性」时间内运行的算法，这意味着当用越大的网络时，它的运行时间越接近 m。

该算法借鉴了 Spielman 和 Teng 的许多想法，并将它们结合在一起，形成了一种全新的东西。Spielman 说，如果你只见过马拉的车，那么现在的算法就像是汽车。「我看到它有一个可以坐的地方，我看到它有轮子，我看到它有东西可以让它移动。但他们已经用发动机代替了马。」

Rao 推测，该团队的分析是漫长而复杂的，但其他研究人员很快就会深入研究以简化问题。他说：「我的感觉是，未来几年，一切都会变得更干净、更好。」

Spielman 说，一旦算法得到简化，计算机科学家可能会开始将其用作解决不同问题的算法的子程序。「现在我们知道我们可以很快做到这一点，人们会发现各种各样的应用程序，这是他们以前没有想过。」

另外，该算法对最大流问题令人眩晕的加速，让 Spielman 对算法理论中的其他核心问题有了期待，「我们还能做些什么？」

原文链接：https://www.quantamagazine.org/researchers-achieve-absurdly-fast-algorithm-for-network-flow-20220608/

理论数据流最大流问题