10 агентов Claude теоретически обошли алгоритм Дейкстры
В Vals AI запустили 10 агентов Claude Opus 5.5, которые за 15 часов и 733 сообщения разработали алгоритм C-HD для поиска кратчайших путей в ориентированных графах.
Для графов с определённой плотностью сложность снизилась с O(n log n) у Дейкстры до O(n log¹¹⁄¹² n). Корректность и оценка времени работы формально подтверждены доказательством в Lean.
Но это пока теоретический результат. Алгоритм не тестировали на крупных реальных графах, константы велики, а улучшение действует только в ограниченном диапазоне входных данных.
Главное здесь другое: группа ИИ-агентов смогла самостоятельно разработать алгоритм и подготовить его формальное доказательство всего за 15 часов.
https://www.vals.ai/blogs/faster-shortest-path-algorithm
В Vals AI запустили 10 агентов Claude Opus 5.5, которые за 15 часов и 733 сообщения разработали алгоритм C-HD для поиска кратчайших путей в ориентированных графах.
Для графов с определённой плотностью сложность снизилась с O(n log n) у Дейкстры до O(n log¹¹⁄¹² n). Корректность и оценка времени работы формально подтверждены доказательством в Lean.
Но это пока теоретический результат. Алгоритм не тестировали на крупных реальных графах, константы велики, а улучшение действует только в ограниченном диапазоне входных данных.
Главное здесь другое: группа ИИ-агентов смогла самостоятельно разработать алгоритм и подготовить его формальное доказательство всего за 15 часов.
https://www.vals.ai/blogs/faster-shortest-path-algorithm