262
правки
Изменения
→Двунаправленный A*
**все посещённые вершины будут лежать на кратчайшем пути
== Двунаправленный A*==
Для двунаправленной версии алгоритма нам нужны две потенциальные функции:
* <tex>p_{f}(v)</tex>, оценивающая <tex>dist(v,t)</tex>
* <tex>p_{r}(v)</tex>, оценивающая <tex>dist(s,v)</tex>
В этом случае появляется дополнительная проблема: различные редуцированные стоимости у рёбер для различных обходов:
*<tex>\ell_{p_{f}}(v,w) = \ell(v,w)-p_{f}(v)+p_{f}(w)</tex> - если ребро обрабатывается в обходе, начатом в <tex>s</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) = \frac{p_{f}(v)-p_{r}(v)}{2}</tex>
*<tex>h_{r}(v) = \frac{p_{r}(v)-p_{f}(v)}{2} = -h_{f}(v)</tex>
При таком выборе потенциальных функций, выполняется <tex>\forall u : h_{f}(u)+h_{r}(u)=0</tex> и тогда двунаправленный A* становится аналогичен двунаправленному алгоритму Дейкстры
