Software & Systems

Задача поиска кратчайшего пути в графе (Shortest-Paths, SP) – хорошо известная задача теории графов, имеющая многие реальные приложения, такие как планирование маршрута в веб-структурах, навигационные системы, моделирование трафика, логистическая оптимизация. Задача SP состоит в поиске кратчайшего пути в заданном графе между двумя его вершинами s и t (стартовой и целевой соответственно), в котором минимизируется сумма длин ребер, составляющих (s, t)-путь [1, 2]. Существует много классических алгоритмов решения задачи SP. Самый известный из них – алгоритм Дейкстры, который равномерно расширяет пространство поиска решения, начиная от стартовой вершины s и далее последовательно до целевой вершины t, присваивает каждой пройденной вершине v временную метку – верхнюю оценку кратчайшего (s, v)-пути, и превращает временную метку в постоянную, когда ее значение совпадает с кратчайшим (s, v)-путем. Алгоритм A* добавляет в алгоритм Дейкстры потенциальную функцию, которая оценивает снизу кратчайший (v, t)-путь. Данные алгоритмы находят точное решение задачи SP за полиномиальное время [3].

Во многих случаях требуется вычислить за несколько секунд кратчайший (s, t)-путь в графе большой размерности. Типичным примером является поиск кратчайшего маршрута в дорожной сети, насчитывающей несколько десятков или сотен тысяч узлов. В этих условиях классические алгоритмы начинают работать неприемлемо долго. Чтобы справиться с этой проблемой, используют различные приемы ускорения [4-12]. Большинство этих приемов основаны на двухфазном подходе решения задачи SP, который содержит фазу предобработки и фазу выполнения (s, t)-запроса – запроса на вычисление (s, t)-пути в исходном графе. На фазе предобработки выполняется просмотр графа с целью извлечения информации, позволяющий ускорить классические алгоритмы точного решения задачи SP. На второй фазе выполняется (s, t)-запрос с применением извлеченной на первой фазе информации. Известно много различных реализаций двухфазного подхода на основе алгоритма Дейкстры: ALT, Arc-Flags, SHARC и другие. Так, алгоритм ALT (A* with Landmarks & Triangle) устанавливает определенным образом ориентиры (подмножество множества вершин графа) и вычисляет на их основе потенциальную функцию [4]. Алгоритм Arc-Flags разбивает исходный граф по некоторому правилу на несколько подграфов и задает для ребер графа набор меток - «флагов». Алгоритм SHARC основывается на алгоритме Arc-Flags, но дополнительно использует технику сжатия графа [5, 7]. Во всех этих алгоритмах, кроме алгоритма ALT, ускорение достигается за счет максимального использования особенностей структуры входного графа.

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

Формулировка задачи о кратчайшем пути и обоснование алгоритма ALT

Введем необходимые определения и обозначения из теории графов [1, 2]. Ориентированный граф определяется как пара G = (V, E), где V – конечное множество вершин, а E Í V ´ V – множество ориентированных ребер, называемых также дугами. Всякая дуга (u, v) Î E представляет собой упорядоченную пару вершин u, v Î V, причем u ¹ v. Ориентированный граф взвешенный, если на множестве его дуг задана вещественная функция весов w: E→R+, ставящая в соответствие каждой дуге (u, v) Î E ее вес w(u, v) ³ 0. Путь из вершины u в вершину v, или (u, v)-путь, определяется как последовательность вершин P = {v0, v1, v2, …, vk}, в которой u = v0, v = vk, (vi - 1, vi) Î E для i = 1, 2, …, k. Данный путь содержит вершины v0, v1, …, vk и дуги (v0, v1), (v1, v2), …, (vk - 1, vk). Вершину u называют началом (u, v)-пути, а вершину v – его концом. Если в G существует (u, v)-путь P, то говорят, что вершина v достижима из вершины u по пути P, и пишут u ~~ñP v. Весом пути P называется сумма весов всех дуг, входящих в этот путь, и обозначается через w(P). Вес кратчайшего (u, v)-пути равен, по определению, d(u, v) = min P{w(P): u ~~ñP v}, если в G существует хотя бы один (u, v)-путь P. Величину d(u, v) называют часто расстоянием между вершинами u и v. Очевидно, что d(u, u) = 0. Если G = (V, E) - неориентированный граф, то E – множество неупорядоченных пар вершин u, v Î V и u ¹ v. Всегда возможен переход от неориентированного к ориентированному графу путем замены всякого ребра {u, v} двумя дугами противоположной направленности (u, v) и (v, u) с весом исходного ребра. В этом случае d(u, v) = d(v, u). Далее везде полагаем, что исходный граф ориентированный.

