1313
правок
Алгоритм поиска кратчайших путей с единственным источником: различия между версиями
Материал из WEGA
Алгоритм поиска кратчайших путей с единственным источником (посмотреть исходный код)
Версия от 04:10, 7 декабря 2024
, 7 декабря 2024→Литература
Irina (обсуждение | вклад) |
KVN (обсуждение | вклад) |
||
| (не показаны 4 промежуточные версии 1 участника) | |||
| Строка 11: | Строка 11: | ||
== Основные результаты == | == Основные результаты == | ||
Главным результатом работы Торупа [ ] стал оптимальный SSSP-алгоритм с линейным временем выполнения для неориентированных графов с целочисленными длинами ребер. Это первый и единственный алгоритм поиска кратчайших путей, не делающий серьезных предположений о классе входного графа. | Главным результатом работы Торупа [17] стал оптимальный SSSP-алгоритм с линейным временем выполнения для неориентированных графов с целочисленными длинами ребер. Это первый и единственный алгоритм поиска кратчайших путей, не делающий серьезных предположений о классе входного графа. | ||
Теорема 1. Существует SSSP-алгоритм для неориентированных графов с целочисленными весами ребер, выполняющийся за время O(m). | '''Теорема 1. Существует SSSP-алгоритм для неориентированных графов с целочисленными весами ребер, выполняющийся за время O(m).''' | ||
Торупу удалось избежать «бутылочного горлышка» сортировки, присущего алгоритму Дейкстры, за счет предварительного вычисления иерархии компонентов за линейное время. Алгоритм из [ ] действует подобно алгоритму Дейкстры [ ], но использует иерархию компонентов для определения групп вершин, которые могут быть посещены в любом порядке. В более поздней работе [ ] Торуп расширил алгоритм таким образом, чтобы он мог работать с длинами ребер, представляющими собой числа с плавающей | Торупу удалось избежать «бутылочного горлышка» сортировки, присущего алгоритму Дейкстры, за счет предварительного вычисления ''иерархии компонентов'' за линейное время. Алгоритм из [17] действует подобно алгоритму Дейкстры [4], но использует иерархию компонентов для определения групп вершин, которые могут быть посещены в любом порядке. В более поздней работе [18] Торуп расширил алгоритм таким образом, чтобы он мог работать с длинами ребер, представляющими собой числа с плавающей запятой. (''Определение кратчайшего пути обладает определенной гибкостью, поскольку сложение с плавающей запятой не является ни коммутативным, ни ассоциативным'')). | ||
Основанный на иерархии подход Торупа был в дальнейшем распространен на ориентированные графы и/или графы с вещественными весами и в таком виде позволил решить задачу ''поиска кратчайших путей между всеми парами'' (all pairs shortest path, APSP) [12, 13, 14]. Обобщения до соответствующих SSSP-задач можно суммировать следующим образом. В работах [12, 13] можно найти более подробное изложение основанных на использовании иерархии APSP-алгоритмов. | |||
'''Теорема 2 (Хагеруп [9], 2000). Иерархия компонентов для ориентированного графа <math>G = (V, E, \ell) \;</math>, где <math>\ell: E \to \{ 0, ..., 2^w - 1 \}</math>, может быть построена за время O(m log w). После этого поиск кратчайших путей из любого единственного источника может быть произведен за время O(m + n log log n).''' | |||
'''Теорема 3 (Петти и Рамачандран [14], 2005). Иерархия компонентов для неориентированного графа <math>G = (V, E, \ell) \;</math>, где <math>\ell: E \to \mathbb{R}^+</math>, может быть построена за время <math>O(m \alpha (m, n) + min \{ n \; log \; log \; r, n \; log \; n \})</math>, где r – отношение максимальной длины ребра к минимальной. Следовательно, поиск кратчайших путей из любого единственного источника может быть произведен за время <math>O(m \; log \; \alpha (m, n))</math>.''' | |||
Алгоритмы Хагерупа [9] и Петти-Рамачандрана [14] применяют тот же базовый подход, что и алгоритм Торупа: некоторая разновидность иерархии компонентов используется для определения групп вершин, которые можно безопасно посещать в любом порядке. Однако в случае ориентированных графов [9] и действительных длин ребер [14] иерархия Торупа становится неприменимой или неэффективной. Иерархия компонентов Хагерупа основывается на ориентированном аналоге [[Минимальное остовное дерево|минимального остовного дерева]]. Алгоритм Петти-Рамачандрана формирует определенный баланс на базе иерархии компонентов, а затем при вычислении кратчайших путей с единственным источником использует специализированную очередь приоритетов, реализующую преимущества этого баланса. | |||
Алгоритмы Хагерупа [ ] и Петти-Рамачандрана [14] применяют тот же базовый подход, что и алгоритм Торупа: некоторая разновидность иерархии компонентов используется для определения групп вершин, которые можно безопасно посещать в любом порядке. Однако в случае ориентированных графов [9] и действительных длин ребер [14] иерархия Торупа становится неприменимой или неэффективной. Иерархия компонентов Хагерупа основывается на ориентированном аналоге минимального остовного дерева. Алгоритм Петти-Рамачандрана формирует определенный баланс на базе иерархии компонентов, а затем при вычислении кратчайших путей с единственным источником использует специализированную очередь приоритетов, реализующую преимущества этого баланса. | |||
== Применение == | == Применение == | ||
Алгоритмы поиска кратчайших путей часто используются в качестве подпрограмм в других задачах оптимизации, таких как задачи о потоке и паросочетании [ ] и определении местоположения [19]. Широко практикуется такое коммерческое применение алгоритмов нахождения кратчайших путей, как поиск эффективных маршрутов в дорожных сетях – к примеру, в Google Maps, MapQuest или Yahoo Maps. | Алгоритмы поиска кратчайших путей часто используются в качестве подпрограмм в других задачах оптимизации, таких как задачи о потоке и паросочетании [1] и определении местоположения [19]. Широко практикуется такое коммерческое применение алгоритмов нахождения кратчайших путей, как поиск эффективных маршрутов в дорожных сетях – к примеру, в Google Maps, MapQuest или Yahoo Maps. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Алгоритм Торупа для решения SSSP-задачи [ ] выполняется за линейное время и потому является оптимальным. Основной задачей остается поиск SSSP-алгоритма с линейным временем выполнения, работающего на ориентированных графах с вещественными | Алгоритм Торупа для решения SSSP-задачи [17] выполняется за линейное время и потому является оптимальным. Основной задачей остается поиск SSSP-алгоритма с линейным временем выполнения, работающего на ''ориентированных'' графах с ''вещественными весам''и ребер. Наилучшее время выполнения для неориентированных графов с вещественными весами ребер приведено в теореме 3. Для ориентированных графов с целыми весами самые быстрые алгоритмы основаны на подходе Дейкстры (а не теореме 2) и выполняются за время <math>O(m \sqrt{log \; log \; n})</math> (рандомизированные) и <math>O(m + n \; log \; log \; n)</math> (детерминированные). | ||
Задача 1. Существует ли алгоритм поиска кратчайших путей с единственным источником для ориентированных графов с целыми весами с временем выполнения O(m)? | ''Задача 1. Существует ли алгоритм поиска кратчайших путей с единственным источником для ориентированных графов с целыми весами с временем выполнения O(m)?'' | ||
Задача 2. Существует ли алгоритм поиска кратчайших путей с единственным источником для ориентированных или неориентированных графов с вещественными весами с временем выполнения O(m) + o( | ''Задача 2. Существует ли алгоритм поиска кратчайших путей с единственным источником для ориентированных или неориентированных графов с вещественными весами с временем выполнения O(m) + o(n log n)?'' | ||
| Строка 48: | Строка 46: | ||
== Экспериментальные результаты == | == Экспериментальные результаты == | ||
Асано и Имаи [ ], а также Петти и др. оценили эффективность основанных на иерархии SSSP-алгоритмов [14, 17]. Исследования SSSP-алгоритмов на ориентированных графах с целочисленными весами производились неоднократно; наиболее актуальные сведения см. в работе [ ] и ссылках в ней. В последнее время исследователи стремятся найти практичные схемы предварительной обработки, способные очень быстро давать ответы на запрос кратчайших двухточечных путей. Подробнее о недавних работах в этой области – в [3, 11, 16]. | Асано и Имаи [2], а также Петти и др. [15] оценили эффективность основанных на иерархии SSSP-алгоритмов [14, 17]. Исследования SSSP-алгоритмов на ориентированных графах с целочисленными весами производились неоднократно; наиболее актуальные сведения см. в работе [8] и ссылках в ней. В последнее время исследователи стремятся найти практичные схемы предварительной обработки, способные очень быстро давать ответы на запрос кратчайших двухточечных путей. Подробнее о недавних работах в этой области – в [3, 11, 16]. | ||
== Наборы данных == | == Наборы данных == | ||
| Строка 57: | Строка 55: | ||
== См. также == | == См. также == | ||
* [[Алгоритм поиска кратчайших путей при помощи матричного произведения]] | * [[Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения]] | ||
== Литература == | == Литература == | ||
| Строка 95: | Строка 93: | ||
19. Thorup, M.: Quick and good facility location. In: Proceedings 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2003, pp. 178-185 | 19. Thorup, M.: Quick and good facility location. In: Proceedings 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2003, pp. 178-185 | ||
[[Категория: Совместное определение связанных терминов]] | |||
