На шаг ближе к идеальному маршруту: новый прорыв в компьютерных науках

Поиск кратчайшего маршрута между двумя точками — обычная задача для навигационных приложений, таких как Google Maps или Яндекс Карты. Гораздо сложнее вычислять кратчайшее расстояние между каждой возможной парой точек в огромной сети. Подобные вычисления очень важны для транспортных систем, сетей связи и даже биологических структур, состоящих из взаимосвязанных элементов. По мере роста таких сетей определение кратчайших маршрутов между всеми их точками становится всё сложнее.

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

Почему так сложно вычислять кратчайшие пути

Точный расчёт расстояний в огромной сети требует огромных вычислительных ресурсов и памяти. Причём некоторые традиционные алгоритмы требуют так называемого кубического времени. Это означает, что при удвоении числа вершин объём вычислений может увеличиться примерно в восемь раз. Поэтому учёные десятилетиями искали способы получать достаточно точные оценки с меньшими затратами. Одно из перспективных решений — алгоритмы приближённых вычислений. Вместо точного ответа они выдают оценку, стремясь обеспечить приемлемую точность при существенном сокращении необходимых вычислительных ресурсов.

В 1996 году исследователи Дор, Гальперин и Цвик ((Dor, Halperin и Zwick — DHZ) разработали метод, который позволяет получать оценки расстояний не более чем вдвое превышающие фактическое кратчайшее расстояние для достаточно удалённых друг от друга вершин. При этом алгоритм работает за время, близкое к теоретически оптимальному.

Такую точность называют 2-приближением (2-approximation). Например, если кратчайший маршрут между двумя точками составляет 10 километров, оценка, удовлетворяющая этой гарантии, должна находиться в диапазоне от 10 до 20 километров.

Вместо анализа всех маршрутов алгоритм DHZ использует относительно небольшую выборку точек сети. Так называемые выборочные вершины (sampled vertices) служат своего рода промежуточными ориентирами, позволяющими алгоритму эффективнее оценивать расстояния.

Удобный способ со скрытым недостатком

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

Однако, для близко расположенных точек такая стратегия менее надёжна. Допустим, кратчайший путь между двумя пригородными районами, то есть двумя вершинами, может состоять всего из двух рёбер, тогда как маршрут, построенный с использованием выборочных вершин, будет содержать пять рёбер. Поскольку пять больше удвоенного истинного расстояния, равного двум, результат уже не удовлетворяет гарантии точности «не более чем в два раза». Таким образом, гарантия точности исходного алгоритма действует только для достаточно удалённых точек. Для коротких расстояний тот же уровень надёжности обеспечить не удастся.

Именно это ограничение оставалось нерешённой проблемой почти три десятилетия.

Новый алгоритм преодолевает существовавшие ограничения

Усовершенствование прежнего подхода предложил доктор Манодж Гупта из Индийского технологического института в Гандинагаре. Своё исследование он назвал «Улучшенные приближённые алгоритмы с коэффициентом 2 для кратчайших путей между близкими парами вершин» (Improved 2-Approximate Shortest Paths for Close Vertex Pairs).

Новый алгоритм сохраняет общую временную сложность прежнего подхода, одновременно расширяя диапазон расстояний, для которых можно гарантировать надёжность оценок. Прорыв стал возможен благодаря новому подходу к выборке вершин сети.

Гупта предложил стратегию многоуровневой выборки (multi-scale sampling), при которой информация о сети организуется и анализируется сразу на нескольких масштабных уровнях. Благодаря этому алгоритм способен учитывать короткие маршруты, которые прежние методы могли упускать из виду.

В результате сокращается минимальное расстояние, начиная с которого действует гарантия 2-приближения, практически без роста общей вычислительной сложности.

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

Почему этот прорыв в области компьютерных наук так важен?

Огромные разветвлённые сети являются основой современных технологий. Интернет-инфраструктура, транспортные системы, платформы социальных сетей и приложения искусственного интеллекта — все они зависят от анализа сложных структур, состоящих из множества взаимосвязанных элементов.

Во многих случаях вычислить абсолютно точное расстояния менее важно, чем быстро получить достаточно надежную оценку. Когда сети содержат огромное количество связей, способность сбалансировать точность и скорость становится особенно ценной.

Исследования Гупты укрепляют математические основы алгоритмов, разработанных для решения этих задач. Хотя его результаты носят теоретический характер и не предполагают немедленного улучшения конкретных коммерческих систем, они предлагают более эффективный подход к расчету расстояний в крупных сетях.

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

Прогресс в теоретической информатике нередко достигается за счет постепенных усовершенствований известных решений, а не кардинальных изменений в подходах. Поэтому, улучшение метода, разработанного в 1996 году, несомненно представляет собой существенный шаг вперёд.

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

Источник: ScienceDaily

Изображение для иллюстрации. Источник: Magnific.com.