“快得离谱”算法解决了 70 年的僵局——加快了从航空公司调度到互联网等领域的网络流量

研究人员设计了一种“快得离谱”的算法来解决寻找网络中最快流量的问题。

当您通过我们网站上的链接购买时，我们可能会赚取联属佣金。这是它的工作原理。

得益于超快的新算法，网络速度缓慢的情况很快就会成为过去。

这一突破为自 20 世纪 50 年代以来一直困扰计算机科学家的问题提供了一种更快的解决方案：最大流量，或者如何通过容量有限的系统实现最快的信息流。

以前的最大流量算法取得了稳步和渐进的进步，但它们找到最佳流量的时间仍然比处理网络数据的时间更长。但这项于 6 月 11 日在第 56 届 ACM 计算理论年度研讨会论文集上发表的新研究详细介绍了一种算法，该算法可以像编写详细信息一样快地大致解决问题。网络故障。

最大流问题是算法科学的基石，并激发了该领域许多最重要的进步。第一次尝试解决这个问题是在 1956 年，当时数学家德尔伯特·富尔克森 (Delbert Fulkerson) 和莱斯特·福特 (Lester Ford) 提出了他们所谓的“贪婪解法”。

贪心算法的工作原理是在决策树上的每个点上做出最直接有利的选择，选择前面的最佳路径，而不管将来可能会阻塞哪些路径。

相关：新型量子计算机将“量子霸权”记录打破了 100 倍，而且功耗降低了 30,000 倍

想象一下优化沿多条可能路径从 A 到 B 的交通的问题，一条路线由第一段六车道高速公路和最后一段三车道道路组成。为了解决这个问题，贪心算法将沿路线发射尽可能多的交通（三车道汽车），调整其容量并对其他路线重复相同的步骤，直到每条可能的路径都满载。

富尔克森和福特的算法被证明足够有效，但它常常无法产生最佳的流量：如果其他路线被切断并且出现次优拥堵，那就这样吧。随后 70 年对这个问题的贡献试图完善解决方案的这方面，通过在算法中构建更好的决策来消除不必要的减速。

2004 年，这些调整将算法的运行时间从 m^2 倍数（其中 m 是网络中的节点数）提高到 m^1.33 倍数，但随后进展陷入停滞。

为了实现突破，研究人员结合了两种先前的方法：将网络视为流量的原始解决方案；以及将网络视为流量的原始解决方案。后来的一个则将它们视为电网。与汽车或火车不同，电子流可以部分转移以沿着另一条路线加入电流，使计算机科学家能够在应用逐段流量方法之前绘制出整个网络的最佳流量。

耶鲁大学应用数学和计算机科学教授丹尼尔·A·斯皮尔曼（Daniel A. Spielman）在一份声明中表示，将这两种方法结合起来产生了一种“快得离谱”的混合算法，他负责指导其中一名研究人员的博士课程。斯皮尔曼将新的解决方案与之前的解决方案进行了比较，就像“一辆保时捷超越了马车”。

研究人员表示，一旦完善，新算法可能会应用于许多应用，包括互联网数据、航班调度和提高市场效率。