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