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