来源：机器之心 本文约3600字，建议阅读7分钟 这项新研究被称为扣篮比赛中最精彩的扣篮。由计算机科学家组成的研究团队为计算机领域的经典最大流量问题提出了快速算法。最大流量问题是组合优化问题，讨论如何充分利用设备的能力，使运输流量达到最佳效果。
这个问题在网络流理论中非常基础。「新算法快速离谱。事实上，我坚信这个问题不可能有如此高效的算法，」耶鲁大学 Daniel Spielman 说道。
自 20 世纪 50 自20世纪90年代以来，人们一直在研究最大流量，研究最大流量是建模和研究前苏联铁路系统。
「它的研究甚至比计算机科学理论还古老，」谷歌加州山景城研究中心 Edith Cohen 这样说。
这个问题有很多应用：互联网数据流、航空公司日程安排，甚至包括匹配求职者和空缺职位。这篇新论文不仅处理了最大流量问题，而且处理了更一般的问题，即处理最大流量，而且希望降低成本。多年来，这两个问题激发了算法技术的许多重大进步。Spielman 说：这几乎就是我们一直在培育算法领域的原因。
新算法在「近似线性」这两个问题在时间内得到了解决，即算法的运行时间基本上与记录网络细节所需的时间成正比。其他解决这些问题的算法对于所有可能的网络都不能如此快。加州大学伯克利分校 Satish Rao 结果让他跳了起来：「太棒了。」
Spielman 我们认为是时候开始思考解决我们以前从未想过的各种应用问题了。
目前，新方法主要是理论上的改进，因为算法速度的提高只适用于比现实世界中遇到的大得多的网络。对于这些网络，最大的流量问题可以很快得到答案（至少不考虑成本最小化）。加拿大滑铁卢大学 Richard Peng 新算法有望在一年内实际应用，他是该算法的六大创造者之一。
一些研究人员认为，计算机科学家可能会在未来几年找到更实用甚至更快的方法。
麻省理工学院 Aleksander M?dry 即使未来有所改善，这篇新论文也是如此「扣篮比赛中最精彩的扣篮比赛」。他说这基本上是最好的」。
Richard Peng 表示，很多计算机科学家在研究最大流问题，以至于在会议上讨论过去的工作就像过电影最后的鸣谢部分。但大多数人都同意第一个形式化算法是 1956 年由 Lester Ford 和 Delbert Fulkerson 利用贪婪算法求解最大流，这种方法在每一步都使用最容易获得的对象。
你可以理解这种方法：首先，想象一个高速公路网络，你希望在给定的时间内从洛杉矶运送尽可能多的卡车到纽约。Ford 和 Fulkerson 的算法从选择从洛杉矶到纽约的一条路径开始，并沿着这条路径安排尽可能多的卡车。这种方法通常不利用特定道路上所有道路的所有交通能力：如果道路是五车道公路，但通过两车道桥，那么你只能随时启动两辆卡车。
接下来，该算法修改了这些路段的交通能力，以反映部分路段的交通能力：它从路段的交通能力中减少了发送的卡车数量，因此五车道公路的交通能力是 3.双车道桥的通行能力为零。同时，该算法在反向方向上提高了这些道路的通行能力 因此，如果我们愿意，以后可以撤销部分流量。
然后，该算法找到了一条从洛杉矶到纽约的新路径，可以容纳一些卡车，沿着它发送尽可能多的卡车，并再次更新容量。在有限数量的步骤之后，从洛杉矶到纽约的道路将无法容纳更多的卡车，这里的算法已经完成：只要我们合并所有构建的流量，我们就可以通过网络获得最大可能的流量。
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/
编辑：于腾凯
校对：林亦霖