Изменения
→Двунаправленный A*
== Проблема поиска кратчайшего пути ==
* отправная точка — вершина <tex>s</tex>, пункт назначения — вершина <tex>t</tex>
Цель: найти кратчайший путь <tex> s \rightsquigarrow t</tex>
}}Мы будем рассматривать сеть автомобильных дорог:* <tex>V</tex> — множество Количество перекрёстков* <tex>E</tex> — множество и дорог* <tex>l(uможет быть очень большим,v)</tex> — среднее времятогда обычные алгоритмы поиска пути будут работать очень долго, которое занимает проезд по дорогепоэтому попытаемся оптимизировать их для более быстрой работы.
==Алгоритм Дейкстры==
Скорость работы алгоритма Дейкстры сильно зависит от скорости операций с приоритетной очередью.
|}
Подходит только графов с целочисленными рёбрами.
* Будем складывать вершины в "корзины" <tex>B[i] = \{u \in B[i] : d(u)=i\}</tex>,* Наша наша структура данных будет поддерживать индекс <tex>L = \{\forall i : i<L \Rightarrow B[i] = \emptyset\}</tex>* На на каждом шаге алгоритма, если <tex>B[L]</tex> пусто, то увеличим <tex>L</tex>, а иначе достанем одну вершину из <tex>B[L]</tex>,* При при релаксации будем убирать вершину из исходной корзины и класть в корзину, соответствующую новому значению <tex>d(u)</tex>.
Можно заметить, что при такой реализации, все операции с приоритетной очередью будут выполняться за <tex>O(1)</tex>. Тогда, для одноуровневой реализации время работы алгоритма Дейкстры можно оценить как <tex>O(m+nC)</tex>, где <tex>C</tex> — максимальная длина ребра в графе.
Мы можем уменьшить количество посещённых вершин в алгоритме Дейкстры, просто запустив его и из начальной и из конечной вершины. Такая эвристика не испортит скорость работы в худшем случае.
Создадим две приоритетных очереди и запустим на одной из них алгоритм Дейкстры, ищущий <tex>d_{forward}(v)</tex> из <tex>s</tex>, а на другой — ищущий <tex>d_{reverse}(v)</tex> из <tex>t</tex>. Алгоритм завершит свою работу, когда какая-нибудь вершина <tex>z</tex> будет удалена из обоих обеих очередей.
Тонкость этого алгоритма заключается в том, что кратчайший путь <tex>s \rightsquigarrow t</tex> не обязательно пройдёт через вершину <tex>z</tex>. Поэтому после остановки двунаправленного поиска, нам необходимо перебрать все рёбра из вершин, имеющих <tex>d_{forward}(u)</tex> в
==Алгоритм A*==
Возьмём функцию <tex>h(v): V \rightarrow \mathbb{R} </tex> — <b>''потенциал''</b> (aнгл. ''potential'') вершины. Тогда, с её помощью можно определить <b>''потенциальную стоимость''</b> (англ. ''reduced cost'') каждого ребра как <tex>\ell_{h}(v,w) = \ell(v,w)-h(v)+h(w)</tex>
*<tex>\ell_{p_{r}}(v,w) = \ell(v,w)-p_{r}(w)+p_{r}(v)</tex> — если ребро обрабатывается в обходе, начатом в <tex>t</tex>
Чтобы избежать этой проблемы, необходимо, чтобы <tex>\ell_{p_{f}}(v,w) = \ell_{p_{r}}(v,w) \Leftrightarrow p_{f}(v) + p_{r}(v) = p_{f}(w) + p_{r}(w) = const</tex>. Кроме того, функции должны бить быть монотонными.
Решение — использовать усреднённые потенциальные функции:
*<tex>h_{f}(v) = \fracdfrac{p_{f}(v)-p_{r}(v)}{2}</tex>*<tex>h_{r}(v) = \fracdfrac{p_{r}(v)-p_{f}(v)}{2} = -h_{f}(v)</tex>
При таком выборе потенциальных функций, выполняется <tex>\forall u : h_{f}(u)+h_{r}(u)=0</tex> и тогда двунаправленный A* становится аналогичен двунаправленному алгоритму Дейкстры
К сожалению, двунаправленный алгоритм Дейкстры всего в два раза быстрее обычного, а это слишком медленно. Рассмотрим алгоритм поиска кратчайшего пути, состоящий из двух этапов:
# Препроцессинг:#* запускается единожды для графа,#* может занимать много времени,#* рассчитывает некую вспомогательную информацию.# Запрос:#* может использовать данные, полученные во время препроцессинга,#* запускается по требованию для пары <tex>(s,t)</tex>,#* должен выполняться очень быстро (в реальном времени).
Можно рассмотреть в этом ключе два примера:
Аббревиатура ALT расшифровывается как <b>A</b>* +<b>L</b>andmarks + <b>T</b>riangle inequality : A* + ориентиры + неравенство треугольника.
#Препроцессинг:#* взять небольшое количество вершин (например, 16), обозначив их как <b>ориентиры (landmarks)</b>(англ. ''landmarks''),#* для каждого из ориентиров посчитать кратчайшие пути до <b>всех</b> вершин,#* сохранить эти пути. #Запрос:#* используем A*,#* если некоторое ребро находится на кратчайшем пути между исходной точкой и ориентиром — по нему идём в первую очередь.
[[Файл:ALT.jpg|right|frame|рис. 1]]
Будем использовать неравенство треугольника для нижних оценок пути (см. рис. 1). Пусть <tex>A</tex> — один из ориентиров, тогда:
*<tex>dist(v,w)\ge geqslant dist(A,w)-dist(A,v)</tex>,*<tex>dist(v,w)\ge geqslant dist(v,A)-dist(w,A)</tex>,*<tex>dist(v,w)\ge geqslant \max\{dist(A,w)-dist(A,v),dist(v,A)-dist(w,A)\}</tex>.
Эта эвристика хорошо работает, на дорожных графах, для которых верно следующее: как правило, кратчайший путь затрагивает небольшое количество локальных дорог, потом крупную автомагистраль и снова некоторое количество локальных дорог.
Сложности в выборе ориентиров:
* хороший ориентир для запроса <tex>s \rightsquigarrow t</tex> должен находиться "до" <tex>s</tex> (точно не будет общих рёбер на кратчайшем пути) или "за" <tex>t</tex> (чем острее угол, тем меньше отклонение от предварительно посчитанного кратчайшего пути до искомого),* Нам нам нужно выбрать такие ориентиры, которые будут неплохими для всех запросов.
Выглядит логичным выбирать ориентиры на краю дорожной сети, тогда будет больше острых углов и ориентиры будут лучше.
====Плоскостной (planar)====
* разделим Разделим карту на <tex>k</tex> секторов одинаковой площади,* возьмём ориентиром наиболее удалённую точку от центра в каждом секторе.
Такой способ подходит, только если граф имеет относительно правильную форму. На практике обычно используется оптимизированная версия этого алгоритма.
Эта эвристика основывается на интуитивном наблюдении: не стоит посещать "локальные" дороги, когда мы находимся достаточно далеко и от <tex>s</tex>, и от <tex>t</tex>
Пусть вершина <tex>v</tex> лежит на кратчайшем пути <tex>P: s \rightsquigarrow t</tex>. Тогда, назовём <b>охватом (reach)</b> (англ. ''reach'') вершины <tex>v</tex> относительно <tex>P</tex> величину <tex>r(v,P) = \min\{dist(s,v), dist(v,t)\}</tex>. Охватом вершины относительно всего графа назовём величину <tex>r(v) = \max\limits_{P} r(v,P)</tex> — максимум по всем кратчайшим путям, содержащим <tex>v</tex>.
Помимо этого, будет полезным ввести понятие охвата ребра. Назовём охватом ребра <tex>(v,w)\in P</tex> относительно <tex>P</tex> величину <tex>\min\{dist(s,v), dist(w,t)\}</tex>. Аналогично, охватом ребра относительно всего графа назовём величину <tex>r(v,w) = \max\limits_{P} r((v,w),P)</tex> — максимум по всем кратчайшим путям, содержащим <tex>(v,w)</tex>.
[[Файл:reach1.jpg|right]]
Заметим, что вершины с большим охватом находятся вблизи середины некоторого длинного кратчайшего пути, то есть
* на больших автомагистралях вершины имеют большой охват,* на локальных перекрёстках (внутри населённых пунктов) вершины имеют маленький охват.
Во время обработки ребра <tex>(v,w)</tex>:
* удалим вершину <tex>w</tex>, если <tex>r(w)<\min\{d(s,v)+\ell(v,w), LB(w,t)\}</tex>,
* оценка <tex>LB(w,t)</tex> должна быть подобрана таким образом, чтобы, если бы <tex>P=(s,..,v,w,...,t)</tex> было кратчайшим путём, <tex>r(w)</tex> было бы больше.
[[Файл:reach2.jpg|right]]
Как искать нижнюю оценку длины пути <tex>LB(w,t)</tex>?
* Явно: Евклидово расстояние, с помощью ориентиров.* Неявно: сделать поиск двунаправленным.
Например, радиус <tex>R_{t}</tex> поиска в обратную сторону может быть нижней оценкой, т.к. если вершина <tex>w</tex> не была посещена поиском в обратную сторону, то <tex>d(w,t)\geq R_{t}</tex>
[[Файл:reach3.jpg|right]]
* на начальном этапе <tex>\forall v: r(v)\leftarrow 0</tex>,* для каждой вершины <tex>s \in V</tex> рассмотрим дерево кратчайших путей до всех других вершин <tex>T_{s}</tex>. , **найдём наиболее длинный путь <tex>P_{s\rightsquigarrow t}</tex>, содержащий <tex>v</tex>. , **Назовём глубиной вершины <tex>d_{s}(v)</tex> расстояние от <tex>s</tex>, высотой вершины <tex>h_{s}(v)</tex> — расстояние до наиболее далёкого потомка вершины,** Тогда, охватом вершины в этом дереве будет величина <tex>r_{s}(v) = \min\{d_{s}(v),h_{s}(v)\}</tex>,** Тогда обновим значение охвата <tex>r(v) \leftarrow \max\{r(v),r_{s}(v)\}</tex>.
Сложность алгоритма: <tex>O(nm)</tex>, поэтому он слишком медленный для больших графов и его нужно улучшить.
====Сокращение области поиска====
Заметим, что нам нужны только вершины с маленьким охватом <tex>r(v)\textless \varepsilon, \varepsilon=const</tex>. Заметим также, что если <tex>r(v) \geq geqslant \varepsilon</tex>, то существует такой путь <tex>P</tex>, что на нем лежит вершина <tex>v \in P</tex>, для которой выполняется условие <tex>r(v,P)\geq geqslant \varepsilon</tex>
Назовём кратчайший путь <tex>P_{s\rightsquigarrow t} = (s, s',...,v,...,t',t)</tex> <tex>\varepsilon</tex>-минимальным, если выполняются условия:
*<tex>dist(s,v)\geqgeqslant\varepsilon</tex>,*<tex>dist(s',v)\textless\varepsilon</tex>,*<tex>dist(v,t)\geqgeqslant\varepsilon</tex>,*<tex>dist(v,t')\textless\varepsilon</tex>.
Таким образом, алгоритм будет выглядеть так:
*найдём оценку охвата <tex>r'(v)</tex>, используя только <tex>\varepsilon</tex> — минимальные пути,* если <tex>r'(v)<\varepsilon</tex>, то оценка корректна: <tex>r(v)=r'(v)</tex>,* если же <tex>r'(v)\geq geqslant \varepsilon</tex>, то она нас не интересует: <tex>r(v)\geq geqslant r'(v)</tex>.
Полезно будет рассматривать <b>частично обработанные деревья</b> (<i>англ. ''partial trees</i>'') — деревья кратчайших путей, хранящие пути длиной, меньшей определённого порога. Тогда дерево кратчайших путей будет глубиной порядка <tex>2\varepsilon</tex>:* Установим установим <tex>G'\leftarrow G</tex> и <tex>\varepsilon\leftarrow \varepsilon_{0}</tex> (маленькое число),* Пока пока <tex>G'</tex> не пусто:** найдём частично обработанное дерево кратчайших путей из <tex>v</tex>, чтобы найти вершины с охватом <tex>r(v) \geq geqslant \varepsilon</tex>,** удалим из <tex>G'</tex> оставшиеся вершины (с охватом <tex>r(v) \textless\varepsilon</tex>, уже обработанные),** установим <tex>\varepsilon\leftarrow 3\varepsilon</tex>.
[[Файл:reach5.jpg|right]]
[[Файл:reach6.jpg|right]]
====Пенальти====
Предыдущее улучшение создаёт проблему: мы должны предполагать, что кратчайший путь может начинаться в вершине с маленьким охватом, которые мы отбрасываем на каждой итерации. Для того, чтобы принять их во внимание, мы введём новую величину — <b>пенальти</b>(<i>англ. ''penalty</i>'') — верхнюю оценку на длину кратчайшего пути в "отброшенной" зоне.
Пусть <tex>G_{i} = (V_{i},A_{i})</tex> — подграф исходного графа, полученный на <tex>i</tex>-й итерации алгоритма, описанного выше. Назовём входящим пенальти (<i>in-penalty</i>) вершины <tex>v\in V_{i}</tex> величину <tex>\max\{ \overline{r}(u,v) : u,v \in A \backslash A_{i}\}</tex>, если у <tex>v</tex> было как минимум одно выброшенное в процессе алгоритма входящее ребро, или ноль в противном случае.
====Сокращение путей====
Представим последовательность вершин степени 2 с большим охватом, идущих подряд. Добавим, <b>сокращающее ребро</b> (<i>англ. ''shortcut</i>'') — ребро, проходящее из начала пути в его конец с длиной, равной длине этого пути. Таким образом мы можем уменьшить охваты вершин на этом пути и ускорить препроцессинг (уменьшив количество проходимых рёбер), но увеличим память, необходимую для хранения нашего графа.
На этом шаге мы будем искать <b>пропускаемые</b> (англ. ''bypassable'') вершины. Назовём вершину <tex>v</tex> пропускаемой, если выполняется одно из двух условий:* <tex>v</tex> имеет только одно входящее ребро <tex>(u,v)</tex> и одно исходящее ребро <tex>(v,w)</tex> ,* <tex>v</tex> имеет два входящих ребра <tex>(u,v)</tex>, <tex>(w,v)</tex> и два исходящих ребра <tex>(v,w)</tex> ,<tex>(v,u)</tex>.В обоих случаях подразумевается, что <tex>u\neq w</tex>, то есть у <tex>v</tex> обязательно есть только два соседа. В первом случае, <tex>v</tex> — кандидат на односторонний пропуск (англ. ''one-way bypass''), во втором — на двухсторонний (англ. ''two-way bypass''). Мы будем использовать сокращающие рёбра, чтобы пропускать такие вершины.
Линия (line) — путь в графе, содержащий как минимум три вершины, так, что все вершины, кроме начальной и конечной, пропускаемые. Каждая пропускаемая вершина может принадлежать только одной линии. Линии также могут быть односторонне- и двухсторонне- пропускаемыми, в зависимости от типа вершин, которые они содержат. Легко заметить, что на линии могут лежать вершины только одного типа.
Такую же процедуру можно проделать с двусторонней линией, т.к. помимо оценок, указанных выше, можно добавить:
* <tex>\overline{r}(w,v)=\ell(w,v)+out\textrm{-}penalty(v)</tex>,* <tex>\overline{r}(v,u)=\ell(v,u)+in\textrm{-}penalty(v)</tex>.
====Фаза отладки====
* красные ромбы — ориентиры
* жёлтые ромбы — выбранные при поиске пути ориентиры
==См. также==
*[[Алгоритм Дейкстры]]
*[[Алгоритм A*]]
==Источники информации==
