写点什么

苏黎世联邦理工学院研发史上最快网络流算法

  • 2024-07-02
    北京
  • 本文字数:1099 字

    阅读完需:约 4 分钟

苏黎世联邦理工学院研发史上最快网络流算法

近日, 苏黎世联邦理工学院计算机系的 Rasmus Kyng 在网络流算法方面取得了显著的进展。其团队开发了一种新的网络流算法,能够在几乎线性的时间里计算最大运输流量,这意味着其运行时间将接近数学理论中的计算速度。



Kyng 的博士生导师、耶鲁大学应用数学和计算机科学教授丹尼尔·A·斯皮尔曼(Daniel A. Spielman)将这种”快得离谱“的算法比作保时捷超跑;苏黎世联邦理工学院官方也做出评价:超快算法为未来高效计算超大型动态变化的网络奠定了基础,有望改变整个研究领域。


那么,是什么让 Kyng 的计算方法能比其他网络流算法都要快呢?


原则上,所有计算方法都必须多次迭代分析网络,以找到最佳流量和最低成本路线。在 Kyng 团队之前,研究人员一般通过两种方案来解决这一问题:


  • 以铁路网络为模型,在每次迭代中对整个网络进行计算,并对交通流量进行修改;


  • 在每次迭代中计算整个网络,但对网络每个部分的修改流量使用统计平均值。


而 Kyng 的团队则是将这两种策略各自的优势结合在一起,创造出了一种新的组合方法。Kyng 团队成员表示,“我们的方法是基于很多小的、低成本的计算步骤,这些步骤加起来比几个大的步骤快得多。”

论文中提出的算法主要解决以下几个问题:


  • 环检测(Cycle Detection):检测图中是否存在环。


  • 强连通分量维护(Strongly Connected Component Maintenance, SCCs):维护图中的强连通分量。


  • 单源最短路径(s-t Shortest Path):计算图中单源到单目标的最短路径。


  • 最小成本流(Minimum-Cost Flow):在满足容量限制的情况下,找到成本最小的流。





相比于现有算法,Kyng 团队新网络流算法具有独特优势:


  • 基于断链的标号算法:新算法广泛吸取了标号算法的最新成果,并引进了断链的基本概念,提出了一种基于断链求解网络最大流的新标号算法。这种方法在处理大规模、高复杂度的网络流问题时表现更为优异,能够有效提高算法的效率和准确性。


  • 仿真实验验证:通过实例和仿真实验进行了验证,证明了新算法的有效性和可靠性。


网络流算法在多个领域都发挥着重要作用。它通过构建网络模型来优化各种流程,提高效率,降低成本。在物流优化方面,算法帮助优化运输路径,提升运输效率并减少开支。电路布线设计方面,也通过此算法,确保电路运行的高效性和可靠性。此外,在网络设计中,算法可以优化数据传输路径,保障数据传输的高效与稳定。


该研究不仅为为解决以前无法有效计算的非常大规模问题奠定了基础,同时,还改变了计算机计算复杂任务的方式。


参考链接:

https://ethz.ch/en/news-and-events/eth-news/news/2024/06/researchers-at-eth-zurich-develop-the-fastest-possible-flow-algorithm.html

论文原文:

https://dl.acm.org/doi/10.1145/3618260.3649767

2024-07-02 15:439955

评论 1 条评论

发布
用户头像
👍
2024-07-14 17:35 · 巴勒斯坦
回复
没有更多了
发现更多内容

深入了解京东API接口:高效获取商品SKU与价格信息

代码忍者

京东API接口

霸榜GitHub周榜!Java面试福音,逼自己一周背完上岸大厂!

程序员高级码农

Java 编程 程序员 java面试 Java面试题

webGL外包开发的技术难点

北京木奇移动技术有限公司

数字孪生 软件外包公司 webgl开发

膜拜!阿里自爆十万字Java面试手抄本,脉脉一周狂转50w/次

程序员高级码农

Java 编程 程序员 java面试 Java面试题

Microsoft Office LTSC 2021 for Mac:稳定高效的办公软件套件

小玖_苹果Mac软件

NFT市场回暖:蓝筹项目成为复苏主力,空投潮助推价格上涨

区块链软件开发推广运营

交易所开发 dapp开发 链游开发 公链开发 代币开发

原生APP外包开发的费用

北京木奇移动技术有限公司

软件外包公司 APP外包公司 APP外包开发

MaxCompute Bloomfilter index在蚂蚁安全溯源场景大规模点查询的最佳实践

阿里云大数据AI技术

大数据 数据处理 布隆过滤器 数据检索 MaxCompute

Java程序员的编程能力要如何进阶?

了不起的程序猿

程序员 后端 架构师 java面试 Java进阶

Microsoft Remote Desktop for Mac:跨平台远程桌面连接利器

小玖_苹果Mac软件

实战技巧 DevEco Profiler 性能调优 Time

万少

鸿蒙

闪迪品牌预告全新企业品牌形象,宣布即将焕新启程

Geek_2d6073

AscendC从入门到精通系列(四)使用Pybind调用AscendC算子

zjun

算子 CANN 昇腾 AscendCL Ascend

AscendC从入门到精通系列(五)调用基于工程开发AscendC算子

zjun

算子 CANN 昇腾 AscendCL Ascend

接口自动化测试中切换多套被测环境方法

测试人

软件测试

集成自然语言理解服务,让应用 “听得懂人话”

不在线第一只蜗牛

人工智能

面试官:DNS解析都整不明白,敢说你懂网络?我:嘤嘤嘤!

EquatorCoco

面试

AscendC从入门到精通系列(三)基于自定义算子工程开发AscendC算子

zjun

算子 CANN 昇腾 AscendCL Ascend

原生APP外包开发流程

北京木奇移动技术有限公司

APP开发 软件外包公司 APP外包公司

SD云端部署哪个好?适合SD部署的桌面云工作站

青椒云桌面

云桌面 sd云端部署 云工作站

考核数据管理系统(源码+文档+部署+讲解)

深圳亥时科技

如何在 Apifox 中发布多语言的 API 文档?

Apifox

前端 接口文档 swagger API接口文档 API 文档

【论文速读】| FirmRCA:面向 ARM 嵌入式固件的后模糊测试分析,并实现高效的基于事件的故障定位

云起无垠

AscendC从入门到精通系列(二)基于Kernel直调开发AscendC算子

zjun

算子 CANN 昇腾 AscendCL Ascend

Navicat Premium 15 for Mac:强大数据库管理和开发利器

小玖_苹果Mac软件

淘宝图片搜索接口(Taobao.item_search_img)

tbapi

淘宝API接口 淘宝拍立淘接口 淘宝图片搜索商品接口

阿里架构师耗时一个月肝出这份26W字Java面试手册,在Github标星30K+

架构师之道

编程 计算机 java面试

阿里巴巴1688 API接口深度解析:如何高效获取商品详情与关键词搜索商品数据

代码忍者

1688API接口

苏黎世联邦理工学院研发史上最快网络流算法_大数据_赵明华_InfoQ精选文章