Математики научили алгоритмы видеть короткие пути в гигантских графах

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

С 1996 года в дискретной математике действовал стандарт, предложенный исследователями Дором, Хальперином и Цвиком. Их метод обеспечивал так называемую 2-аппроксимацию: оценка длины пути превышала реальную максимум в два раза при околооптимальном времени работы. Суть заключалась в выборке опорных вершин, служащих ориентирами. Однако подход работал лишь на больших дистанциях — например, между удаленными мегаполисами вроде Дели и Ченнаи. На коротких связках, таких как соседние пригородные кварталы, опорные точки оказывались в стороне, и гарантированная точность терялась: вместо пути длиной в 2 ребра алгоритм мог выдать 5, нарушая предельный порог ошибки.

Ограничение, остававшееся незыблемым почти 30 лет, преодолел доцент Индийского института технологий в Гандинагаре Манодж Гупта. Ученый представил многомасштабную схему выборки узлов на 66-м ежегодном симпозиуме по основам компьютерных наук (FOCS 2025). Организация анализа сети на нескольких уровнях детализации позволила алгоритму уверенно учитывать близко расположенные маршруты. Главное математическое достижение заключается в том, что строгая гарантия точности теперь распространяется на пары близких вершин, не требуя дополнительного времени на вычисления.

Телеграм: t.me/ainewsline

Источник: vk.com

Комментарии: