那个比影子还快的人——拉斯穆斯·金和他的团队开发了一种超快算法，看起来将改变整个研究领域。金团队的开创性工作涉及所谓的网络流算法，该算法解决了如何在网络中实现最大流量同时最小化传输成本的问题。

想象一下，您正在使用欧洲交通网络，并寻找最快、最便宜的路线，以便将尽可能多的货物从哥本哈根运送到米兰。在这种情况下，Kyng 的算法可以用于计算任何类型网络(无论是铁路、公路、水路还是互联网)的最佳、成本最低的交通流量。他的算法执行这些计算的速度非常快，以至于它可以在计算机读取描述网络的数据时提供解决方案。

网络计算速度很快

在 Kyng 之前，没有人能够做到这一点——尽管研究人员已经研究这个问题大约 90 年了。以前，计算最佳流量所花的时间比处理网络数据所花的时间要长得多。随着网络变得越来越大、越来越复杂，所需的计算时间相对而言比计算问题的实际规模增长得更快。这就是为什么我们也看到网络中的流量问题太大而计算机甚至无法计算的原因。

Kyng 的方法消除了这个问题：使用他的算法，计算时间和网络规模以相同的速率增加——有点像徒步旅行，无论路有多陡峭，都始终保持相同的步伐。看一下原始数据，就能知道我们已经取得了多大的进步：直到 2000 年，还没有一种算法的计算速度能超过 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 计算理论年度研讨会 (STOC) 上介绍了一种新的近乎线性时间算法。该算法解决了随着新连接的增加而逐渐变化的网络的最小成本最大流问题。此外，在 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 开发的著名算法也源于这一时期。他们的算法有效地解决了最大流问题，该问题旨在确定如何在不超过各个路线容量的情况下通过网络运输尽可能多的货物。