ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Journal influence

Higher Attestation Commission (VAK) - К1 quartile
Russian Science Citation Index (RSCI)

Bookmark

Next issue

2
Publication date:
16 June 2024

Adaptive landmark selection in shortest-paths problem for a big graph

Date of submission article: 15.12.2015
UDC: 519.179
The article was published in issue no. № 1, 2016 [ pp. 60-67 ]
Abstract:The shortest path (SP) problem is one of the main problems in routing in the theory of graphs. This problem arises in a web-structure analysis when creating navigation systems, traffic modeling and logistics optimization. The problem requires a search of the shortest path between two given vertices of the initial directed graph G and minimization of the sum of edges weight forming this way. Traditionally the SP problem is solved using Dijkstra's algorithm. The algorithm works assigning marks to vertices of graph G and uniformly expands the search space of solutions, starting from the start vertex s to the target vertex t of the graph. There are a lot of modifications of Dijkstra’s algorithm aimed to reduce working time. A* (A star) algorithm is one of these modifications, in which acceleration is achieved using a potential function defined on the set of G graph vertices. The ALT (A* with Landmark & Triangle) algorithm is based on A* algorithm. Here a potential function is defined by a set of landmarks (a certain subset of G graph vertices). Different landmark selections in G correspond to different potential functions. Selection of the optimal set of landmarks is carried in a finite set of variants and is a NP-hard problem. The ALT algorithm is represented in the form of two phases: the first phase contains execution of preliminary graph processing to select landmarks and calculate a potential function; the second phase computes the shortest (s, t)-path using a potential function. The paper suggests an adaptive heuristic for landmark selection. This heuristic uses exexecution history of last queries to search the shortest paths in G graph and corrects the current set of landmarks for effective execution of a newly received query to search the shortest (s, t)-path in a current graph. In the proposed modification the ALT algorithm and Dijkstra’s algorithm are equivalent in terms of asymptotic estimate of their performance. However, in real life the modified ALT algorithm applied to a big graph is much faster than Dijkstra’s algorithm. This is confirmed by presented in this work computation results.
Аннотация:Задача о кратчайшем пути (Shortest-Paths, SP) является одной из основных задач маршрутизации, решаемых в теории графов. Данная задача возникает в анализе веб-структур, при создании систем навигации, моделировании трафика и логистической оптимизации. В задаче осуществляется поиск кратчайшего пути между двумя заданными вершинами исходного ориентированного графа G и минимизируется сумма весов дуг, составляющих этот путь. Традиционно задача SP решается с помощью алгоритма Дейкстры, который работает посредством приписывания меток вершинам графа G и равномерного расширения пространства поиска решения, начиная от стартовой вершины s и до целевой вершины t этого графа. Существуют различные модификации алгоритма Дейкстры, направленные на сокращение времени его работы. Алгоритм A* (A star) - одна из таких модификаций, в которой ускорение достигается за счет применения потенциальной функции, определяемой на множестве вершин графа G. В алгоритме ALT (A* with Landmark & Triangle), основу которого составляет алгоритм A*, потенциальная функция задается набором ориентиров - некоторым подмножеством множества вершин графа G. Различным размещениям ориентиров отвечают различные потенциальные функции. Выбор оптимального набора ориентиров осуществляется в конечном множестве вариантов и является NP-трудной задачей. Алгоритм ALT реализуется в виде двух фаз: на первой фазе выполняется предварительная обработка графа с целью расстановки ориентиров и определения потенциальной функции; на второй фазе находится точное значение кратчайшего (s, t)-пути с применением вычисленной потенциальной функции. В работе предложена адаптивная эвристика для первой фазы алгоритма ALT. Данная эвристика использует историю обработки предыдущих запросов по поиску кратчайших путей в графе G и корректирует текущий набор ориентиров для эффективного исполнения поступившего запроса по нахождению кратчайшего (s, t)-пути в этом графе. В предложенной модификации алгоритм ALT и алгоритм Дейкстры сопоставимы с точки зрения асимптотической оценки времени их работы. Однако в реальной действительности модифицированный алгоритм ALT на графах большой размерности работает значительно быстрее алгоритма Дейкстры, что подтверждают результаты вычислительных экспериментов.
Authors: Bykova V.V. (bykvalen@mail.ru) - Siberian Federal University (Professor), Krasnoyarsk, Russia, Ph.D, Soldatenko A.A. (glinckon@gmail.com) - Siberian Federal University, Krasnoyarsk, Russia
Keywords: big graph, heuristics, landmarks, alt algorithm, dijkstra's algorithm, accelerate method, shortest path problem
Page views: 8564
Print version
Full issue in PDF (8.31Mb)
Download the cover in PDF (1.24Мб)

Font size:       Font:

Задача поиска кратчайшего пути в графе (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

Число ориентиров (K)

Число вершин с постоянными метками (P)

Время выполнения (s, t)-запроса (T, сек.)

7

779

0,0969

8

768

0,0932

9

662

0,0819

10

656

0,0789

11

645

0,0781

12

613

0,0729

13

551

0,0782

14

632

0,0778

15

658

0,0845

16

700

0,1031

17

614

0,0841

18

647

0,0929

 

Таблица 2

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

Table 2

The results of the experiments for different values of D

Частота обновления ориентиров (D)

Число вершин с постоянными метками (P)

Время выполнения (s, t)-запроса (T, сек.)

5

589

0,0715

10

582

0,0697

15

556

0,0684

20

515

0,0626

25

553

0,0639

30

594

0,0763

35

671

0,0894

40

541

0,0678

45

582

0,0739

50

635

0,0824

Таблица 3

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

Table 3

Comparison of algorithms according to an average query execution time

Число вершин графа

Алгоритм Дейкстры

Алгоритм ALT_Adapt

n

P

T, сек.

P

T, сек.

1000

486

00,0083

42

00,0009

10000

4846

00,7455

579

00,1213

25000

12568

07,0800

1689

00,9112

50000

27021

32,2372

4754

07,2919

70000

35288

65,3484

5020

09,4202

75000

38610

61,2791

5842

18,8327

80000

38474

61,6918

6248

18,0949

Из результатов вычислительных экспериментов можно сделать вывод, что алгоритм 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.


Permanent link:
http://swsys.ru/index.php?page=article&id=4111&lang=&lang=&like=1&lang=en
Print version
Full issue in PDF (8.31Mb)
Download the cover in PDF (1.24Мб)
The article was published in issue no. № 1, 2016 [ pp. 60-67 ]

Perhaps, you might be interested in the following articles of similar topics: