Quanta Magazine：研究人员实现了网络流“出奇快”的算法

大数据文摘授权转载自zzllrr小乐

作者：Erica Klarreich

译者：zzllrr小乐

一个计算机科学家团队针对计算机科学中最古老的问题之一提出了一种速度显著加快的算法：最大流（maximum flow）。该问题是如果网络中的链路有容量限制，有多少材料可以通过网络从源头流到目的地。

耶鲁大学的Daniel Spielman说，新算法“快得出奇”。“我实际上曾经倾向于相信......对这个问题很好的算法不会存在。”

最大流自 1950 年代以来一直被人们研究，当时它是为研究苏联铁路系统而制定的。“它可能比计算机科学的理论还要古老，”加利福尼亚州山景城谷歌研究中心的 Edith Cohen 说。这个问题有很多应用：互联网数据流、航空公司调度，甚至将求职者与空缺职位匹配。新论文处理了最大流和你还希望最小化成本的问题的更一般版本。多年来，这两个问题激发了算法技术许多极大的进步。“它们几乎就是我们拥有算法领域的原因，”Spielman说。

新算法在“几乎线性”的时间内解决了这两个问题，这意味着算法的运行时间大致与首先写下网络细节所需的时间量成正比。对于所有可能的网络，没有其他算法能够接近于以这种速度运行这些问题。这个成果让他“上蹿下跳” ，加州大学伯克利分校的Satish Rao说。“太奇妙了。”

现在我们知道我们可以非常快速地做到这一点，人们会发现各种各样的应用程序，他们只是以前没有考虑过。

目前，这主要是理论上的进步，因为速度改进只适用于远大于我们在现实世界中遇到的网络，最大流问题已经可以相当快地解决（至少，如果他们不涉及最小化成本）。但该算法的六位创造者之一、加拿大滑铁卢大学的Richard Peng预测，新算法的某些部分可能会在一年内看到实际应用。研究人员表示，在未来几年，计算机科学家可能会找到使其更实用甚至更快的方法。

麻省理工学院的Aleksander Mądry说，即使后续改进确实随之而来，这篇新论文也相当于“灌篮高手” 。他说，这“基本上是最好的”。

一次一条路径

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²的倍数。）差不多 30 年后，Rao 和现在在亚马逊工作的 Andrew Goldberg 对高容量网络产生了类似的结果。但是没有人能击败 1.5 的指数。“进入 2000 年代……这个m^ 1.5的屏障已加固。新论文的作者之一、多伦多大学的Sushant Sachdeva说。

为了取得进展，计算机科学家必须采取完全不同的方法。

从组合学到微积分

到目前为止，所有这些算法都采用了组合方法，它们在每一步中寻找某种类型的结构，并使用该结构来更新流。但在 2003 年，南加州大学的 Spielman 和Chang-Hua 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 年，Google 的 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 算法的内部工作原理。他们的算法提供了一种使用“低拉伸生成树”（low-stretch spanning tree）的新方法——一种捕获网络中许多最显著特征的内部主干。给定这样一棵树，你总是可以通过从树外部添加一个链接来构建至少一个良好的循环。因此，拥有低拉伸生成树会大大减少你需要考虑的循环数。

即使这样，为了让算法快速运行，团队也无法在每一步都构建一个全新的生成树。相反，他们必须确保每个新循环在生成树中只引起轻微的涟漪效应，以便他们可以重用之前的大部分计算。论文作者之一、斯坦福大学研究生Yang Liu说，达到这种控制水平是“核心难点” 。

最终，研究人员创建了一种在“几乎线性”时间内运行的算法，这意味着当你看到越来越大的网络时，它的运行时间接近m的某个倍数。这是一场“巡回演出”，Mądry 说。

该算法使用了 Spielman 和 Teng 工作中的许多想法，但它将它们组合在一起形成了全新的东西。Spielman说，如果你只看过马车，看算法就像遇到汽车一样。“我看到它有一个可以坐的地方，我看到它有轮子，我看到它有一些东西可以让它移动。但他们已经用发动机代替了马。”

Rao 预测，该团队的分析冗长而复杂，但其他研究人员很快就会投入其中以简化事情。“我的感觉是，在接下来的几年里，一切都会变得更清洁、更好，”他说。

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

这种对最大流问题的令人眼花缭乱的加速让Spielman想知道算法理论中的其他核心问题。“我们还能做什么？”

原文链接：

https://www.quantamagazine.org/researchers-achieve-absurdly-fast-algorithm-for-network-flow-20220608/