Изменения

procedure CalcKey(s) { return [min(g(s); rhs(s)) + h(s;sgoals_{goal});min(g(s); rhs(s))]; }

procedure '''Initialize'''() { <tex>U = null;</tex> <tex>for all s \in S</tex>{ <tex>rhs(s) = g(s) = 1;</tex>} <tex>rhs(s_start) = 0;</tex> <tex>U.Insert(s_{start};CalcKey(s_{start}));</tex> }

procedure '''UpdateVertex'''(<tex>u</tex>): { if (<tex>u != s_{start}</tex>) <tex>rhs(u) = min_{s' \in Pred(u)}(g(s')+c(s',u));</tex> if (<tex>u \in U</tex>) U.Remove(u); if (g(u) != rhs(u)){ U.Insert(<tex>u</tex>;CalcKey(<tex>u</tex>));} }

procedure '''ComputeShortestPath'''(): { while (U.TopKey()< CalcKey(sgoals_{goal}) OR rhs(sgoals_{goal}) != g(sgoals_{goal})) u = U.Pop(); if (g(u) > rhs(u)) g(u) = rhs(u); for all s 2 Succ(u) UpdateVertex(s); else g(u) = 1; for all s \in Succ(u) perec {u}{ UpdateVertex(s);} }

procedure Main() { Initialize(); while (s_start != s_goal) { ComputeShortestPath(); Wait for changes in edge costs; for all directed edges (u;v) with changed edge costs { Update the edge cost c(u;v); UpdateVertex(v); } } } Таким образом мы описали алгоритм LPA*. Он неоднократно определяет путь между вершинами <tex>s_start</tex> и <tex>s_goal</tex>, используя при этом данные из предыдущих итераций. Очевидно, что в худшем случае (а именно когда все ребра вокруг текущей вершины изменили свой вес) алгоритм будет работать как последовательные вызовы алгоритма А* за O(n^2*log(n)). Улучшим эту оценку с помощью алгоритма D* lite.'''Примечание''': на практике же такой подход тоже имеет место на плотных графах (или матрицах), так как в среднем дает оценку О(n*log(n)).