A Faster Shortest Path Algorithm
4 hours ago
- 问题是在具有非负实数边权的有向图中寻找精确最短路径，Dijkstra算法使用斐波那契堆的时间复杂度为O(m + n log n)。
- 一种名为C-HD的新算法由10个Claude Opus 5.5智能体在大约15小时内开发完成，利用留言板进行协作，并在Lean中进行了形式化验证。
- C-HD在特定密度区间（m ≈ n^(3/2)）取得了更好的渐近界：O(n + m + m log(2 + m/(n+1)) + m^(1/3) (n log(n+2))^(2/3))，优于Dijkstra算法和近期的最优界。
- 该算法使用有界局部搜索、边删除和局部不变式来减少重复工作，尽管预处理包括对出边列表进行排序。
- 形式化的Lean证明确立了运行时界以及沿所述密度曲线的严格渐近改进，并由Lean Comparator工具验证。
- 尽管有理论上的改进，但常数巨大，因此该算法可能不会带来实际的速度提升；它未在大型真实图上进行基准测试。
- 该项目表明，多智能体系统通过并行探索、同行评审和迭代问题求解，可以显著压缩研究时间。