Разработка алгоритмов для применения в больших сетях
Постановка задачи
Для эффективного управления работой приложений в больших сетях обычно требуется решение одной или нескольких базовых алгоритмических задач. Из-за размера сети для достижения требуемой продуктивности алгоритма необходимы значительные усилия.
Одной из основных задач при работе в больших сетях является нахождение ответов на запросы о поиске лучшего маршрута или пути с максимально возможной эффективностью. Нередко серьезную проблему представляет обработка большого числа таких запросов в онлайн-режиме: типичный сценарий, встречающийся в различных системах, работающих в режиме реального времени (таких как системы управления информацией о дорожном движении или системы управления общественным транспортом), подразумевает обработку центральным сервером множества запросов от клиентов в реальном времени, которым необходим лучший путь или оптимальный маршрут. Основной целью при выполнении таких приложений является сокращение среднего времени выполнения запроса.
Поиск наилучшего пути (или оптимального маршрута) подразумевает решение задачи о поиске пути с минимальной стоимостью (или кратчайшего пути) на подходящим образом определенном ориентированном графе с неотрицательными стоимостями ребер. Это, в свою очередь, сводится к базовой алгоритмической задаче, которой в данной ситуации является задача нахождения кратчайших путей с единственным источником и единственной целью.
Прямолинейный подход с предварительным вычислением и хранением кратчайших путей между всеми парами вершин позволяет отвечать на запросы о кратчайших путях с оптимальной скоростью, однако он требует квадратичного объема памяти, что для орграфов с числом вершин более 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*-поиск.
Второй подход (дополнительный граф)
Первая работа в рамках этого подхода [10] представляет новую технику иерархической декомпозиции, получившую название многоуровневого графа. Многоуровневый граф M представляет собой орграф, определяемый последовательностью подмножеств V, множество E которого расширено посредством дополнения несколькими уровнями ребер. Это позволяет в ходе ответа на запрос эффективно строить подграф M, значительно меньшего размера по сравнению с G, в котором расстояние по кратчайшему пути между любыми двумя вершинами равно расстоянию по кратчайшему пути между теми же вершинами в графе G. Дальнейшие улучшения этого подхода были недавно предложены в работе [1]. Дальнейшим развитием первоначальной идеи стало введение многоуровневых графов с наложениями [5]. В таком графе иерархия декомпозиции не определяется информацией, относящейся к конкретной области применения, как это было в случае [9, 10].
Альтернативная техника иерархической декомпозиции под названием иерархии магистралей была предложена в [7]. Этот подход использует свойство изначально присущих системе иерархий, которым обладают дорожные сети материального мира, и вычисляет иерархию более крупноблочных представлений входного графа. Затем алгоритм поиска кратчайших путей рассматривает главным образом именно эти крупноблочные представления, размер которых намного меньше, что способствует значительному сокращению времени выполнения запроса. Пересмотр и улучшение этого метода были произведены в работе [8]. Мощное сочетание иерархии магистралей с идеями из статьи [3] было рассмотрено в [2].
Вопросы моделирования
Моделирование исходной задачи поиска наилучшего пути (или оптимального маршрута) на большой сети при помощи задачи о кратчайшем пути в подходящим образом определенном подграфе с соответствующими стоимостями ребер также играет важную роль в сокращении времени выполнения запросов. Вопросы моделирования были досконально исследованы в работе [6]. В этой статье было проведено первое экспериментальное сравнение двух значимых подходов (растянутого по времени и зависящего от времени), а также предложены новые расширения подходов с целью реалистичности моделирования. Кроме того, было предложено несколько новых эвристик для ускорения выполнения запросов.