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