拉斯穆斯·金(RasmusKyng)和他的团队取得了突破，他们开发出了一种超快的算法，看起来将改变整个研究领域，这让人想起了幸运卢克(LuckyLuke)，那个射击速度比他的影子还快的人。
Kyng团队的开创性工作涉及所谓的网络流算法，该算法解决了如何在网络中实现最大流量同时最小化传输成本的问题。
想象一下，您正在使用欧洲交通网络，并寻找最快、最便宜的路线，以便将尽可能多的货物从哥本哈根运送到米兰。在这种情况下，Kyng的算法可以用于计算任何类型网络(无论是铁路、公路、水路还是互联网)的最佳、成本最低的交通流量。
他的算法执行这些计算的速度非常快，以至于它可以在计算机读取描述网络的数据时立即提供解决方案。
网络计算速度很快
在Kyng之前，没有人能够做到这一点——尽管研究人员已经研究这个问题大约90年了。以前，计算最佳流量所花的时间比处理网络数据所花的时间要长得多。
随着网络变得越来越大、越来越复杂，所需的计算时间相对而言比计算问题的实际规模增长得更快。这就是为什么我们也看到网络中的流问题太大，计算机甚至无法计算。
Kyng的方法消除了这个问题：使用他的算法，计算时间和网络规模以相同的速率增加——有点像去徒步旅行，无论路有多陡峭，始终保持相同的步伐。
只要看一下原始数据，就能知道我们已经取得了多大的进步：直到千禧年，没有任何算法的计算速度能够超过m1.5，其中m代表计算机必须计算的网络中的连接数，并且仅读取一次网络数据就需要m时间。
2004年，解决该问题所需的计算速度成功降低至1.33m。使用Kyng的算法，读取网络数据后得出解决方案所需的“额外”计算时间现在可以忽略不计。
就像保时捷和马车赛跑一样
苏黎世联邦理工学院的研究人员由此开发出了理论上最快的网络流算法。两年前，Kyng和他的团队在一篇开创性的论文中展示了他们概念的数学证明。科学家将这些新颖的、几乎最佳速度的算法称为“几乎线性时间算法”，理论计算机科学家界对Kyng的突破既惊讶又热情。
Kyng的博士生导师、耶鲁大学应用数学和计算机科学教授DanielA.Spielman本人也是该领域的先驱和资深人士，他将这种“快得离谱”的算法比作保时捷超越马车。
他们的论文不仅赢得了IEEE计算机科学基础年度研讨会(FO)的2022年度最佳论文奖，还在ACM的计算期刊《通讯》上重点介绍，而科普杂志《Quanta》的编辑将Kyng的算法评为2022年计算机科学十大发现之一。
苏黎世联邦理工学院的研究人员此后不断改进他们的方法，并开发出更多近乎线性时间的算法。例如，第一个算法仍然侧重于固定的静态网络，这些网络的连接是定向的，这意味着它们的功能就像城市道路网络中的单行道一样。
今年发布的算法现在还能够计算随时间逐渐变化的网络的最佳流量。闪电般快速的计算是解决高度复杂且数据丰富的网络的重要一步，这些网络动态且快速地变化，例如生物学中的分子或大脑，或人类的友谊。
用于改变网络的闪电般快速的算法
周四，Kyng团队成员SimonMeierhans在温哥华举行的ACM计算理论年度研讨会(STOC2024)上展示了一种新的近乎线性时间算法。该算法解决了随着新连接的增加而逐渐变化的网络的最小成本最大流问题。
此外，在10月份IEEE计算机科学基础研讨会(FO)接受的第二篇论文中，ETH的研究人员开发了另一种处理连接断开的算法。
具体来说，这些算法会在添加或删除连接时识别出最短路线。在现实世界的交通网络中，瑞士此类变化的例子包括自2023年夏季以来几个月内圣哥达基线隧道完全关闭，然后部分重新开放，或者最近发生的山体滑坡摧毁了A13高速公路的部分路段，而A13高速公路是圣哥达公路隧道的主要替代路线。
面对这样的变化，计算机、在线地图服务或路线规划器如何计算米兰和哥本哈根之间成本最低、速度最快的连接?Kyng的新算法还能在近乎线性的时间内为这些不断变化或不断减少的网络计算出最佳路线——速度如此之快，以至于每个新连接的计算时间(无论是通过重新路由还是创建新路线而增加的)都可以忽略不计。
但究竟是什么使得Kyng的计算方法比其他任何网络流算法都快得多呢?原则上，所有计算方法都面临着这样的挑战：必须多次迭代分析网络，才能找到最佳流量和最低成本路线。在此过程中，它们会逐一分析哪些连接是开放的、关闭的或由于达到容量极限而拥塞的。
计算整体?还是部分?
在Kyng之前，计算机科学家倾向于在两种关键策略之间做出选择来解决此问题。其中一种策略以铁路网络为模型，涉及在每次迭代中计算整个网络部分，并修改交通流量。第二种策略——受电网中电力流的启发——在每次迭代中计算整个网络，但对网络每个部分的修改流量使用统计平均值，以加快计算速度。
Kyng的团队现在将这两种策略各自的优势结合在一起，以创建一种全新的组合方法。“我们的方法基于许多小的、高效的和低成本的计算步骤，这些步骤加在一起比几个大步骤要快得多，”Kyng团队的讲师兼成员MaximilianProbstGutenberg说，他在开发近乎线性时间的算法中发挥了关键作用。
简要回顾一下这门学科的历史，我们就能更深入地理解Kyng的突破性进展的意义：网络中的流问题是20世纪50年代最早借助算法系统地解决的问题之一，而且流算法在确立理论计算机科学作为一个独立的研究领域方面发挥了重要作用。
数学家LesterR.FordJr.和DelbertR.Fulkerson开发的著名算法也起源于这一时期。他们的算法有效地解决了最大流量问题，该问题旨在确定如何在不超过各个路线容量的情况下通过网络运输尽可能多的货物。
快速且广泛
这些进展向研究人员表明，最大流问题、最小成本问题(转运或运输问题)以及许多其他重要的网络流问题都可以看作是一般最小成本流问题的特殊情况。
在Kyng的研究之前，大多数算法只能有效地解决其中一个问题，尽管它们甚至不能特别快速地完成这一点，也无法扩展到更广泛的最小成本流问题。
同样的情况也发生在20世纪70年代的流算法先驱身上，理论计算机科学家约翰·爱德华·霍普克罗夫特、理查德·曼宁·卡普和罗伯特·恩德雷·塔扬分别因该算法获得了图灵奖，该奖被认为是计算机科学的“诺贝尔奖”。卡普于1985年获得该奖，霍普克罗夫特和塔扬于1986年获得该奖。
从铁路到电力的视角转变
直到2004年，数学家兼计算机科学家DanielSpielman和Shang-HuaTeng(以及后来的SamuelDaitch)才成功编写出算法，为最小成本流问题提供快速有效的解决方案。正是这个团队将重点转移到了电网中的电力流上。
他们从铁路到电力的视角转变导致了一个关键的数学区别：如果一列火车因为一条线路停止服务而在铁路网络上改变路线，那么根据时间表，下一个最佳路线可能已经被其他火车占用。
在电网中，组成电力流的电子可能会被部分转移到其他电流已经流过的网络连接中。因此，与火车不同，从数学角度来说，电流可以“部分”转移到新的连接中。
这种部分重新路由使Spielman和他的同事能够更快地计算此类路线变化，同时在每次变化后重新计算整个网络。“我们拒绝了Spielman为整个网络创建最强大算法的方法，”Kyng说。
“相反，我们将他的部分路线计算思想应用到了Hopcroft和Karp的早期方法中。”每次迭代中部分路线的计算对加快整体流量计算起到了重要作用。
理论原则的转折点
苏黎世联邦理工学院研究人员取得的大部分进展都归功于他们决定将工作扩展到开发新算法之外。该团队还使用和设计了新的数学工具，以进一步加快他们的算法速度。
具体来说，他们开发了一种用于组织网络数据的新数据结构。这使得能够非常快速地识别网络连接的任何变化。这反过来又有助于使算法解决方案变得如此之快。
由于如此多的应用程序采用近乎线性时间的算法和诸如新数据结构之类的工具，整体创新螺旋可能很快就会比以前转动得更快。
然而，为解决以前无法有效计算的大型问题奠定基础只是这些速度显著加快的流算法的一个好处——因为它们还改变了计算机计算复杂任务的方式。
加州大学伯克利分校的一个国际研究小组写道：“在过去十年中，在获得可证明的快速算法以解决理论计算机科学基础问题的理论基础方面发生了一场革命。”该研究小组的成员包括苏黎世联邦理工学院理论研究所的研究员拉斯穆斯·金(RasmusKyng)和迪克沙·阿迪尔(DeekshaAdil)。
标签：
免责声明：本文由用户上传，如有侵权请联系删除！