Пост канала
- фото
ИИ за 15 часов обошёл алгоритм Дейкстры Десять агентов Claude Opus 5.5 придумали и формально доказали новый способ искать кратчайшие пути в графе. Что у них вышло — разбираем ниже. ▬▬▬▬▬▬▬▬▬▬ Исследователи из Vals AI поставили десяти агентам Claude Opus 5.5 одну задачу: придумать более быстрый алгоритм поиска кратчайших путей и доказать его свойства в системе формальной верификации Lean. Через 15 часов у них был готов алгоритм C-HD — он находит точные расстояния от одной вершины до всех остальных в ориентированном графе с неотрицательными весами. Классический алгоритм Дейкстры работает за O(m + n·log n), а C-HD при m ≈ n·log^(3/4) n укладывается в O(n·log^(11/12) n). По оценке авторов, «при n = 2^1000 выигрыш составляет ~1,78х и растет с размером графа». Без оговорок, впрочем, не обошлось: практическое ускорение пока не показано. Корректность проверяли лишь на небольших примерах, скорость на больших графах не замеряли, а в формальной конструкции остаются «огромные константы». Независимого рецензирования результата тоже пока нет.
Открыть в MAX- Просмотры
- 30
- ER
- —
- Реакции
- —