10 агентов Opus 5.5 за 15 часов обнаружили алгоритм поиска кратчайшего пути, превосходящий Дейкстру
Поиск кратчайшего пути – классическая проблема теории графов, на решении которой основываются навигаторы, роутинг в интернете, логистика и куча других задач современного мира. В 1959 году нидерландский информатик Эдсгер Дейкстра предложил для поиска кратчайшего пути алгоритм O(m + n log n), который следующие 65 лет оставался золотым стандартом и использовался буквально везде.
В 2025-м команда из Цинхуа, Стэнфорда и Института Макса Планка впервые обошла его с оценкой O(m log^{2/3} n). Однако выигрыш их решения раскрывается только на достаточно плотных графах (число ребер m ≥ числа вершин n). На разреженных графах Дейкстра все еще был лучше.
Vals AI решили потестировать новый Opus 5.5 именно на этом непобитом диапозоне (
блогпост). Они запустили 10 агентов, дали им задачу и доску объявлений, чтобы те могли обмениваться идеями и кооперироваться.
В итоге за 15 часов и 733 сообщений агенты получили алгоритм C-HD и формально его верифицировали.
Это первое доказанное улучшение именно в этой разреженной зоне, где лучшим все еще был Дейкстра: при m ≈ n·log^{3/4}n C-HD дает O(n·log^{11/12}n) против O(n log n) у Дейкстры: при n = 2^1000 выигрыш составляет ~1,78х и растет с размером графа.
Правда, несмотря на всю мощь того, как это звучит, и на наличие доказательства в Lean, о практическом ускорении речи пока нет, потому что оценки из предыдущего абзаца –асимптотические, а на реальных графах алгоритм пока не бенчмаркали. То есть при n → ∞ одна кривая гарантировано обгонит другую, однако на практике точка перегиба может возникать только при огромных n, и на любом реалистичном графе Дейкстра все еще будет быстрее, даже если у него худшая асимптотика. Так что эту часть еще предстоит проверить.
