418
правок
Изменения
→Псевдокод
Таким образом мы описали алгоритм LPA*. Он неоднократно определяет путь между вершинами <tex>s_{start}</tex> и <tex>s_{goal}</tex>, используя при этом данные из предыдущих итераций. Очевидно, что в худшем случае (а именно когда все ребра вокруг текущей вершины изменили свой вес) алгоритм будет работать как последовательные вызовы алгоритма А* за <tex>O(n^2 \cdot log(n))</tex>. Улучшим эту оценку с помощью алгоритма D* lite.
'''Примечание''': на практике же такой подход тоже имеет место на плотных графах (или матрицах), так как в среднем дает оценку <tex>ОO(n \cdot log(n))</tex>.
== Алгоритм D* ==
