Изменения
Нет описания правки
<tex>rhs(s) = min_{s' \in pred(s)}(g(s') + c(s', s)</tex>
Будем говорить, что вершина s насыщена @A vertex s is called locally consistent@, если <tex>g(s) = rhs(s)</tex>переполненанесыщена
Очевидно, что если все вершины "locally consistent", то мы можем найти расстояние от стартовой вершины до любой.
}
Таким образом мы описали алгоритм LPA*. Он неоднократно определяет путь между вершинами <tex>s_start</tex> и <tex>s_goal</tex>, используя при этом данные из предыдущих итераций. Очевидно, что в худшем случае (а именно когда все ребра вокруг текущей вершины изменили свой вес) алгоритм будет работать как последовательные вызовы алгоритма А* за <tex>O(n^2*log(n))</tex>. Улучшим эту оценку с помощью алгоритма D* lite.
'''Примечание''': на практике же такой подход тоже имеет место на плотных графах (или матрицах), так как в среднем дает оценку О(n*log(n)).
