251
правка
Изменения
м
Нет описания правки
При такой реализации, время работы алгоритма Дейкстры можно оценить как <tex>O(m+n(1+ \sqrt{C}))</tex>
====Калибровка (англ. ''caliber'')====Введём величину <b><i>''калибр (caliber)</i>''</b> вершины <tex>c(v)</tex> — вес минимального ребра, входящего в <tex>v</tex> , или <tex>\infty</tex>, если в вершину не входит ни одно ребро. Будем говорить, что текущее значение <tex>d(v)</tex> точно, если оно равно длине пути <tex>s \rightsquigarrow v</tex>.
{{Лемма
|about = 1
Модифицируем нашу MLB — структуру: будем хранить помеченные вершины в двух структурах: дерево поиска <tex>F</tex> и приоритетная очередь <tex>B</tex>, реализованная на MLB.
Алгоритм, приведённый ниже, называется <b><i>''алгоритмом умной очереди '' (англ. ''smart queue'')</i></b>.
Вершины в <tex>F</tex> будут иметь точные метки <tex>d(u)</tex>. Если <tex>F</tex> непусто, мы удалим оттуда вершину и прорелаксируем всех её соседей. Если же <tex>F</tex> пусто, мы достанем из
Приведём немного изменённую версию этого алгоритма.
Возьмём функцию <tex>h(v): V \rightarrow \mathbb{R} </tex> — <b><i>''потенциал '' (aнгл. ''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>.
В нашем случае, алгоритм 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>d(v,t)</tex>
Главное отличие от алгоритма Дейкстры в том, что A* является <b>информированным</b> алгоритмом — он обрабатывает в первую очередь те вершины, которые находятся ближе к результату.
