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, и на любом реалистичном графе Дейкстра все еще будет быстрее, даже если у него худшая асимптотика. Так что эту часть еще предстоит проверить.