418
правок
Изменения
м
→Алгоритм LPA*
rhs(f) = 0;
U.Insert(f; CalcKey(f));
//Функция <tex>key(s)</tex>. Возвращаемые значения сортируются в лексографическом порядке, т.е. сначала <tex>k_1(s)</tex>, потом <tex>k_2(s)</tex>
=== Асимптотика ===
{{Теорема
|author=Свен Кёниг
|about=О монотонности изменения ключей
|statement=В течение выполнения функции '''ComputeShortestPath''' вершины, взятые из очереди монотонно не убывают.
}}
{{Теорема
|author=Свен Кёниг
|about=О необратимой насыщенности
|statement=Если в функции '''ComputeShortestPath''' была взята переполненная вершина, то на следующей итерации она станет насыщенной.
}}
Таким образом мы описали алгоритм LPA*. Он неоднократно определяет путь между вершинами <tex>f</tex> и <tex>t</tex>, используя при этом данные из предыдущих итераций. Очевидно, что в худшем случае (а именно когда все ребра вокруг текущей вершины изменили свой вес) алгоритм будет работать как последовательные вызовы алгоритма А* за <tex>O(n \cdot m \cdot \log(n))</tex>. Улучшим эту оценку с помощью алгоритма D* lite.
