当前位置:首页 > 科技/电子
 

计算机基础问题,最大流问题获突破性进展:新算法「快得离谱」


时间:2022-06-14  来源:  作者:  点击次数:


选自quantamagazine

作者:Erica Klarreich

机器心脏编译

编辑:罗马罗马

一个由计算机科学家组成的科研团队,针对计算机领域经典的最大流问题,提出了一种极快的算法。最大流问题是一个组合优化问题。本文探讨了如何充分利用设备的能力,使输送流量最大化,达到最佳效果。

这个问题在网络流理论中是非常基础的。“新算法快得离谱。事实上,我坚信这个问题不可能有如此高效的算法,”耶鲁大学的丹尼尔斯皮尔曼说。

自20世纪50年代以来,人们一直在研究最大流,然后用于模拟前苏联的铁路系统。

加州山景城谷歌研究中心的伊迪丝科恩说:“对它的研究甚至比计算机科学的理论还要古老。

这个问题导致了许多应用:互联网数据流,航空公司调度,甚至匹配求职者与空缺职位。这篇新论文处理最大流和更一般的问题,即最大流和最小费用。多年来,这两个问题刺激了算法技术的许多重大进步。斯皮尔曼说:“这几乎是我们一直在培育算法领域的原因。”

新算法在“近似线性”的时间内解决了这两个问题,也就是说,算法的运行时间与记录网络细节所需的时间基本成正比。对于所有可能的网络,其他解决这些问题的算法都达不到这么快的速度。加州大学伯克利分校的萨蒂什拉奥(Satish Rao)说,这个结果让他跳了起来:“太棒了。」

Spielman认为,我们已经找到了这样一个快速的算法,现在是时候开始考虑解决以前没有想到的各种应用问题了。

目前新方法主要是理论上的改进,因为算法速度的提高只适用于比现实世界中遇到的大得多的网络。对于这些网络来说,最大流量问题已经可以快速回答了(至少不考虑成本最小化)。加拿大滑铁卢大学的理查德彭(Richard Peng)是这种算法的六个创造者之一,他预测新算法可能在一年内投入实际使用。

一些研究人员认为,在未来几年内,计算机科学家可能会找到使其更实用甚至更快的方法。

麻省理工学院的亚历山大mdry说,这篇新论文是“扣篮大赛中最好的扣篮”,尽管未来还会改进。他说,这基本上是最好的”。

一次一条路

理查德彭(Richard Peng)说,许多计算机科学家都在研究最大流问题,以至于在会议上讨论过去的工作就像在看电影结尾的致谢部分。但大多数人都认同第一个形式算法是在1956年,莱斯特福特和德尔伯特富尔克森应用贪婪算法求解最大流。这种方法在每一步中都使用了最简单的对象。

你可以这样理解这个方法:首先,想象一个高速公路网络,你想在给定的时间内从洛杉矶运送尽可能多的送货卡车到纽约。福特和富尔克森的算法从选择一条从洛杉矶到纽约的路线开始,沿着这条路线安排尽可能多的卡车。这种方法通常不利用该特定道路上所有道路的全部容量:如果道路是五车道道路,但是它通过

一架两车道的桥梁,那么你在任何时候都只能启动两辆卡车。

接下来,该算法修改这些路段的通行能力,以反映现在使用了部分路段的通行能力:它从路段的通行能力中减去发送的卡车数量,因此五车道公路现在通行能力是 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/


本文来自华纳娱乐 转载请注明

上一篇 下一篇


  • 用户名:
  • 密码:
  • 验证码:
  • 匿名发表