Изменения
→Алгоритм A*
=Алгоритм A*=
основная статья: [[Алгоритм A*]]
Приведём немного изменённую версию этого алгоритма.
Возьмём функцию <tex>h(v): V \rightarrow \mathbb{R} </tex> - <b><i>потенциал</i></b> вершины. Тогда, с её помощью можно определить <b><i>редуцированную стоимость</i></b> каждого ребра как <tex>\ell_{h}(v,w) = \ell(v,w)-h(v)+h(w)</tex>
Заметим, что замена <tex>\ell</tex> на <tex>\ell_{h}</tex> не изменит кратчайших путей: возьмём любой путь <tex>P = (s=v_{0},v_{1},...,v_{k},v_{k+1}=t)</tex>. Тогда <tex>\ell_{h}(P) = \ell_{h}(s,v_{1}), \ell_{h}(s,v_{w})</tex>. Тогда <tex>\ell_{h}(P) = \ell_{h}(s,v_{1})+\ell_{h}(v_{1},v_{2})+...+\ell_{h}(v_{k},t) =</tex> <tex> \ell(s,v_{1})-h(s)+h(v_{1})+\ell(v_{1},v_{2})-h(v_1)+h(v_{2})+...+\ell(v_{k},t)-h(v_k)+h(t) = </tex> <tex>\ell(P)-h(s)+h(t)</tex>.
Таким образом длины все путей <tex>s \rightsquigarrow t</tex> изменятся на одну и ту же величину <tex>h(t)-h(s)</tex>
В нашем случае, алгоритм 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>правдоподобной</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>dist(v,t)</tex>
Главное отличие от алгоритма Дейкстры в том, что A* является <b>целенаправленным</b> алгоритмом - он обрабатывает в первую очередь те вершины, которые находятся ближе к результату.
Скорость работы алгоритма A*:
* в худшем случае - <tex>h(v)=0</tex> - вырождается в алгоритм Дейкстры
* в лучшем случае - <tex>\forall v: h(v)=dist(v,t)</tex>
**<tex>\ell_{h}(v,w)=0</tex>, если ребро <tex>(v,w)</tex> лежит на кратчайшем пути, иначе редуцированная стоимость положительна
**все посещённые вершины будут лежать на кратчайшем пути
