研究人员开发出最快的流动算法

拉斯穆斯·金 (Rasmus Kyng) 和他的团队取得了突破，他们开发出了一种超快的算法，看起来将改变整个研究领域，这让人想起了幸运卢克（Lucky Luke），那个射击速度比他的影子还快的人。

Kyng 团队的开创性工作涉及所谓的网络流算法，该算法解决了如何在网络中实现最大流量同时最小化传输成本的问题。

想象一下，您正在使用欧洲交通网络，并寻找最快、最便宜的路线，以便将尽可能多的货物从哥本哈根运送到米兰。在这种情况下，Kyng 的算法可以用于计算任何类型网络（无论是铁路、公路、水路还是互联网）的最佳、成本最低的交通流量。

他的算法执行这些计算的速度非常快，以至于它可以在计算机读取描述网络的数据时立即提供解决方案。

网络计算速度很快

在 Kyng 之前，没有人能够做到这一点——尽管研究人员已经研究这个问题大约 90 年了。以前，计算最佳流量所花的时间比处理网络数据所花的时间要长得多。

随着网络变得越来越大、越来越复杂，所需的计算时间相对而言比计算问题的实际规模增长得更快。这就是为什么我们也看到网络中的流问题太大，计算机甚至无法计算。

Kyng 的方法消除了这个问题：使用他的算法，计算时间和网络规模以相同的速率增加——有点像去徒步旅行，无论路有多陡峭，始终保持相同的步伐。

看一下原始数据就能知道我们已经走了多远：直到千禧年，还没有一种算法能够比 m^1.5，其中m代表计算机需要计算的网络连接数，仅仅读取一次网络数据就需要m时间。

2004年，解决该问题所需的计算速度成功降低至m^1.33使用Kyng的算法，读取网络数据后到达解决方案所需的“额外”计算时间现在可以忽略不计。

就像保时捷和马车赛跑一样

因此，苏黎世联邦理工学院的研究人员开发出了理论上最快的网络流算法。两年前，Kyng 和他的团队在一项开创性的研究中展示了他们概念的数学证明 纸科学家将这些新颖的、几乎最优的快速算法称为“近似线性时间算法”，而理论计算机科学家界对 Kyng 的突破既惊讶又热情。

Kyng 的博士生导师、耶鲁大学应用数学和计算机科学教授 Daniel A. Spielman 本人也是该领域的先驱和资深人士，他将这种“快得离谱”的算法比作保时捷超越马车。

他们的论文不仅获得了 IEEE 计算机科学基础年度研讨会 (FOCS) 2022 年最佳论文奖，还 突出显示 在计算杂志上 ACM 通讯，科普杂志《Quanta》的编辑们将 Kyng 的算法评为 2022 年计算机科学十大发现。

苏黎世联邦理工学院的研究人员此后不断改进他们的方法，并开发出更多近乎线性时间的算法。例如，第一个算法仍然侧重于固定的静态网络，这些网络的连接是定向的，这意味着它们的功能就像城市道路网络中的单行道一样。

今年发布的算法现在还能够计算随时间逐渐变化的网络的最佳流量。闪电般快速的计算是解决高度复杂且数据丰富的网络的重要一步，这些网络动态且快速地变化，例如生物学中的分子或大脑，或人类的友谊。

用于改变网络的闪电般快速的算法

周四，Kyng 团队的成员 Simon Meierhans 表示：呈现 在 ACM 年度计算理论研讨会上提出的一种新的近线性时间算法（库存 2024 年，温哥华。该算法解决了随着新连接的添加而逐步变化的网络的最小成本最大流问题。

此外，在第二篇论文中 公认 在 10 月份的 IEEE 计算机科学基础研讨会 (FOCS) 上，ETH 的研究人员开发了另一种算法，也可以处理被删除的连接。

具体来说，这些算法会在添加或删除连接时识别出最短路线。在现实世界的交通网络中，瑞士此类变化的例子包括自 2023 年夏季以来几个月内圣哥达基线隧道完全关闭，然后部分重新开放，或者最近发生的山体滑坡摧毁了 A13 高速公路的部分路段，而 A13 高速公路是圣哥达公路隧道的主要替代路线。

面对这样的变化，计算机、在线地图服务或路线规划器如何计算米兰和哥本哈根之间成本最低、速度最快的连接？Kyng 的新算法还能在近乎线性的时间内为这些不断变化或不断减少的网络计算出最佳路线——速度如此之快，以至于每个新连接的计算时间（无论是通过重新路由还是创建新路线而增加的）都可以忽略不计。