Теперь сформулируем задачу SP в приведенных терминах. Задан граф G = (V, E) с неотрицательной вещественной функцией весов w: E → R+. Требуется найти путь наименьшего веса (кратчайший путь) от заданной стартовой вершины s Î V до целевой вершины t Î V. Решение данной задачи всегда существует, если вершина t достижима из вершины s в графе G.

Задачу SP рассматриваем при следующих условиях. Исходный граф G = (V, E) имеет большие размеры (большое число вершин) и хранится в виде БД. К этой БД последовательно поступают (s, t)-запросы в виде пары вершин s и t, которые играют роль стартовой и целевой вершин соответственно. Алгоритм решения задачи SP должен выдавать кратчайший (s, t)-путь для каждого отдельного запроса. Эффективность алгоритма оценивается по времени обработки возможной последовательности запросов. Эта последовательность запросов целиком заранее не известна: обрабатывая поступивший запрос, мы не знаем, какой запрос будет следующим. Кроме того, считаем, что заданная функция весов w такова, что при любых u, v, k Î V всегда выполнимо неравенство треугольника: d(u, v) + d(v, k) ³ d(u, k).

Алгоритм ALT находит точное решение задачи SP при всех вышеперечисленных условиях. Он представляет собой версию алгоритма A*, главная идея которого заключается в применении ориентиров и неравенства треугольника для определения допустимой и преемственной потенциальной функции [3, 4]. Согласно ALT, вначале выбирается множество L Í V вершин графа, в которых будут установлены ориентиры. Затем для каждой вершины v Î V и всякого ориентира l Î L значение потенциальной функции pL(v) вычисляется по формулам:

pl- (v) = | d(l, t) – d(l, v) |,                                 (1)

pl+ (v) = | d(v, l) – d(t, l) |,                                 (2)

pl (v) = max {pl+ (v), pl- (v)},                           (3)

pL (v) = max {pl (v): l Î L}.                                   (4)

Согласно формулам (1), (2) и неравенству треугольника, справедливы оценки: d(v, t) ≥ pl- (v), d(v, t) ≥ pl+ (v).

Действительно, для первой оценки имеем: d(v, t) + d(l, v) ³ d(l, t), d(v, t) ³ d(l, t) -– d(l, v), d(v, t) ³ d(l, t) - d(l, v) = pl- (v) (рис. 1а).

Аналогично получается вторая оценка: d(v, t) + +d(t, l) ³ d(v, l), d(v, t) ³ d(v, l) - d(t, l), d(v, t) ³ ³ d(v, l) - d(t, l) = pl+ (v) (рис. 1b).

Формула (3) учитывает тот факт, что при различной ориентации дуг графа возможна ситуация, когда d(v, l) ¹ d(l, v). В формуле (4) максимум берется по всем l Î L. Таким образом, вычисленное по формулам (1)-(4) значение pL (v) определяет потенциал текущей вершины v как наибольшую нижнюю оценку кратчайшего пути от этой вершины до целевой вершины t:

d(v, t) ≥ pL (v) ³ 0.                                                   (5)

Потенциальная функция, удовлетворяющая (5), называется допустимой [3]. Такая потенциальная функция не переоценивает значение кратчайшего (v, t)-пути. Из приведенных выше рассуждений следует, что неравенство треугольника и формулы (1)-(4) гарантируют допустимость потенциальной функции.

