Изменения
→Двунаправленный A*
== Проблема поиска кратчайшего пути ==
* отправная точка — вершина <tex>s</tex>, пункт назначения — вершина <tex>t</tex>
Цель: найти кратчайший путь <tex> s \rightsquigarrow t</tex>
}}Мы будем рассматривать сеть автомобильных дорог:* <tex>V</tex> — множество Количество перекрёстков* <tex>E</tex> — множество и дорог* <tex>l(uможет быть очень большим,v)</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> в
*<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* становится аналогичен двунаправленному алгоритму Дейкстры
[[Файл: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>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> (англ. ''partial trees'') — деревья кратчайших путей, хранящие пути длиной, меньшей определённого порога. Тогда дерево кратчайших путей будет глубиной порядка <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>(англ. ''penalty'') — верхнюю оценку на длину кратчайшего пути в "отброшенной" зоне.
* красные ромбы — ориентиры
* жёлтые ромбы — выбранные при поиске пути ориентиры
==См. также==
*[[Алгоритм Дейкстры]]
*[[Алгоритм A*]]
==Источники информации==
