418
правок
Изменения
м
Нет описания правки
UpdateVertex(s);
=== Асимптотика === Таким образом мы описали алгоритм LPA*. Он неоднократно определяет путь между вершинами <tex>f</tex> и <tex>t</tex>, используя при этом данные из предыдущих итераций. Очевидно, что в худшем случае (а именно когда все ребра вокруг текущей вершины изменили свой вес) алгоритм будет работать как последовательные вызовы алгоритма А* за <tex>O(n^2 \cdot m \cdot \log(n))</tex>. Улучшим эту оценку с помощью алгоритма D* lite.
'''Примечание''': на практике же такой подход тоже имеет место на плотных графах (или матрицах), так как в среднем дает оценку <tex>O(n \cdot \log(n))</tex>.
U.Update(s; '''CalcKey'''(s));
'''ComputeShortestPath'''();
=== Асимптотика ===
{{Теорема
