2Dwork/Shutterstock
一个计算机科学家团队针对计算机科学中最古老的问题之一提出了一种速度显着加快的算法：最大流量。问题是如果网络中的链路有容量限制，有多少材料可以通过网络从源流到目的地。
耶鲁大学的丹尼尔斯皮尔曼说，新算法“快得离谱”。 “我实际上倾向于相信……这种对这个问题很好的算法不会存在。”
自 1950 年代以来一直在研究最大流量，当时它是为研究苏联铁路系统而制定的。 “它可能比计算机科学的理论还要古老，”加利福尼亚州山景城谷歌研究中心的伊迪丝·科恩 ( Edith Cohen ) 说。这个问题有很多应用：互联网数据流、航空公司调度，甚至将求职者与空缺职位匹配。新论文处理了最大流量和您还希望最小化成本的问题的更一般版本。多年来，这两个问题激发了算法技术的许多最大进步。 “它们几乎就是我们拥有算法领域的原因，”斯皮尔曼说。
新算法在“几乎线性”的时间内解决了这两个问题，这意味着算法的运行时间大致与首先写下网络细节所需的时间量成正比。对于所有可能的网络，没有其他算法能够接近于以这种速度运行这些问题。结果让他“跳上跳下”，加州大学伯克利分校的Satish Rao说。 “太奇妙了。”
Ford 和 Fulkerson 的算法并没有尝试在此过程中做出明智的选择。如果它选择了一条切断其他有用路线的路径，那只是它以后处理的问题。在算法发布后的几十年里，研究人员试图通过让算法做出更明智的选择来加快运行时间——例如始终使用最短的可用路径或具有最大可用容量的路径。
1970 年，Yefim Dinitz 找到了一种有效的方法，可以一步使用网络中的所有最短路径。这创建了一种算法，其在低容量网络中的运行时间由 Shimon Even 和Robert Tarjan显示为m 1.5的倍数，其中m是网络中的链接数。 （相比之下，Ford-Fulkerson 算法在低容量网络中采用m 2的倍数。）差不多 30 年后，Rao 和现在在亚马逊工作的 Andrew Goldberg 对高容量网络产生了类似的结果。但没有人能打败 1.5 的指数。 “进入 2000 年代……这个1.5米的障碍已经根深蒂固，”新论文的作者之一、多伦多大学的Sushant Sachdeva说。
为了取得进展，计算机科学家必须采取完全不同的方法。
从组合到微积分
到目前为止，所有这些算法都采用了组合方法，它们在每一步中寻找某种类型的结构，并使用该结构来更新流程。但在 2003 年，南加州大学的 Spielman 和Chang-Hua Teng打开了通往完全不同的“优化”方法的大门，在这种方法中，您使用微积分技术来引导您找到最佳解决方案。
Spielman 和 Teng 开发了一种快速优化算法，该算法解决的不是最大流量问题，而是一个密切相关的问题，即通过每个具有给定电阻的导线网络找到能量最低的电流。 Sachdeva 说，斯皮尔曼和滕的晋级是“一个关键时刻”。
创建可以确定网络最大流量和最小成本的超快速算法的团队：（从左上角顺时针方向）Yang Liu、Li Chen、Rasmus Kyng、Maximilian Probst Gutenberg、Richard Peng 和 Sushant Sachdeva。
（从左上角顺时针方向）由杨柳提供；黄伊娃；由 Rasmus Kyng 提供；由马克西米利安普罗布斯特提供；乔·佩特里克；普什卡里尼·阿格哈卡
研究人员很快开始探索如何将这一进步应用于最大流量问题。这个想法是将我们的高速公路网络想象成一个电线网络，并提高没有太多可用容量的高速公路上的电阻，以阻止电子穿过它们。因为有了斯皮尔曼和滕，我们可以快速计算出通过这些电线的电流，它就会具有高速公路上车辆最大流量的粗略属性。 （它们不会完全相同，因为电流问题对电线的容量没有任何硬性限制。）
然后，在产生了这个初始流程后，您重新调整容量，就像在 Ford 和 Fulkerson 的组合算法中一样。接下来，您重置每根电线的电阻以反映这些变化的容量并解决这个新的电气问题，等等。
与一次更改网络的一部分的组合方法不同，Spielman 和 Teng 的优化方法一次涵盖整个网络。这使得每一步都更加强大，因此您需要更少的总步数来达到最大值。 2008 年，Google 的 Samuel Daitch 和 Spielman使用这种方法基本上匹配了之前的m 1.5最大流量界限。然后在 2013 年，Mądry 进一步推动了这一方法，突破了低容量网络的m 1.5障碍，将运行时间加快到m 1.43左右的倍数。 “这令人震惊，”饶说。
在接下来的几年里，研究人员进一步扩展了这种方法，但他们被困在了m 1.33上。他们开始怀疑这个指数是否是一个基本极限。
最大流算法的最快可能运行时间将只是m的倍数（即m 1.0 ），因为仅写下一个网络就需要m步的倍数。这被称为线性时间。但对许多研究人员来说，如此快速的算法似乎是不可想象的。
“没有充分的理由相信我们可以做到这一点，”斯皮尔曼说。
减少回收再利用
但这篇新论文的作者认为，戴奇和斯皮尔曼的方法可以榨出更多的汁液。 Mądry 曾使用它来减少解决最大流量问题所需的步骤数，但这种减少是有代价的：在每一步中，都必须重写整个网络，并从头开始解决其电流问题。
这种方法将斯皮尔曼和滕的算法视为一个黑匣子——算法在内部做什么并不重要。六名研究人员决定深入挖掘算法的核心，并根据最大流量问题调整其各种组件。他们怀疑，这些组件甚至可以让他们解决更难的“最低成本”问题，在这个问题中，您正在寻找最便宜的方法来路由给定数量的材料。计算机科学家早就知道，任何最小成本算法也可以解决最大流量问题。
与其他优化方法一样，研究人员提出了流动“能量”的概念——一个考虑链接成本和容量的函数。将流量从昂贵的低容量链路转移到廉价的高容量链路会降低系统的总能量。
为了弄清楚如何快速将流动移向低能量状态，研究人员将这种优化方法与旧的组合观点相结合。后者一次只更改网络的一部分，提供了重用之前步骤中的一些工作的潜力。
在每一步，算法都会寻找一个循环——一条在同一点开始和结束的路径——可以减少能量。基本想法很简单：想象一下，您创建了一条将卡车从芝加哥沿收费公路运送到纽约的流程，但随后您发现有一条更便宜的高速公路可用。增加从纽约开始的循环，沿着昂贵的道路运行到芝加哥，然后沿着更便宜的路线返回，有效地取消了昂贵的路径并用更便宜的路径取而代之，从而降低了流程的总成本。
加拿大维多利亚大学的Valerie King说，这种方法比电气方法使用了更多的步骤，因此乍一看“听起来像是在倒退”。作为补偿，算法在每一步都必须非常快地找到一个好的循环——比仅仅检查整个网络所需的速度还要快。
这就是 Spielman 和 Teng 算法的内部工作原理。他们的算法提供了一种使用“低拉伸生成树”的新方法——一种捕获网络中许多最显着特征的内部主干。给定这样一棵树，您总是可以通过从树外部添加一个链接来构建至少一个良好的循环。因此，拥有低拉伸生成树会大大减少您需要考虑的周期数。
即使这样，为了让算法快速运行，团队也无法在每一步都构建一个全新的生成树。相反，他们必须确保每个新循环在生成树中只引起轻微的涟漪效应，以便他们可以重用之前的大部分计算。论文作者之一、斯坦福大学研究生杨柳说，达到这种控制水平是“核心难点”。
最终，研究人员创建了一种在“几乎线性”时间内运行的算法，这意味着当你观察越来越大的网络时，它的运行时间接近m的某个倍数。这是一场“巡回演出”，Mądry 说。
该算法使用了 Spielman 和 Teng 工作中的许多想法，但它将它们组合在一起形成了全新的东西。斯皮尔曼说，如果你只看过马车，看算法就像遇到汽车一样。 “我看到它有一个可以坐的地方，我看到它有轮子，我看到它有一些东西可以让它移动。但他们已经用发动机代替了马。”
Rao 预测，该团队的分析冗长而复杂，但其他研究人员很快就会投入其中以简化事情。 “我的感觉是，在接下来的几年里，一切都会变得更清洁、更好，”他说。
斯皮尔曼说，一旦算法得到简化，计算机科学家可能会开始将其用作解决不同问题的算法的子程序。 “现在我们知道我们可以非常快地做到这一点，人们会找到他们以前没有想到的各种应用程序。”
这种对最大流量问题的令人眼花缭乱的加速让斯皮尔曼想知道算法理论中的其他核心问题。 “我们还能做什么？”