Неравенство треугольника и формулы (1)-(4) также гарантируют выполнимость другого важного свойства потенциальной функции – свойства преемственности (или монотонности). Потенциальная функция называется преемственной, если для любых вершин s, v, t Î V справедливо условие

d(s, v) + pL (v) ≥ pL (s).                                            (6)

Условие (6) - своеобразная форма записи неравенства треугольника для стартовой вершины s, текущей вершины v и целевой вершины t через потенциальные функции. Справедливость условия (6) для неориентированного графа, то есть при d(u, v)=d(v, u) для любых u, v Î V, вытекает из цепочки неравенств: d(s, v) + pL (v) ≥ pL (s), d(s, v) + [d(l, t) – d(l, v)] ³ [d(l, t) - d(l, s)], d(s, v) + d(l, t) - d(l, t) + d(l, s) ³ d(l, v), d(s, v) + d(l, s) ³ d(l, v).

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

Известно, что алгоритм A* находит точное решение задачи SP для графа G = (V, E), если потенциальная функция удовлетворяет условиям (5) и (6), то есть является допустимой и преемственной [3]. При |V| = n время работы алгоритма A* составляет O(n2). Однако на практике за счет использования нижних оценок (5) алгоритм A* способен значительно уменьшить время нахождения кратчайшего (s, t)-пути по сравнению с алгоритмом Дейкстры. Чем лучше (больше по значению) нижние оценки, тем быстрее работает алгоритм A*.

Задача оптимального выбора ориентиров в графе и подходы к ее решению

Очевидно, что различное расположение ориентиров порождает различные потенциальные функции и соответствующие им оценки (5). Из неравенства треугольника следует, что ориентир дает лучшую оценку (5) для текущей вершины v, если его расположение отвечает правилу «тупого угла»: ориентир должен находиться как можно ближе к вершине v и как можно дальше от целевой вершины t или наоборот, ближе всего к t и как можно дальше от v (рис. 3).

Таким образом, расстановка ориентиров в вершинах графа на фазе предобработки – фактор, существенно влияющий на быстродействие алгоритма ALT [4, 9]. Естественны следующие требования к множеству ориентиров L:

-      в качестве множества L может выступать любое подмножество множества V, включая крайние случаи L = Æ и L = V, хотя при L = Æ алгоритм ALT вырождается в алгоритм Дейкстры;

-      любая вершина, в которой установлен ориентир, может выступать в роли стартовой и целевой вершины;

-      ориентиров должно быть разумное число; чем больше мощность L, тем больше времени требуется для вычисления значения потенциальной функции.

Задача оптимального выбора ориентиров в графе заключается в определении числа ориенти- ров и мест их расстановки. Данная задача носит комбинаторный характер и является труднорешаемой. Доказано, что в частном случае, когда число ориентиров фиксированное, данная задача является NP-трудной [4]. Поэтому для ее решения обычно прибегают к эвристическим алгоритмам. С помощью эвристик определяются число ориентиров и места из расстановки. В настоящее время уже экспериментально установлено разумное число ориентиров, одинаково эффективное как на малых, так и на больших графах [4]. Таким образом, задача выбора ориентиров сведена к задаче расстановки заданного числа K = |L| ориентиров в исходном графе. Чаще всего эта задача решается именно в такой постановке и применительно к взвешенным графам, заданным координатами вершин и весами ребер со свойствами евклидовой метрики [4, 9].

Для решения задачи расстановки заданного числа ориентиров в графе на сегодняшний день используются следующие эвристики [6, 9]:

-      H1 - случайная расстановка ориентиров в вершинах графа перед выполнением первого (s, t)-запроса; найденный вариант размещения ориентиров остается неизменным для всех последующих запросов;

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

-      H3 - случайная расстановка ориентиров на границе графа перед выполнением первого (s, t)-запроса (под границей графа здесь понимается выпуклая оболочка этого графа [2]); найденный вариант размещения ориентиров остается неизменным для всех последующих запросов.

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

Адаптивная эвристика расстановки ориентиров и модифицированный алгоритм ALT

