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

这个成绩在收集流理论中非常基础。「新算法快的离谱。其实，我本来坚信这个成绩不可能存在这么高效的算法，」来自耶鲁大学的 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/