但究竟是什么使得 Kyng 的计算方法比其他任何网络流算法都快得多呢？原则上，所有计算方法都面临着这样的挑战：必须多次迭代分析网络，才能找到最佳流量和最低成本路线。在此过程中，它们会逐一分析哪些连接是开放的、关闭的或由于达到容量极限而拥塞的。

计算整体？还是部分？

在 Kyng 之前，计算机科学家倾向于在两种关键策略之间做出选择来解决此问题。其中一种策略以铁路网络为模型，涉及在每次迭代中计算整个网络部分，并修改交通流量。第二种策略——受电网中电力流的启发——在每次迭代中计算整个网络，但对网络每个部分的修改流量使用统计平均值，以加快计算速度。

Kyng 的团队现在将这两种策略各自的优势结合在一起，以创建一种全新的组合方法。“我们的方法基于许多小的、高效的和低成本的计算步骤，这些步骤加在一起比几个大步骤要快得多，”Kyng 团队的讲师兼成员 Maximilian Probst Gutenberg 说，他在开发近乎线性时间的算法中发挥了关键作用。

简要回顾一下这门学科的历史，我们就能更深入地理解 Kyng 的突破性进展的意义：网络中的流问题是 20 世纪 50 年代最早借助算法系统地解决的问题之一，而且流算法在确立理论计算机科学作为一个独立的研究领域方面发挥了重要作用。

数学家 Lester R. Ford Jr. 和 Delbert R. Fulkerson 开发的著名算法也起源于这一时期。他们的算法有效地解决了最大流量问题，该问题旨在确定如何在不超过各个路线容量的情况下通过网络运输尽可能多的货物。

快速且广泛

这些进展向研究人员表明，最大流问题、最小成本问题（转运或运输问题）以及许多其他重要的网络流问题都可以看作是一般最小成本流问题的特殊情况。

在 Kyng 的研究之前，大多数算法只能有效地解决其中一个问题，尽管它们不能特别快速地完成这一点，也无法扩展到更广泛的最小成本流问题。

同样的情况也发生在 20 世纪 70 年代的流算法先驱身上，理论计算机科学家约翰·爱德华·霍普克罗夫特、理查德·曼宁·卡普和罗伯特·恩德雷·塔扬分别因该算法获得了图灵奖，该奖被认为是计算机科学的“诺贝尔奖”。卡普于 1985 年获得该奖，霍普克罗夫特和塔扬于 1986 年获得该奖。

从铁路到电力的视角转变

直到 2004 年，数学家兼计算机科学家 Daniel Spielman 和 Shang-Hua Teng（以及后来的 Samuel Daitch）才成功编写出算法，为最小成本流问题提供快速有效的解决方案。正是这个团队将重点转移到了电网中的电力流上。

他们从铁路到电力的视角转变导致了一个关键的数学区别：如果一列火车因为一条线路停止服务而在铁路网络上改变路线，那么根据时间表，下一个最佳路线可能已经被其他火车占用。

在电网中，组成电力流的电子可能会被部分转移到其他电流已经流过的网络连接中。因此，与火车不同，从数学角度来说，电流可以“部分”转移到新的连接中。

这种部分重新路由使 Spielman 和他的同事能够更快地计算此类路线变化，同时在每次变化后重新计算整个网络。“我们拒绝了 Spielman 为整个网络创建最强大算法的方法，”Kyng 说。

“相反，我们将他的部分路线计算思想应用到了 Hopcroft 和 Karp 的早期方法中。”每次迭代中部分路线的计算对加快整体流量计算起到了重要作用。

理论原则的转折点

苏黎世联邦理工学院研究人员取得的大部分进展都归功于他们决定将工作扩展到开发新算法之外。该团队还使用和设计了新的数学工具，以进一步加快他们的算法速度。

具体来说，他们开发了一种用于组织网络数据的新数据结构。这使得能够非常快速地识别网络连接的任何变化。这反过来又有助于使算法解决方案变得如此之快。

随着如此多的应用程序采用近乎线性时间的算法和诸如新数据结构之类的工具，整体创新螺旋可能很快就会比以前转动得更快。

然而，为解决以前无法有效计算的大型问题奠定基础只是这些速度显著加快的流算法的一个好处——因为它们还改变了计算机计算复杂任务的方式。

加州大学伯克利分校的一个国际研究小组写道：“在过去十年中，在获得可证明的快速算法以解决理论计算机科学基础问题的理论基础方面发生了一场革命。”该研究小组的成员包括苏黎世联邦理工学院理论研究所的研究员拉斯穆斯·金 (Rasmus Kyng) 和迪克沙·阿迪尔 (Deeksha Adil)。