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

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

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

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

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

Прямолинейный подход с предварительным вычислением и хранением кратчайших путей между всеми парами вершин позволяет отвечать на запросы о кратчайших путях с оптимальной скоростью, однако он требует квадратичного объема памяти, что для орграфов с числом вершин более [math]\displaystyle{ 10^5 }[/math] делает его крайне непрактичным для использования в больших и очень больших сетях. По этой причине основная цель почти всех известных подходов заключается в максимально возможном сокращении требований к памяти. Это, в свою очередь, подразумевает возможность применения масштабной (по времени) предварительной обработки, не требующей увеличения объема памяти, для ускорения выполнения запросов.

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

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

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

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

Основные результаты применения первого [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]. В этой статье было проведено первое экспериментальное сравнение двух значимых подходов (растянутого по времени и зависящего от времени), а также предложены новые расширения подходов с целью реалистичности моделирования. Кроме того, было предложено несколько новых эвристик для ускорения выполнения запросов.

Применение

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

Открытые вопросы

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

Экспериментальные результаты

Все работы, упомянутые в разделе «Основные результаты», содержат изложение важных экспериментальных исследований рассматриваемых ими техник.

Наборы данных

Наборы данных, использовавшиеся в [6, 11], доступны по адресу http://lso-compendium.cti.gr/ (номера задач 20 и 26, соответственно).

Наборы данных, использовавшиеся в [1, 2], доступны по адресу http://www.dis.uniroma1.it/~challenge9/.

Ссылка на код

Код, используемый в работе [9], доступен на сайте http://doi.acm.org/10.1145/351827.384254.

Код, используемый в [6, 11], доступен по адресу http://lso-compendium.cti.gr/ (номера задач 20 и 26, соответственно).

Код, используемый в [3], доступен на сайте http://www.avglab.com/andrew/soft.html.

См. также

Литература

1. Delling, D., Holzer, M., Miiller, K., Schulz, F., Wagner, D.: High-Performance Multi-Level Graphs. In: 9th DIMACS Challenge on Shortest Paths, Nov 2006. Rutgers University, USA (2006)

2. Delling, D., Sanders, P., Schultes, D., Wagner, D.: Highway Hierarchies Star. In: 9th DIMACS Challenge on Shortest Paths, Nov 2006 Rutgers University, USA (2006)

3. Goldberg, A.V., Harrelson, C.: Computing the Shortest Path: A* Search Meets Graph Theory. In: Proc. 16th ACM-SIAM Symposium on Discrete Algorithms - SODA, pp. 156-165. ACM, New York and SIAM, Philadelphia (2005)

4. Gutman, R.: Reach-based Routing: A New Approach to Shortest Path Algorithms Optimized for Road Networks. In: Algorithm Engineering and Experiments - ALENEX (SIAM, 2004), pp. 100-111. SIAM, Philadelphia (2004)

5. Holzer, M., Schulz, F., Wagner, D.: Engineering Multi-Level Overlay Graphs for Shortest-Path Queries. In: Algorithm Engineering and Experiments - ALENEX (SIAM, 2006), pp. 156-170. SIAM, Philadelphia (2006)

6. Pyrga, E., Schulz, F., Wagner, D., Zaroliagis, C.: Efficient Models for Timetable Information in Public Transportation Systems. ACM J. Exp. Algorithmic 12(2.4), 1-39 (2007)

7. Sanders, P., Schultes, D.: Highway Hierarchies Hasten Exact Shortest Path Queries. In: Algorithms - ESA 2005. Lect. Note Comp. Sci. 3669,568-579 (2005)

8. Sanders, P., Schultes, D.: Engineering Highway Hierarchies. In: Algorithms - ESA 2006. Lect. Note Comp. Sci. 4168, 804-816 (2006)

9. Schulz, F., Wagner, D., Weihe, K.: Dijkstra's Algorithm On-Line: An Empirical Case Study from Public Railroad Transport. ACM J. Exp. Algorithmics 5(12), 1 -23 (2000)

10. Schulz, F., Wagner, D., Zaroliagis, C.: Using Multi-Level Graphs for Timetable Information in Railway Systems. In: Algorithm Engineering and Experiments - ALENEX 2002. Lect. Note Comp. Sci. 2409,43-59 (2002)

11. Wagner, D., Willhalm, T., Zaroliagis, C.: Geometric Containers for Efficient Shortest Path Computation. ACM J. Exp. Algorithmics 10(1.3), 1-30 (2005)