Суть предлагаемой адаптивной эвристики состоит в следующем. Перед выполнением первого (s, t)-запроса выполняется случайная расстановка заданного числа K = |L| ориентиров в вершинах графа. Далее выбранное множество ориентиров периодически обновляется через каждые D запросов. При выполнении запросов накапливается статистика об эффективности текущих ориентиров, которая далее используется для перемещения неэффективных ориентиров в новые места их установки. Для определения новых мест применяется стратегия, схожая со стратегиями эвристик H2 и H3.

Потенциальная функция определяется так: для всякого ориентира l Î L и для каждой вершины v Î V вычисляется информация обо всех кратчайших (l, v)-путях и (v, l)-путях; с помощью вычисленной информации значения потенциальной функции находятся по формулам (1)-(4). Заметим, что в случае задания графа координатами вершин и использования евклидовой метрики кратчайшие (l, v)-пути находятся непосредственно без привлечения процедур нахождения кратчайших путей.

Перед первым (s, t)-запросом K=½L½ ориентиров случайным образом размещаются на V. После выполнения каждого (s, t)-запроса выполняется обновление истории процесса обработки запросов: добавление вершин, получивших временные мет­ки, если эти вершины еще не были просмотрены предыдущими (s, t)-запросами; удаление вершин, сменивших временные метки на постоянные.

При выполнении (s, t)-запроса собирается статистика об эффективности ориентиров: всякий раз, когда ориентир предлагает наилучшую оценку пути среди всего набора ориентиров, он получает очко. Как только выполнится (D-1)-й запрос, начинается процедура обновления ориентиров. Ориентир с наименьшим количеством очков подлежит замене на вершину, удовлетворяющую одновременно двум условиям: наибольшая удаленность от текущего набора ориентиров, за исключением заменяемого ориентира (требование правила «тупого угла»); наличие временной метки. После обновления множества L статистика об эффективности ориентиров начинает формироваться заново.

Модифицированный алгоритм ALT, названный ALT_Adapt, реализует классический алгоритм ALT и описанную эвристику. Схема работы алгоритма ALT_Adapt приведена на рисунке 4.

Время работы и объем требуемой памяти для алгоритма ALT_Adapt составляют O(n2), n= |V|. В описании ALT_Adapt, приведенном на рисунке 4, величина dmark (v) = Sl Î L d(l, v) / (K - 1) определяет среднее расстояние от текущего набора ориентиров L до вершины v и характеризует удаленность этой вершины от L. Массив Landmark служит для хранения и формирования набора ориентиров L, при этом i-й элемент массива содержит номер вершины, где установлен этот ориентир. Массив Passed предназначен для хранения номеров вершин, получивших постоянные метки при выполнении предшествующих (s, t)-запросов. Массив Space содержит все вершины, сохранившие временную метку на протяжении всех ранее выполненных (s, t)-запросов. Элементы данного массива являются кандидатами на установку в них нового ориентира. Объединение массивов Passed, Space определяет пространство поиска решения, а мощность этого пространства – один из факторов эффективности алгоритма ALT_Adapt. В массив Stat записываются очки для каждого i-го ориентира, i = 1, …, K. Массивы Passed, Space, Stat характеризуют в целом историю процесса обработки запросов.

Результаты вычислительных экспериментов

Алгоритм ALT_Adapt реализован в виде комплекса программ на языке программирования С++ в среде разработки Code::Blocks. С помощью данного комплекса программ были выполнены вычислительные эксперименты. Эксперименты осуществлялись на компьютере с процессором Intel® Core™ i3 CPU & 2.40 GHz и ОЗУ размером 3 Гб.

Традиционно эффективность различных приемов ускорения алгоритма Дейкстры оценивается по отношению к оригиналу, то есть классической его реализации [4-12]. В данной работе, следуя этой традиции, алгоритм ALT_Adapt сравнивался с классическим алгоритмом Дейкстры по ряду показателей на различных случайных последовательностях запросов. В процессе выполнения вычислительных экспериментов было установлено, что наборы вершин, получивших временные метки для различных запросов к одному и тому же графу, имеют схожую мощность. Поэтому сопоставление алгоритмов осуществлялось лишь по двум показателям: P - среднее число вершин, получивших постоянные метки при выполнении одного (s, t)-запроса; T - среднее время выполнения одного запроса в секундах. Были проведены две серии экспериментов.

