Изменения

Основная функция, описывающая алгоритм

'''Main'''():

'''Initialize'''();

while (true)

'''ComputeShortestPath'''();

//В данный момент мы знаем кратчайший путь из <tex>s_{start}</tex> в <tex>s_{goal}</tex>.

Ждем каких-либо изменений графа.

for всех ориентированных ребер <tex>(u; v)</tex> с измененными весами:

Обновляем результат функции <tex>c(u; v)</tex>;

'''UpdateVertex'''(<tex>v</tex>);

Теперь опишем составные элементы подробнее

Функция инициализации исходного графа устанавливает для всех вершин кроме стартовой (<tex>s_{start}</tex>) значения <tex>g(s)</tex> и <tex>rhs(s)</tex> равными бесконечности. Для стартовой <tex>rhs(s_{start})=0</tex>. Очевидно, что минимальное расстояние от стартовой вершины до самой себя должно быть равным 0, но <tex>g(s_{start})=+\infty</tex>. Это сделано для того, чтобы стартовая вершина была ненасыщенной и имела право попасть в приоритетную очередь.

'''Initialize'''():

//Заведем [[Двоичная куча|приоритетную очередь]] <tex>U</tex>, в которую будем помещать вершины. Сортировка будет производиться по функции <tex>key(s)</tex>.

<tex>U = \varnothing;</tex>

<tex>rhs(s_{start}) = 0;</tex>

U.Insert(<tex>s_{start}</tex>; CalcKey(<tex>s_{start}</tex>));

//Функция <tex>key(s)</tex>. Возвращаемые значения сортируются в лексографическом порядке, т.е. сначала <tex>k_1(s)</tex>, потом <tex>k_2(s)</tex>

'''CalcKey'''(s):

return [<tex>\min(g(s); rhs(s)) + h(s; s_{goal})</tex>; <tex>\min(g(s); rhs(s))</tex>];

'''UpdateVertex'''(<tex>u</tex>):

<tex>rhs(u) = \min\limits_{s' \in Pred(u)}(g(s') + c(s',u));</tex>

U.Remove(u);

U.Insert(<tex>u</tex>; CalcKey(<tex>u</tex>));

// Функция неоднократно перерасчитывает значение <tex>g(s)</tex> у ненасыщенных вершин в неубывающем порядке их ключей. Такой перерасчет значения <tex>g(s)</tex> будем называть ''расширением'' вершины.

'''ComputeShortestPath'''():

while (U.TopKey() < CalcKey(<tex>s_{goal}</tex>) OR rhs(<tex>s_{goal}</tex>) <tex>\ne</tex> g(<tex>s_{goal}</tex>))

u = U.Pop();

g(u) = rhs(u);

for <tex>s \in Succ(u)</tex>

for <tex>s \in Succ(u) \cup \{u\}</tex>

UpdateVertex(s);

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