262
правки
Изменения
м
→Алгоритм A*
В нашем случае, алгоритм A* будет эквивалентен алгоритму Дейкстры, на графе <tex>G_{h}</tex>, у которого стоимости рёбер заменили на их потенциальные стоимости. На каждом шаге необходимо будет выбирать из очереди вершину <tex>v</tex> с минимальным значением <tex>\ell(P_{s \rightsquigarrow v})-h(s)+h(v)</tex>. Очевидно, <tex>h(s)</tex> будет одинаковым для любой вершины <tex>v</tex>.
Назовём функцию <tex>h</tex> <b>правдоподобной (<i>feasible</i>)</b>, если <tex>\forall (u,v): \ell_{h}(u,v) \geqslant 0</tex>. Известно, что, если <tex>h(t)\leqslant 0</tex> и <tex>h</tex> правдоподобна, то для любого <tex>v</tex>, <tex>h(v)</tex> - нижняя граница <tex>distd(v,t)</tex>
Главное отличие от алгоритма Дейкстры в том, что A* является <b>информированным</b> алгоритмом - он обрабатывает в первую очередь те вершины, которые находятся ближе к результату.
Скорость работы алгоритма A*:
* в худшем случае - <tex>h(v)=0</tex> - вырождается в алгоритм Дейкстры
* в лучшем случае - <tex>\forall v: h(v)=distd(v,t)</tex>
**<tex>\ell_{h}(v,w)=0</tex>, если ребро <tex>(v,w)</tex> лежит на кратчайшем пути, иначе потенциальная стоимость положительна
**все посещённые вершины будут лежать на кратчайшем пути
Для двунаправленной версии алгоритма нам нужны две потенциальные функции:
* <tex>p_{f}(v)</tex>, оценивающая <tex>distd(v,t)</tex>* <tex>p_{r}(v)</tex>, оценивающая <tex>distd(s,v)</tex>
В этом случае появляется дополнительная проблема: различные потенциальные стоимости у рёбер для различных обходов:
