Разработка алгоритмов для применения в больших сетях

Постановка задачи

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

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

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

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

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