文章图片
文章图片
文章图片
文章图片
文章图片
文章图片
文章图片
文章图片
文章图片
编辑：KingHZ
【新智元导读】清华大学教授段然提出了一种最短路径新方法 ， 击败了教科书中经典的Dijkstra算法 。
计算机科学的重大成果！
清华大学教授刷新最短路径算法认知 ， 或将改写计算机算法教科书 。
在计算机科学中 ， 一个经典问题是寻找网络中每个点的最短路径 ， 而Dijkstra算法是此问题的最经典解决方法 。
自1956年来 ， 最短路径问题吸引了众多研究人员的关注 。
哥本哈根大学计算机科学家Mikkel Thorup米克尔·索鲁普表示:
最短路径是个绝妙的好问题 ， 全世界人都能感同身受 。
直觉上 ， 找到离起点最近的点的路径应该最简单 。
因此 ， 如果想设计一个解决最短路径问题的最快算法 ， 合理的做法是先找到最近的点 ， 然后是次近的点 ， 依此类推 。 但这意味着你需要反复确定哪个点是最近的 ， 也就是说 ， 你得按距离给这些点排序 。
然而 ， 这种方法有一个根本的限制：这种算法的速度无法快过排序所需的时间 。
四十年前 ， 研究最短路径算法的科学家们遇到了这个「排序瓶颈」 。
现在 ， 来自清华大学等机构的研究团队设计了一种新算法 ， 突破了这一瓶颈 。 这种算法不依赖排序 ， 而且比任何需要排序的算法运行得更快 。
论文链接：https://arxiv.org/abs/2504.17033
普林斯顿大学的计算机科学家Robert Tarjan说：「这些研究者大胆地认为他们能打破这个瓶颈 。 这是一个惊艳的成果 。 」
值得一提的是 ， 这项研究摘得STOC最佳论文 ， 实至名归 。
左：Mikkel Thorup；右：Robert Tarjan
最短路径
若想解决复杂难题 ， 条理分明往往事半功倍 。 比如将问题拆解后优先处理最简单的部分——但这种分类需要代价 ， 你可能耗费过多时间在排序上 。
这一困境尤其体现在计算机科学中最经典的问题之一：如何在网络中从特定起点出发 ， 找到通往其他所有点的最短路径 。 这就像日常搬家后必须解决的升级版问题：规划从新家到公司、健身房和超市的最佳路线 。
为了从数学角度分析最短路径问题 ， 研究者们使用图论的语言——图是由点（或称节点）组成的网络 ， 这些点通过线连接起来 。 每条连接线都标有一个数字 ， 叫作权重 ， 它可以代表这段线的长度或穿越它所需的时间 。
通常 ， 任意两个节点之间都有很多路径 ， 最短路径就是那些权重加起来最小的路径 。 给定一个图和一个特定的「起点」 ， 算法的目标就是找到到其他每个节点的最短路径 。
在1956年 ， 计算机科学先驱埃兹赫·迪杰斯特拉（Edsger Dijkstra）设计了日后最著名的最短路径算法 。
它从起点开始 ， 一步步向外扩展 。
Dijkstra算法如何找到最短路径
Dijkstra算法从网络中的一个特定点开始 ， 找到到每个其他点的最短路径 。 它按距离从近到远的顺序找到这些路径 。
Dijkstra算法的基本步骤：
从A点开始：
你看到两条路径 。 B点距离1单位 ， C点距离5单位 。 你现在知道到B的最短路径 ， 但可能有一条更短的间接路径到C 。最短路径：A → B = 1
跟随最短路径：
前往 B ， 然后再观察一次 ， 记录从 A 到每个点的总距离 。 D点比C点离 A 更近 。 最短路径：A → B = 1；A → D = 2
继续探索:
前往D点并再次观察 ， 现在你已经找到了到C的最短路径 。 最短路径 ：A → B = 1；A → D = 2；A → C = 3 。
从起点开始 ， 逐步探索网络中到每个点的最短路径——这种方法很有效 ， 因为知道到附近节点的最短路径 ， 能帮助你找到到更远节点的最短路径 。
但最终结果是一个按距离排序的最短路径列表 ， 因此排序瓶颈设定了算法速度的根本限制 。
1984年 ， Tarjan和另一位研究者改进了迪杰斯特拉的原始算法 ， 使其达到了这个速度极限 。 任何进一步的改进都必须来自一个避免排序的算法 。
论文链接：https://dl.acm.org/doi/10.1145/28869.28874
在20世纪90年代末和21世纪初 ， Thorup和其他研究者设计出了打破排序瓶颈的算法 。
从左至右：Bernhard Haeupler、Václav Rozhoň（上方）、Jakub Tětek（下方）、Robert Tarjan和Richard Hladík证明了Dijkstra算法的一个版本是对所有网络布局的最佳解决方案
他们需要对权重做出某些假设 。 没人知道如何将这些技术扩展到任意权重上 。 似乎他们已经走到了尽头 。
研究停滞了很长一段时间 ， 很多人相信没有更好的办法了 。
但清华的段然不是其中之一 。 他长期梦想构建一个能在所有图上突破排序瓶颈的最短路径算法 。 去年秋天 ， 他终于成功了 。
超越排序
段然对排序瓶颈的关注可以追溯到近20年前 。
那时 ， 他在密歇根大学读研究生 。 他的导师是研究如何在特定情况下打破排序瓶颈的学者之一 。
但直到2021年 ， 段然才找到一个更有前景的方法 。
关键在于关注算法每一步的下一步走向 。
迪杰斯特拉的算法会利用之前已探索的区域 ， 决定下一步通过扫描这个区域的「边界」——也就是所有与边界相连的节点 。 起初这不会花太多时间 ， 但随着算法推进 ， 速度会变慢 。
段然则设想将边界上的相邻节点分组 ， 形成多个集群 。 每一步只考虑每个集群中的一个节点 。 由于需要筛选的节点减少了 ， 每一步的搜索都能更快 。 算法可能不会总是选择最近的节点 ， 因此排序瓶颈不再适用 。 但要确保这种基于集群的方法确实能加速算法 ， 而不是让它更慢 ， 是一个挑战 。
在接下来的一年里 ， 段然完善了这个基本想法 。
到2022年秋天 ， 他乐观地认为自己能克服技术难题 。
他拉来三位研究生帮忙细化细节 ， 几个月后 ， 他们取得了部分成功——开发出了一种算法 ， 打破了任意权重下的排序瓶颈 ， 但仅适用于所谓无向图 。
论文链接：https://arxiv.org/abs/2307.04139
在无向图中 ， 每条连接线都可以双向通行 。 计算机科学家通常更关注包含单向路径的更广义的图类 ， 但这些「有向图」往往更难处理 。
这次新论文的合著者、斯坦福大学计算机科学博士生毛啸说：「（在有向图中）可能存在一种情况 ， A到B很容易 ， 但B到A却很困难 。 这会给你带来很多麻烦 。 」
希望之路
2023年夏天 ， 在加州的一场学术会议上 ， 毛啸聆听了段然关于无向图算法的演讲 。 他主动与这位仰慕已久的学者攀谈起来 。
那是他第一次在现实中见到段然 ， 当时非常激动 。
随机性如何优化算法
会议结束后 ， 毛啸开始利用业余时间思考这个问题 。 与此同时 ， 段和他的团队正在探索适用于有向图的新方法 。 他们从最短路径问题的另一经典算法——贝尔曼-福特算法中汲取灵感 。
贝尔曼-福特算法不生成排序列表 ， 但初看却像是个糟糕的选择：它的速度远逊于迪杰斯特拉算法 。
计算机科学家米克尔·索鲁普补充道：「科研就是不断尝试有潜力的路径 。 但借鉴贝尔曼-福特算法简直像在反其道而行——这看起来蠢透了 。 」
段然的团队通过分阶段运行贝尔曼-福特算法避开了其低速缺陷 。 这种选择性使用让他们能预先侦察后续步骤中最有价值的节点 ， 这些节点如同交通网络中的核心枢纽 。
计算机科学家米克尔·索鲁普解释道：「要获取多数目的地的最短路径 ， 你必须经过这些关键点」 。
2024年3月 ， 毛啸提出另一创新思路 。
原算法中某些关键步骤依赖随机性 ， 虽然随机算法能高效解决许多问题 ， 但学界仍更青睐确定性方案 。
毛啸设计出无需随机化的最短路径求解方法 ， 随后加入团队 。
通过数月的群聊和视频会议 ， 他们最终在秋季取得突破——段然教授意识到可借鉴其2018年解决另一类图问题时突破排序障碍的技术 ， 这正是补齐最后一块拼图的关键 。
层进式革新
最终算法将图分层处理 ， 像迪杰斯特拉算法那样从源头向外推进 。
但其精妙之处在于：通过贝尔曼-福特算法定位关键节点后优先探索 ， 稍后回溯处理其他边界节点 。 由于不严格按距离顺序探索每层节点 ， 排序障碍自然失效 。 若采用恰当的分层策略 ， 其速度甚至略超优化版迪杰斯特拉算法 。
这个由多个精密模块组成的算法虽复杂 ， 却意外地未使用任何高深数学工具 。
计算机科学家米克尔·索鲁普感慨万分：「这套方法本可能在五十年前就被发现 ， 但直到现在才问世 。 这才更显其非凡 。 」
段然团队正着手优化算法以追求更快的速度 。 随着排序障碍的攻克 ， 新算法的运行效率已远超现有理论极限 。
参考资料：
https://www.quantamagazine.org/new-method-is-the-fastest-way-to-find-the-best-routes-20250806/
https://www.cnblogs.com/gaochundong/p/bellman_ford_algorithm.html
【突破40年Dijkstra算法瓶颈，清华教授等颠覆教科书！STOC最佳论文】https://iiis.tsinghua.edu.cn/en/People/Faculty/DuanRan.htm
推荐阅读
- 法国科研中心发布医学文本AI识别系统：超越专有软件的开源突破
- 卡内基梅隆大学：AI突破航拍车辆识别难题
- 突破单卡性能上限，新华三超节点一览
- 阿里巴巴联合多所高校突破性研究如何让代码修复变得更聪明
- 字节跳动：AI系统突破国际奥数5题证明
- 正式交付！中国半导体装备重大突破，技术指标已超越日本！
- 中兴在中亚取得重要突破！
- 腾讯混元团队：让图像生成模型重新崛起的革命性突破
- 人工智能学会了看懂动作！复旦大学团队的视频识别新突破
- 北京交大与微软亚研：突破性评估多模态AI诚实度