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

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

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

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

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

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

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

Основные результаты

Все обсуждаемые результаты касаются ответов на запросы о нахождении оптимальных (либо точных, либо сохраняющих расстояния) кратчайших путей в упомянутом сценарии с большим числом запросов и основываются на следующем базовом подходе. Выполняется предварительная обработка входной сети G = (V, E), результатом которой становится структура данных размера O(|V| + |E|) (т.е. линейная относительно размера G). Эта структура данных содержит дополнительную информацию по поводу определенных кратчайших путей, которая впоследствии может быть использована в ходе ответов на запросы.

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

Основные результаты применения первого [3, 4, 9, 11] и второго [1, 2, 5, 7, 8, 10] подходов, а также вопросы моделирования будут обсуждены далее.

Первый подход (аннотирование графа)

Первая работа в рамках этого подхода посвящена исследованию крупных железнодорожный сетей [9]. В этой статье были введены две новые эвристики: ограничение угла (эта эвристика стремится сократить пространство поиска, пользуясь информацией о геометрическом расположении вершин) и выбор станций (выбирается подмножество вершин, для которого вычисляются кратчайшие пути между всеми вершинами). Эти две эвристики в сочетании с классическим целеориентированным поиском или A*-поиском оказались очень эффективными. Более того, они стимулировали создание двух важных обобщений [10, 11], позволивших ускорить выполнение запросов о кратчайшем пути.

Полное исследование геометрических эвристик было проведено в работе [11], в которой рассматривались уличная и железнодорожная сети. В этой работе было показано, что пространство поиска у алгоритма Дейкстры можно значительно уменьшить (до 5-10% от исходного размера графа) в результате извлечения геометрической информации из заданного расположения графа и сохранения заранее вычисленной информации о кратчайших путях в геометрических объектах, называемых контейнерами. Исследовался также динамический вариант этой задачи, в котором стоимости ребер могли изменяться, а геометрические контейнеры нужно было обновлять.

Мощная модификация классического алгоритма Дейкстры, получившая название маршрутизации на основе достижимости, была представлена в [4]. Каждой вершине присваивается так называемое значение достижимости, определяющее, следует ли рассматривать конкретную вершину в ходе работы алгоритма Дейкстры. Вершина исключается из рассмотрения, если ее значение достижимости невелико – иначе говоря, если она не входит в какой-либо путь, достаточно длинный, чтобы пригодиться при выполнении текущего запроса.

Важное расширение классического алгоритма A*-поиска, использующее ориентиры (избранные вершины, как в работах [9, 10]) и неравенство треугольника применительно к расстояниям по кратчайшим путям, было предложено в [3]. Ориентиры и неравенство треугольника позволяют улучшить нижние границы и, в силу этого, ускорить A*-поиск.

Второй подход (дополнительный граф)