Vals AI и Claude Opus 5.5 разработали алгоритм C‑HD, ускоряющий поиск кратчайших путей

Исследовательская группа Vals AI поставила перед десятью агентами Claude Opus 5.5 задачу, которой традиционно занимаются ученые‑алгоритмисты: придумать более быстрый способ вычисления кратчайших путей в ориентированном графе с неотрицательными весами и оформить доказательство в системе Lean. За пятнадцать часов работы агенты представили новый метод, получивший название C‑HD. Работа проводилась полностью автоматически: агенты генерировали идеи, проверяли их корректность и формулировали формальные доказательства, которые затем были объединены в единую теорему. Результат – полностью доказанный алгоритм, готовый к публикации в академической среде.

C‑HD вычисляет точные расстояния от выбранной вершины до всех остальных, используя структуру, напоминающую комбинацию сжатия графа и многопоточного обхода. Для плотности ребер, приближенной к m ≈ n·log^{3/4} n, его асимптотическая оценка составляет O(n·log^{11/12} n). По сравнению с классическим Дейкстрой, чей верхний предел O(m + n·log n), в указанном диапазоне C‑HD теоретически выигрывает, сокращая главный логарифмический множитель.

Задача поиска кратчайшего пути является одной из краеугольных в теории графов, а алгоритм Дейкстры более пол века считается оптимальным для большинства практических сценариев. Однако в редкой «разреженной» зоне, где количество ребер растет медленнее, чем n·log n, улучшения оставались лишь гипотетическими. C‑HD стал первым формально доказанным решением, которое в этой области опережает Дейкстру, хотя прирост в реальном времени пока измеряется лишь на примере n = 2^{1000}, где ускорение составляет около 1,78× и растет с ростом n.

Авторы отмечают, что пока не проведено масштабных экспериментов на больших графах: проверка корректности ограничивалась небольшими тестами, а константы, появляющиеся в формальном доказательстве, оказались весьма большими, что может нивелировать теоретический выигрыш. Кроме того, независимая экспертиза результата еще не выполнена, поэтому сообществу придется самостоятельно подтвердить заявленные свойства алгоритма.

Тем не менее публикация C‑HD демонстрирует потенциал современных языковых моделей в генерации оригинальных алгоритмических идей и их формальной верификации. Если последующие исследования смогут уменьшить константы и подтвердить эффективность на реальных данных, такой подход может открыть новый путь к автоматическому созданию конкурентоспособных решений в области теории алгоритмов.