10 агентов Opus 5.5 за 15 часов обнаружили алгоритм поиска кратчайшего пути, превосходящий Дейкстру
Десять автономных агентов на базе модели Opus 5.5 за 15 часов разработали и формально верифицировали новый алгоритм поиска кратчайшего пути C-HD, который теоретически превосходит алгоритм Дейкстры на разреженных графах.
Поиск кратчайшего пути – классическая проблема теории графов, на решении которой основываются навигаторы, роутинг в интернете, логистика и куча других задач современного мира. В 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, и на любом реалистичном графе Дейкстра все еще будет быстрее, даже если у него худшая асимптотика. Так что эту часть еще предстоит проверить.
Почему это важно
АналитикаЭто демонстрирует новый уровень автономности ИИ-агентов в решении фундаментальных научных задач: они способны не просто генерировать код, а создавать и формально верифицировать новые алгоритмы, превосходящие многолетние стандарты.
Обсудить в сообществе
Делитесь опытом и мыслями с ИИ-разработчиками
Связанные материалы экосистемы
Практические гайды, терминология и агентские скиллы
Claude Code Projects: как один ИИ координирует команду автономных агентов
Глубокий разбор Claude Code Projects: архитектура Coordinator и Threads, параллельные ветки, общая память MEMORY.md и управление облачными агентами.
Часть I. Архитектура ИИ-агентов: фундаментальные блоки
Одиннадцать фундаментальных строительных блоков современного ИИ-агента: таксономия моделей, агентный рантайм, техники промптинга, дистилляция, архитектура навыков (skills), память, function calling и FinOps.
Бенчмарки для агентов: GAIA и SWE-bench
Новое поколение строгих практических бенчмарков для оценки автономности искусственного интеллекта. GAIA тестирует мультимодальные задачи в открытом вебе с файлами и браузером, а SWE-bench проверяет способность агентов находить и исправлять настоящие баги в больших репозиториях GitHub.
Оценка Агентов и Бенчмаркинг SWE-bench
Методология и инфраструктура систематического измерения надежности, точности и безопасности ИИ-агентов с помощью синтетических тестов, SWE-bench и headless репозиторных симуляций.