算法与理论计算机2024arxiv.org编辑精选
通过超越最坏情况堆实现 Dijkstra 的通用最优性
Universal optimality of Dijkstra via beyond-worst-case heaps
专业 · 约 90 分钟读完前置知识：Dijkstra 算法、堆与优先队列、摊还分析
导读
这篇论文研究 Dijkstra 算法在超越最坏情况的堆（beyond-worst-case heaps）下的普遍最优性。核心结论是：若堆具有 working-set property，Dijkstra 能充分利用图的结构特征，达到任何基于比较的算法所能达到的最优程度。
HN 关注点：这一经典算法为何能被证明具有“普遍最优性”，并讨论它与 A*、动态图路径规划以及非比较算法之间的关系。
HN 评论精选
这几条评论里：质疑 1 补充 2
补充讨论路径规划中超 Dijkstra 的技术、D* Lite 在动态图上的退化，以及 TDH 预计算在变化图中的取舍。
过去一两周我深入研究了路径查找（这也不是第一次）。当你对图拓扑有一定了解时，可以用不同技术做得比 Dijkstra 更好。当然，如果有大量时间和空间且图完全静态，可以跑全源最短路并存储所有结果，实现 O(1) 查询；但针对不同类型图还有各种折中方案，这篇 Stack Exchange 文章是不错的综述：https://cstheory.stackexchange.com/questions/11855/how-do-the-state-of-the-art-pathfinding-algorithms-for-changing-graphs-d-d-l。我一直在想 D* Lite 在略有变化的图上实际表现如何。有说法称，只要图偶尔变化一点，它多半会退化成 A*，因为许多受影响的路径需要重新评估。在游戏语境下，我还考虑过 true distance heuristics（TDH）：预计算一些固定节点间的距离，作为 A*（或 D* Lite）启发式的一部分；但在变化图中更新这些 TDH 的开销可能和没有它们一样大。不过，若有一些比道路快得多的“线路”（比如铁路线），这可能是有趣的权衡。
foota查看英文原文
I've gone down a bit of a rabbit hole on path finding in the last week or two (most recently, this isn't the first time). When you have some knowledge of the topology of the graph you can use different techniques to do better than djikstra's. Of course, if you have lots of time and space and a completely static graph, you can run all pairs shortest paths and simply store all the results for O(1) path lookup, but there are intermediates for varying types of graphs. This stack exchange article is a good overview: https://cstheory.stackexchange.com/questions/11855/how-do-the-state-of-the-art-pathfinding-algorithms-for-changing-graphs-d-d-l. I've been wondering about how well D* lite would perform in practice with a somewhat varying graph. I read some suggestions that if the graph is changing even a bit on occasion, then it will mostly degrade to A*, since many changed paths would need to be re-evaluated. In the context of games, I've also been thinking about a technique called true distance heurustics (TDH), where you essentially precompute the distances between some fixed set of nodes, and then use those as a part of the heurustic for A* (or D* lite in this case), but it seems like updating these TDH in the case of a changing graph might introduce just as much overhead as not having them in the first place. It might be an interesting trade off though, if you have some "lines" (e.g., think train lines) that are much faster than roadways, you could handle each of these specially via the TDH, and in exchange you would be able to assume a lower "max speed" for use with the A* heurustic, allowing you to explore fewer paths (since with a lower "max speed" paths will more rapidly increase in cost), whereas if you had to assume all car based paths could move as fast as a train, you would have to explore more paths.
补充追问在比较模型之外是否存在类似基数排序的最短路算法。
摘要里说：“我们的普遍最优性结果揭示了这一性质与 Dijkstra 算法之间出奇简洁的相互作用：任何具有 working set property 的堆，都能让算法充分利用它所操作图的每一个结构属性，达到任何基于比较的算法所能达到的最大程度。”最后这句让我好奇：不基于比较的最短路算法会是什么样？是否也有类似 radix sort 的方法，能超越基于比较的最短路算法？
vanderZwan查看英文原文
> Our universal optimality result reveals a surprisingly clean interplay between this property and Dijkstra’s algorithm: Any heap with the working set property enables the algorithm to efficiently leverage every structural attribute of the graph it operates on, to the fullest extent that any comparison-based algorithm possibly can. That last bit makes me wonder: what would a shortest path algorithm without comparisons look like? Are there also "radix sort" like approaches to shortest-path algorithms that surpass comparison-based algorithms or something?
质疑询问论文结论是否说明 Dijkstra 能优于 A*。
这是否意味着 Dijkstra 算法能比 A* 之类的算法表现更好？
fiddlerwoaroof查看英文原文
Does this mean that Dijkstra’s algorithm can perform better than something like A*?
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
历次讨论
- 2024Hacker News 讨论帖203 分 · 47 评
同领域还值得读
哲学家为何应关注计算复杂性
Why Philosophers Should Care About Computational Complexity (2011)
Scott Aaronson 的这篇长文论证计算复杂性理论（如 P vs NP、停机问题的复杂度视角）对哲学问题（如知识的本质、中文房间、水槽论证等）具有实质意义，而不仅是技术细…
算法与理论计算机2015 · 552 分 · 120 评进阶 · 约 90 分钟编辑精选通信的数学理论
A Mathematical Theory of Communication
是香农1948年的《通信的数学理论》，为通信建立数学框架：把信息量定义为不确定性或自由度（信息熵），并讨论信源编码、信道容量与可靠传输。
算法与理论计算机2020 · 495 分 · 91 评进阶 · 约 120 分钟编辑精选物理、拓扑、逻辑与计算：罗塞塔石碑
Physics, Topology, Logic and Computation: A Rosetta Stone (2009)
用范畴论充当“罗塞塔石碑”，试图在量子物理、拓扑、逻辑与计算四个领域之间建立统一的结构性类比：物理中的量子过程、拓扑中的配边、逻辑中的证明和计算中的程序，都可被视为某类范畴中的态…
算法与理论计算机2009 · 390 分 · 55 评 · 引用 13专业 · 约 180 分钟编辑精选一种快速、极小内存的一致性哈希算法
A Fast, Minimal Memory, Consistent Hash Algorithm
论文给出一种快速、省内存的一致哈希方案，目标是在桶数量变化时保持较小的键迁移成本，同时降低计算和内存开销。
算法与理论计算机2014 · 327 分 · 57 评 · 引用 4进阶 · 约 25 分钟编辑精选第五个 Busy Beaver 值的确定
Determination of the fifth Busy Beaver value
宣布确定了第五个 Busy Beaver 值 BB(5)：即 5 状态图灵机中停机前运行步数最多的机器（Champion）在 47,176,870 步后停机。
算法与理论计算机2025 · 288 分 · 116 评 · 引用 1专业 · 约 75 分钟编辑精选