Целью первой серии экспериментов являлось установление рациональных значений числа ориентиров K = |L| и частоты D их обновления. Данная серия экспериментов проводилась на связных графах с n = 10 000 вершин и на последовательностях запросов длиной 1 000. Исходный граф и последовательность запросов были заранее сгенерированы случайным образом и оставались неизменными в процессе проведения экспериментов. Изменению подвергались только K и D. Результаты первой серии экспериментов приведены в таблицах 1 и 2.

Как видно из таблицы 1, на практике число ори- ентиров K целесообразно брать в диапазоне 9≤K≤16. Превышение верхней границы этого диа- пазона, то есть числа 16, резко увеличивает время предобработки и не изменяет должным образом значения показателей P и T. Примечательно, что подобный факт отмечен для приемов ускорения алгоритма Дейкстры, описанных в работах [6, 9]. Из таблицы 2 и рисунка 5 следует, что частоту обновления для больших графов на практике разумно полагать D » 20.

Цель второй серии экспериментов – непосредственное сопоставление алгоритма ALT_Adapt с классическим алгоритмом Дейкстры по времени работы при фиксированных значениях K = 13 и D = 20 на случайных связных n-вершинных графах. Результаты этих экспериментов при различных значениях n приведены в таблице 3 и на рисунке 6.

Таблица 1

Результаты экспериментов для различных значений K

Table 1

The results of the experiments for different values of K

Таблица 2

Результаты экспериментов для различных значений D

Table 2

The results of the experiments for different values of D

Таблица 3

Сравнение алгоритмов по среднему времени выполнения одного запроса

Table 3

Comparison of algorithms according to an average query execution time

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

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

Литература

1.     Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Либроком, 2012. 392 с.

2.     Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы. Построение и анализ. М.: Вильямс, 2013. 1328 с.

3.     Рассел С., Норвинг П. Искусственный интеллект: современный подход. М.: Вильямс, 2006. 1408 с.

4.     Goldberg A., Kaplan H. & Werneck R. Reach for A*: Efficient point-to-point shortest path algorithms. Technical Report MSR-TR-2005-132, Microsoft Research, Microsoft Corporation, 2005, 41 p.

5.     Bauer R. & Delling D. SHARC: Fast and robust unidirectional routing. Journ. of Experimental Algorithmics, 2009, vol. 14, no. 4, pp. 1–29.

6.     Goldberg A. & Harrelson C. Computing the shortest path: A* search meets graph theory. Proc. SIAM Symposium on Discrete Algorithms, 2005, pp. 156–165.

7.     Brunel E., Delling D., Gemsa A. & Wagner D. Space-efficient SHARC-routing, 9th Int. Sympos. on Experimental Algorithms (SEA), 2012, pp. 47-58.

8.     Geisberger R., Sanders P., Schultes D. & Delling D. Contraction hierarchies: faster and simpler hierarchical routing in road networks. Proc. Intern. Workshop on Experimental Algorithms (WEA). Springer, 2008, pp. 319–333.

9.     Goldberg A., Kaplan H. & Werneck R. Better landmarks within reach. Proc. Intern. Workshop on Experimental Algorithms (WEA). Lecture Notes in Comp. Sci. Springer, 2007, vol. 4525, pp. 38–51.

10.  Wagner D. & Willhalm T. Speed-up techniques for shortest-path computations. Proc. STACS, 2007, pp. 23-36.

11.  Subashini R. & Christy A. Jeya. Online Shortest Path based on Live Traffic Circumstances. Int. Journ. of Comp. Sc. and Mobile Computing, 2014, vol. 3, iss. 11, pp. 331–337.

12.  Sivakumar S. & Chandrasekar C. Modified Dijkstra’s Shor­test Path Algorithm. Int. J. of Innovative Research in Computer and Communication Engineering, 2014, vol. 2, iss. 2, pp. 6450–6456.