• 行业咨询
  • 品牌营销
  • 集微资讯
  • 知识产权
  • 集微职场
  • 集微投融资
  • 集微企业库
搜索
爱集微APP下载

扫码下载APP

爱集微APP扫码下载
集微logo
资讯集微报告舆情JiweiGPT企业洞察
2025第九届集微半导体大会集微视频
登录登录
bg_img
search_logo
大家都在搜

清华大学交叉信息研究院段然团队获得STOC 2025最佳论文奖

作者: 集小微 05-14 15:45
相关舆情 AI解读 生成海报
来源:清华大学 #算法# #图论# #清华大学#
7544

近日,清华大学交叉信息院段然团队的论文“突破有向单源最短路径的排序障碍”(Breaking the Sorting Barrier for Directed Single-Source Shortest Paths)在理论计算机国际顶级会议STOC 2025(ACM SIGACT Symposium on Theory of Computing,ACM理论计算特别兴趣小组理论计算研讨会)上获得最佳论文奖。

段然团队探讨了图论算法中经典的“单源最短路径问题(SSSP)”。Dijkstra算法是解决这一问题的基本算法,它以荷兰计算机科学家埃德斯格尔·迪克斯特拉(Edsger Dijkstra)的名字命名。自1956年开发以来,该算法一直被认为是一项里程碑式的贡献,被广泛应用于导航系统等。为了改进Dijkstra算法,该论文仔细研究了造成其大部分计算成本的部分:与所谓“优先队列 ”的交互。在执行过程中,Dijkstra算法需要维护“前沿”,即已经发现但尚未完全处理的顶点集合——这意味着它们与源点的暂定最短距离是已知的,但算法可能尚未完全探索它们的邻近顶点。这些前沿顶点存储在一个优先级队列中,并从中反复提取下一个最近的顶点。Dijkstra算法中的前沿顶点可以多达 “n”,即顶点的数量。每次提取其中一个顶点的操作开销为log(n),因此总时间为n log(n)。研究团队提出的新算法通过融合Dijkstra算法和Bellman-Ford的教科书算法,以及一种巧妙设计的允许分组插入和提取的数据结构,递归地缩小了所考虑的前沿的大小。因此,操作的总数可以大大减少,从而缩短了运行时间,使整个算法运行得更快。

2024年图灵奖得主罗伯特·塔尔扬(Robert Tarjan)及合作者发表的论文证明了Dijkstra算法对于“最短路径排序问题”的普遍最优性,获得了FOCS 2024的最佳论文奖,受到了《量子杂志》(Quanta Magazine)和量子位等媒体的报道。单源最短路径问题需要找到从一点s到其他所有点的最短路,而Dijkstra算法的副产品是所有点按照从源点的距离排序,也就是说他们证明的是Dijkstra算法对于这个排序问题是普遍最优的(universally optimal)。但是段然团队的新算法避免了整体排序,所以得到了比Dijkstra算法更快的最短路径问题的算法。而且最短路径问题明显更加重要,更快的最短路径算法在理论上和实际应用中都有很大意义。

清华大学交叉信息院副教授段然为论文通讯作者,其他作者包括姚班2019届本科毕业生束欣凯,以及姚班毕业生、交叉信息院2022级博士生毛嘉怡和2021级博士生尹龙晖。斯坦福大学2022级博士生毛啸也作出了贡献。

责编: 集小微
来源:清华大学 #算法# #图论# #清华大学#
分享至:
THE END
相关推荐
  • 计算机科学家沈向洋:中国AI算法迅速追赶美国,芯片差距仍需时间弥合

  • 清华大学任天令团队合作在基于石墨烯热声共振腔体的可调频声音增强研究上取得进展

  • 清华大学报道基于衍射与偏振深度线索融合的拓展场景单目三维成像

  • 清华机械系生物制造团队合作构建基于喷墨打印的可多次读写“引物盘”DNA存储系统

  • 清华大学钱翔课题组合作在触觉交互执行器领域取得新进展

  • 清华大学何宏辉课题组合作提出可重构任意椭圆延迟器阵列助力高维光子操控

评论

文明上网理性发言,请遵守新闻评论服务协议

登录参与评论

0/1000

提交内容
    没有更多评论
集小微

微信:

邮箱:


4562文章总数
7509.9w总浏览量
最近发布
  • 中国科大在类脑智能神经形态器件领域取得新进展

    16小时前

  • 中国科大高功率密度电源芯片与W波段接收机芯片亮相VLSI 2025

    16小时前

  • 中国科学院半导体所集体导模共振手性激光器研发取得进展

    16小时前

  • 电子科技大学在触觉智能感知器件与集成微系统领域取得重要研究成果

    16小时前

  • 中国AI模型全球走俏,快速削弱美国领先优势

    17小时前

最新资讯
  • 【市场】比亚迪巴西乘用车工厂首车下线;

    31分钟前

  • 【专利】三星收购部分英特尔半导体专利权;

    31分钟前

  • 传索尔思转手陆资 台湾立委呼吁“避免半导体技术被移转”

    32分钟前

  • 传立讯精密寻求赴港上市 募资规模上看10亿美元

    32分钟前

  • OpenAI砸重金租Oracle算力 星门计划加速落地

    32分钟前

  • 特斯拉暂停人形机器人Optimus生产 修改设计

    32分钟前

关闭
加载

PDF 加载中...

集微logo
网站首页 版权声明 集微招聘 联系我们 网站地图 关于我们 商务合作 rss订阅

联系电话:

0592-6892326

新闻投稿:

laoyaoba@gmail.com

商务合作:

chenhao@ijiwei.com

问题反馈:

1574400753 (QQ)

集微官方微信

官方微信

集微官方微博

官方微博

集微app

APP下载

Copyright 2007-2023©IJiWei.com™Inc.All rights reserved | 闽ICP备17032949号

闽公网安备 35020502000344号