这个问题在网络流量理论中很基础。“新算法快得离谱。事实上，我确信对于这个问题不可能有如此有效的算法，”耶鲁大学的DanielSpielman说。自1950年代以来，人们一直在研究最大流量，当时它是为前苏联铁路系统的建模研究而研究的。“对它的研究甚至比计算机科学理论还要古老，”谷歌加州山景城研究中心的伊迪丝科恩说。这个问题导致了很多应用：互联网数据流、航班时刻表，甚至匹配求职者和职位空缺。这篇新论文既处理了最大流量问题，也处理了处理最大流量同时还希望最小化成本的更普遍的问题。多年来，这两个问题激发了算法技术的许多重大进步??。“这几乎就是我们一直在算法领域工作的原因，”斯皮尔曼说。新算法在“近似线性”的时间内解决了这两个问题，这意味着算法的运行与记录网络细节所需的时间大致成正比。.解决这些问题的其他算法无法对所有可能的网络实现如此快速。加州大学伯克利分校的SatishRao说，这个结果让他跳了起来：“这真是太棒了。”Spielman认为，我们已经找到了这么快的算法，现在是时候开始思考以前没有想到的各种应用了。问题。目前，新方法主要是理论上的改进，因为算法加速只适用于比现实世界中遇到的更大的网络，对于最大流量问题已经可以非常快速地解决（至少在不管成本最小化）。加拿大滑铁卢大学的RichardPeng是该算法的六位发明者之一，他预计新算法可以在一年内投入实际使用。一些研究人员认为，在未来几年内，计算机科学家可能会找到使其更实用、甚至更快的方法。麻省理工学院的AleksanderM?dry说，即使未来有所改进，这篇新论文也是“扣篮大赛中最好的扣篮”。这基本上是最好的事情，”他说。RichardPeng说，有这么多计算机科学家研究最大流问题，以至于在会议上讨论过去的工作就像在电影结束时浏览演职员表一样。但是大多数人认为，第一个形式化算法是在1956年由LesterFord和DelbertFulkerson提出的，用于解决应用贪心算法的最大流问题，该算法在每一步都使用最容易获得的对象。你可以这样想这个方法：首先，想象一个高速公路网络，你想在给定的时间内将尽可能多的送货卡车从洛杉矶运到纽约市。Ford和Fulkerson的算法首先选择从洛杉矶到纽约的路径，并在该路径上安排尽可能多的卡车。这种方法通常不会利用该特定道路上所有道路的全部容量：如果这条道路是五车道高速公路，但它经过一座双车道桥，那么在任何时候你只能有两辆卡车在行驶.接下来，该算法修改这些路段的通行能力，以反映路段的部分通行能力现在已被使用：它从路段通行能力中减去发送的卡车数量，因此五车道高速公路现在的通行能力为3，而两个-lane桥的容量为零。同时，算法在这些道路的反向通行能力上增加了2，这样我们以后可以根据需要撤回一些流量。该算法然后找到一条从洛杉矶到纽约的新路线，可以容纳一些卡车，沿该路线发送尽可能多的卡车，并再次更新容量。经过有限数量的这些步骤后，从洛杉矶到纽约的道路将无法容纳更多的卡车，此时算法完成：我们只需要组合所有构建的流量以获得可能的最大流量网络。Ford和Fulkerson的算法并没有试图在整个过程中做出明智的选择。如果它选择了一条切断其他有用路径的路径，那是算法稍后要处理的事情。在该算法发布后的几十年里，研究人员一直试图通过让算法做出更明智的选择来加快运行时间，例如始终使用最短的可用路径或具有最大可用容量的路径。1970年，YefimDinitz发现了一种在一个步骤中使用网络中所有最短路径的有效方法。ShimonEven和RobertTarjan证明了该算法在低容量网络中的运行时间为m^1.5（m：网络中的链接数，相比之下Ford-Fulkerson算法需要多个m^2）。将近30年后，Rao和AndrewGoldberg对高容量网络得出了类似的结果。但是没有人可以击败m^1.5指数。“进入21世纪……m^1.5的障碍根深蒂固，”新论文的作者之一、多伦多大学的SushantSachdeva说。为了取得进一步的进展，计算机科学家将不得不找到完全不同的方法。从组合到微积分，到目前为止，所有这些算法都采用组合方法，在每个步骤中寻找某种类型的结构，并使用该结构来更新流程。但在2003年，南加州大学的Spielman和ShangHuaTeng打开了通往“优化”的完全不同方法的大门，其中使用微积分技术来指导寻找最佳解决方案。Spielman和Teng开发了一种快速优化算法，它解决的不是最大流量问题，而是一个密切相关的问题，即找到通过每条具有给定电阻的电线网络的最低??能量电流。Sachdeva说Spielman和Teng的进步是在“关键时刻”进行的。创建确定网络最大流量和最小成本的超快速算法的团队成员（从左上顺时针方向）：YangLiu、LiChen、RasmusKyng、MaximilianProbstGutenberg、RichardPeng、SushantSachdeva。研究人员很快开始探索如何将这一进步应用于最大流量问题。将道路网络想象成一个电线网络，在没有太多可用容量的道路上增加电阻，以防止电子穿过它们。感谢Spielman和Teng的工作，我们可以快速计算出通过这些电线的电流，并且该模型具有通过高速公路的最大车辆流量的粗略属性。（它们不会完全相同，因为当前问题对电线的容量没有任何硬性限制。）然后，在生成此初始流后，我们可以像Ford和Fulkerson的组合算法一样重新调整容量。接下来，可以重置每根导线的电阻以反映这些变化量并对新生成的电路进行故障排除。与一次更改一个网络块的组合方法不同，Spielman和Teng的优化方法一次扫描整个网络。这使得每一步都更有效率，因此达到最大值所需的总步数更少。2008年谷歌的SamuelDaitch和Spielman就用了这个方法，基本接近了之前的最大流m^1.5bound。2013年，M?dry进一步推进了针对低容量网络打破m^1.5的方法，将运行时间增加到大约m^1.43的倍数。“这令人震惊，”拉奥说。在接下来的几年里，研究人员进一步扩展了这种方法，但他们的结果仍然停留在m^1.33。他们开始怀疑这个指数是否是一个基本极限。最大流算法的最快运行时间应该是m次（即m^1.0），因为写下网络需要m步的倍数。这称为线性时间。但对于许多研究人员来说，这样一个极快的算法似乎是不可想象的。“我们没有充分的理由相信这是可能的，”斯皮尔曼说。缩小、再利用、回收新论文的作者认为，Daitch和Spielman的方法还有其他优点。M?dry用它来减少解决最大流问题所需的步骤数，但这种减少是有代价的：每一步都必须重写整个网络，并且必须从头开始解决潮流问题。这种方法将Spielman和Teng的算法视为黑盒——无论算法内部发生了什么。六位研究人员决定深入算法的核心并将其各个组件调整为最大流量问题。他们怀疑，这些组件甚至可能让他们解决更难的“最小成本问题”，即找到运输给定量材料的最便宜方式。计算机科学家早就知道任何最小成本算法都可以解决最大流问题。问题。与其他优化方法一样，研究人员提出了流量“能量”的概念，作为链路成本和容量的函数。将流量从昂贵的低容量链路转移到廉价的高容量链路可以降低系统的整体能量。为了弄清楚如何快速将流动转移到低能量状态，研究人员将这种优化方法与旧的组合观点相结合。后者一次只改变网络的一部分，提供了重用前面步骤的一些工作的可能性。在每一步，该算法都会寻找一个减少能量的循环，即在同一点开始和结束的路径。基本思路很简单：假设您修建了一条从芝加哥到纽约的收费公路，然后您发现有一条更便宜的高速公路。现在将纽约添加到循环中，运行昂贵的路线到芝加哥并沿着便宜的路线返回，形成一个循环来取代昂贵的路线，从而降低交通的总体成本。加拿大维多利亚大学的ValerieKing说，这种方法比“电法”使用的步骤多得多，所以乍一看，这听起来“像是倒退了一步”。作为补偿，该算法必须以极快的速度在每个步骤中找到良好的循环，这比检查整个网络所需的速度还要快。这就是Spielman和Teng算法的工作原理。他们的算法提供了一种使用“低扩展生成树”的新方法，这是该算法的关键，它捕获了网络的许多最显着特征。给定这样一棵树，至少总是可以通过在树外添加一个链接来构造一个好的循环。因此，具有低尺度生成树可以大大减少需要考虑的循环数。即便如此，该团队也无法在每一步都构建一棵全新的生成树，以便算法快速运行。相反，他们必须确保每个新循环只在生成树中产生小的涟漪效应，以便重复使用以前的大部分计算。该论文的作者之一、斯坦福大学研究生YangLiu说，实现这种控制水平是“核心困难”。最终，研究人员创建了一种以“几乎线性”时间运行的算法，这意味着当使用更大的网络时，它的运行时间更接近m。该算法借鉴了Spielman和Teng的许多想法，并将它们结合起来形成了全新的东西。Spielman说，如果你只见过马车，那么现在的算法就像汽车一样。“我看到它有地方可以坐，我看到它有轮子，我看到它有东西可以移动。但他们用引擎代替了马。”Rao推测该团队的分析冗长而冗长。复杂，但其他研究人员将很快深入挖掘以简化问题。“我的感觉是，在接下来的几年里，一切都会变得更干净、更好，”他说。斯皮尔曼说，一旦算法得到简化，计算机科学家可能会开始将其用作解决不同问题的算法的子程序。“现在我们知道我们可以很快做到这一点，人们会发现他们以前没有想到的各种应用程序。”此外，该算法在最大流问题上令人眼花缭乱的加速使Spielman想到了算法理论中的另一个核心问题：“我们还能做什么？”
