1632
правки
Изменения
м
rollbackEdits.php mass rollback
Мы можем уменьшить количество посещённых вершин в алгоритме Дейкстры, просто запустив его и из начальной и из конечной вершины. Такая эвристика не испортит скорость работы в худшем случае.
Создадим две приоритетных очереди и запустим на одной из них алгоритм Дейкстры, ищущий <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* становится аналогичен двунаправленному алгоритму Дейкстры
