研究人员开发出最快的网络流算法
瑞士联邦理工学院（ETH Zurich）的研究人员开发出了一种几乎完美的算法，可以以最快的速度计算任何类型网络的最大运输流量和最低运输成本。这项算法的速度在数学上已经达到了极限。
1. 突破性的网络流算法
ETH Zurich的计算机科学家Rasmus Kyng及其团队在理论计算机科学领域取得了重大突破，开发了一种超快速的网络流算法。该算法可以在最短时间内计算出任何网络的最大流量和最低运输成本，从而解决了网络流量优化的关键问题。
2. 算法性能卓越，超越历史极限
在Kyng之前，没有人能够在读取网络数据的同时计算出最优解决方案。传统方法需要更长时间进行计算，尤其在面对大型复杂网络时，计算时间往往会大幅增加。Kyng的算法解决了这个问题，使得计算时间和网络规模同步增长。
3. 快速应对动态变化的网络
Kyng的团队不仅优化了静态网络的计算，还针对动态变化的网络提出了新的解决方案。比如，当网络中新增或删除连接时，他们的算法仍能以近乎线性的时间计算出最优路径。这对处理如生物分子、人脑网络等复杂动态系统具有重要意义。
4. 小步快跑的计算策略
Kyng的创新之处在于结合了两种传统方法的优点，通过许多小而高效的计算步骤来提升整体速度，而不是进行大规模计算。这种方法不仅提高了速度，还使得算法在面对不同网络变化时更加灵活。
5. 广泛应用前景
这种几乎线性时间的算法不仅改变了计算复杂任务的方式，还为解决以前无法高效计算的大规模问题奠定了基础。未来，这些算法有望在交通运输、电网管理甚至社交网络分析等领域得到广泛应用。获取更多有价值信息 访问：https://byteclicks.com
参考
van den Brand, J、Chen, L、Kyng, R、Liu, YP、Meierhans, S、Probst Gutenberg, M、Sachdeva, S。递减图的准线性时间算法：通过对偶实现最小成本流及更多算法。第 65 届 IEEE 计算机科学基础研讨会 (FOCS) 2024。https://focs.computer.org/2024/accepted-papers-for-focs-2024/
Chen, L, Kyng, R, Liu, YP, Meierhans, S, Probst Gutenberg, M. 增量图的准线性时间算法：循环检测、SCC、st 最短路径和最小成本流。第 56 届 ACM 计算理论研讨会论文集，2024 年 6 月 (STOC 2024)。doi：https://doi.org/10.1145/3618260.3649745。
Chen, L, Kyng, R, Liu, YP, Peng, R, Probst Gutenberg, M, Sachdeva, S, Kyng, R. 几乎线性时间内的最大流和最小成本流。2022 年 IEEE 第 63 届计算机科学基础年会 (FOCS)，美国科罗拉多州丹佛市，2022 年。doi:10.1109/FOCS54457.2022.00064。
更多信息
研究人员实现了‘极快’的网络流算法。”（Quanta Magazine。2022 年 6 月 8 日）。
