Манодж Гупта преодолел барьер 1996 года в алгоритмах кратчайших путей

Манодж Гупта из Индийского технологического института в Гандинагаре (IIT Gandhinagar) разработал алгоритм, который точнее оценивает расстояния в огромных сетях и при этом не замедляет вычисления. Работа снимает ограничение, с 1996 года сдерживавшее прогресс в этой области информатики.

Задача APSP и старый барьер

Ключом стал метод, дающий более точные приближения кратчайших путей между близко расположенными точками. С такой задачей компьютеры сталкиваются ежедневно: на ней основаны навигационные приложения, транспортные системы и интернет-инфраструктура. Всё усложняется, когда нужно вычислить расстояния между каждой парой точек в большой сети. В информатике это называется задачей APSP (All-Pairs Shortest Paths). Сетью могут быть города, компьютеры, железнодорожные станции и даже нейроны.

Точный расчёт всех кратчайших маршрутов в плотной сети требует огромных ресурсов, поэтому учёные ищут приближённые методы. В 1996 году Дор, Гальперин и Цвик предложили алгоритм, гарантирующий, что оценка не превысит реальное расстояние более чем вдвое (2-приближение). Однако гарантия работала главным образом для далёких друг от друга точек. На коротких связях ошибки были больше: вместо двух рёбер алгоритм мог выдать пять, выходя за допустимый двукратный предел.

Многомасштабная выборка

Гупта изменил способ выбора точек, по которым оценивается расстояние. Раньше использовали небольшой набор репрезентативных вершин. Новый алгоритм применяет многомасштабную выборку: структура сети анализируется на нескольких уровнях, а не по одному набору точек. Благодаря этому учитываются короткие связи, которые раньше могли быть упущены.

Главное, что рост точности не повышает общую вычислительную сложность алгоритма. Более надёжные результаты достигаются без дополнительных затрат времени.

Достижение может пригодиться везде, где анализируются обширные сети: в телекоммуникациях, на транспорте, в соцсетях и системах искусственного интеллекта. Быстрая и надёжная оценка расстояний помогает изучать связи между элементами и оптимизировать работу целых систем.