{"id":"mb-20260901-304e38","account":"mubei","brand":"","title":"清华大学的研究团队，打破了一项保持 41 年的计算机算法世界纪录","summary":"清华大学的研究团队，打破了一项保持 41 年的计算机算法世界纪录","body":"清华大学的研究团队，打破了一项保持 41 年的计算机算法世界纪录。\n\n他们改写了计算机教科书里最基石的算法之一：Dijkstra 最短路径算法。\n\n从手机地图导航、外卖路径规划，到互联网路由协议，底层的寻路逻辑都在用它。\n\n这篇论文拿下了理论计算机顶级会议 STOC 2025 的最佳论文奖（Best Paper Award）。\n\n但这项研究最震撼的地方，不在于算力跑分。\n\n它击穿了一个困扰全世界顶尖学者四十多年的思维盲区。\n\n要看懂这台机器是怎么被拆掉的，得先退回 1984 年。\n\n1959 年，计算机先驱戴克斯特拉（Edsger Dijkstra）提出了最短路径算法。\n\n1984 年，计算机科学家弗雷德曼（Michael Fredman）和塔扬（Robert Tarjan）发明了斐波那契堆，把算法的时间复杂度推进到 O(m + n log n)。\n\n从那以后的整整 41 年里，这个数字成了理论界公认不可逾越的天花板。\n\n为什么这道边界立了 41 年没人能打破？\n\n因为所有人都撞上了一堵墙：排序屏障（Sorting Barrier）。\n\nDijkstra 算法的核心逻辑是贪心策略。\n\n它从起点出发，每一步都要在所有未访问的节点里，精准挑出距离起点最近的那一个。\n\n为了挑出绝对最近的点，算法必须维护一个全局优先队列（Priority Queue）。\n\n这意味着什么？\n\n这意味着你在计算最短路径的同时，顺手把成千上万个节点按距离从近到远，做了一次严密的全局排序。\n\n但在数学上有一条铁律：基于比较的排序算法，把 n 个元素排好序，计算量下界就是 n log n。\n\n既然算法每一步都在做排序，它的速度上限就被死死钉在了排序的数学下界上。\n\n过去 41 年，全世界顶尖学者都在同一个盒子里死磕：怎样把优先队列做得更精巧，怎样在排序里再抠出一点性能。\n\n清华大学段然团队干了一件打破盲点的事。\n\n他们问了一个没人停下来深究的问题：\n\n要算清楚两个点之间的最短距离，真的需要把沿途所有节点都排一遍大小吗？\n\n不需要。\n\n你需要的是从起点到终点的总距离，根本不需要知道第 500 个路口和第 501 个路口谁比谁近了半米。\n\nDijkstra 算法为了算出距离，强迫计算机做了一大堆精密的无用排序。\n\n那笔交了 41 年的排序税，纯粹是附带的冗余负担。\n\n新算法的核心机制，叫递归偏序分治（Recursive Partial Ordering）。\n\n它彻底丢掉了沉重的全局优先队列。\n\n它不再强求每一步都挑出绝对最小的节点。\n\n团队把节点按距离区间扔进粗粒度桶里，只在局部做必要的分治与松弛。\n\n不需要全局全序，只维护局部偏序。\n\n那道卡了全世界 41 年的排序屏障，就这么被绕了过去。\n\n复杂度的理论上限，第一次被压到了 O(m log^(2/3) n)。\n\n很多看似坚不可摧的技术瓶颈，往往不是目标本身有多难。\n\n是我们手里的经典工具，自带了一大堆我们不需要的副产品。\n\n所有人误以为，那个副产品是必须付出的代价。\n\n当所有人都在争着把梯子造得更轻去爬墙的时候。\n\n真正跨过时代的突破，往往只是走上前看了一眼，发现那堵墙原本就可以绕开。","category":"科技","score":null,"translated_x_url":null,"translated_status_id":null,"published_at":"2026-09-01 14:46:14","created_at":"2026-09-01 14:46:14"}