Перевод названия: Adaptive landmark selection in shortest-paths problem for a big graph
Тип публикации: статья из журнала
Год издания: 2016
Ключевые слова: кратчайший путь, техника ускорения, алгоритм Дейкстры, алгоритм alt, ориентиры, эвристика, граф большой размерности
Аннотация: Задача о кратчайшем пути (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 на графах большой размерности работает значительно быстрее алгоритма Дейкстры, что подтверждают результаты вычислительных экспериментов. 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.
Журнал: Программные продукты и системы
Выпуск журнала: № 1
Номера страниц: 60-67
ISSN журнала: 0236235X
Место издания: Тверь
Издатель: Закрытое акционерное общество Научно-исследовательский институт Центрпрограммсистем