262
правки
Изменения
м
→Алгоритм A*
Приведём немного изменённую версию этого алгоритма.
Возьмём функцию <tex>h(v): V \rightarrow \mathbb{R} </tex> - <b><i>потенциал(potential)</i></b> вершины. Тогда, с её помощью можно определить <b><i>редуцированную потенциальную стоимость(reduced cost)</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>правдоподобной(<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>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> лежит на кратчайшем пути, иначе редуцированная потенциальная стоимость положительна
**все посещённые вершины будут лежать на кратчайшем пути
== Двунаправленный A*==
* <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>
