研究人员开发出最快的流动算法
几乎最快速流算法背后的两位思想家：Rasmus Kyng 和 Maximilian Probst Gutenberg。图片来源：苏黎世联邦理工学院 / Nicola Pitaro 拉斯穆斯·金 (Rasmus Kyng) 和他的团队取得了突破，他们开发出了一种超快的算法，看起来将改变整个研究领域，这让人想起了幸运卢克（Lucky Luke），那个射击速度比他的影子还快的人。 Kyng 团队的开创性工作涉及所谓的网络流算法，该算法解决了如何在网络中实现最大流量同时最小化传输成本的问题。 想象一下，您正在使用欧洲交通网络，并寻找最快、最便宜的路线，以便将尽可能多的货物从哥本哈根运送到米兰。在这种情况下，Kyng 的算法可以用于计算任何类型网络（无论是铁路、公路、水路还是互联网）的最佳、成本最低的交通流量。 他的算法执行这些计算的速度非常快，以至于它可以在计算机读取描述网络的数据时立即提供解决方案。 网络计算速度很快 在 Kyng 之前，没有人能够做到这一点——尽管研究人员已经研究这个问题大约 90 年了。以前，计算最佳流量所花的时间比处理网络数据所花的时间要长得多。 随着网络变得越来越大、越来越复杂，所需的计算时间相对而言比计算问题的实际规模增长得更快。这就是为什么我们也看到网络中的流问题太大，计算机甚至无法计算。 Kyng 的方法消除了这个问题：使用他的算法，计算时间和网络规模以相同的速率增加——有点像去徒步旅行，无论路有多陡峭，始终保持相同的步伐。 看一下原始数据就能知道我们已经走了多远：直到千禧年，还没有一种算法能够比 m1.5，其中m代表计算机需要计算的网络连接数，仅仅读取一次网络数据就需要m时间。 2004年，解决该问题所需的计算速度成功降低至m1.33使用Kyng的算法，读取网络数据后到达解决方案所需的“额外”计算时间现在可以忽略不计。 就像保时捷和马车赛跑一样 因此，苏黎世联邦理工学院的研究人员开发出了理论上最快的网络流算法。两年前，Kyng 和他的团队在一项开创性的研究中展示了他们概念的数学证明 纸科学家将这些新颖的、几乎最优的快速算法称为“近似线性时间算法”，而理论计算机科学家界对 Kyng 的突破既惊讶又热情。 Kyng 的博士生导师、耶鲁大学应用数学和计算机科学教授 Daniel A. Spielman 本人也是该领域的先驱和资深人士，他将这种“快得离谱”的算法比作保时捷超越马车。 他们的论文不仅获得了 IEEE 计算机科学基础年度研讨会 (FOCS) 2022 年最佳论文奖，还 突出显示 在计算杂志上 ACM 通讯，科普杂志《Quanta》的编辑们将 Kyng 的算法评为 […]