Изменения

Функция <tex>0 \leqslant c(s, s') \leqslant +\infty</tex> будет возвращать стоимость перехода из вершины ребра <tex>(s, s')</tex> в вершину . При этом <tex>c(s, s') = +\infty</tex>. При этом будет тогда и только тогда, когда ребра <tex>(s, s' \in Succ(s)</tex>не существует.

|definition=Будем называть '''rhs-значением''' (англ. ''right-hand side value'') такую функцию <tex>rhs(s)</tex>, которая будет возвращать потенциальное минимальное расстояние от <tex>f</tex> до <tex>s</tex> по следующим правилам:

|definition=Вершина <tex>s</tex> называется '''насыщенной''' (англ. ''locally consistent''), если <tex>g(s) = rhs(s)</tex>

|definition=Вершина <tex>s</tex> называется '''переполненной''' (англ. ''locally overconsistent''), если <tex>g(s) > rhs(s)</tex>

|definition=Вершина <tex>s</tex> называется '''ненасыщенной''' (англ. ''locally underconsistent''), если <tex>g(s) < rhs(s)</tex>

'''Mainfunction'''main(): '''Initialize'''initialize(); '''while (true) '''ComputeShortestPath''true'' computeShortestPath(); <font color="green">//В данный момент мы знаем кратчайший путь из f в t.</font>

'''for ''' всех ориентированных ребер (u; , v) с измененными весами: Обновляем результат функции c(u; , v); '''UpdateVertex'''updateVertex(v);

Теперь опишем составные элементы подробнееФункция инициализации исходного графа устанавливает для всех вершин кроме стартовой (вершины <tex>f</tex>) значения <tex>g(s)</tex> и <tex>rhs(s)</tex> равными бесконечности. Для стартовой <tex>rhs(f)=0</tex>. Очевидно, что минимальное расстояние от стартовой вершины до самой себя должно быть равным 0, но <tex>g(f)=+\infty</tex>. Это сделано для того, чтобы стартовая вершина была ненасыщенной и имела право попасть в приоритетную очередь. '''Initializefunction'''initialize(): <font color="green">// Заведем [[Двоичная куча|приоритетную очередь]] U, в которую будем помещать вершины. </font> <font color="green">// Сортировка будет производиться по функции key(s).</font> U = <tex>\varnothing</tex>; '''for ''' s <tex>\in</tex> V rhs(s) = g(s) = <tex>+\infty;</tex> rhs(f) = 0; U.Insertinsert(f; CalcKey, calcKey(f));

//Функция <tex>key(s)</tex>. Возвращаемые значения сортируются в лексографическом порядке, // т.е. то есть сначала сортируется по <tex>k_1(s)</tex>, потом по <tex>k_2(s)</tex> '''CalcKeyfunction'''calcKey(s): '''return ''' [min(g(s); , rhs(s)) + h(s; , t); , min(g(s); , rhs(s))];

// Обновляет данные вершины в соответствие с данными выше определениями. // Также поддерживает инвариант того, что в очереди U лежат только ненасыщенные вершины. '''UpdateVertexfunction'''updateVertex(u): '''if ''' u <tex>\ne</tex> f <tex>rhs(u) = \min\limits_{s' \in Pred(u)}(g(s') + c(s',u));</tex> '''if ''' u <tex>\in</tex> U U.Removeremove(u); '''if ''' g(u) <tex>\ne</tex> rhs(u) U.Insertinsert(u; CalcKey, calcKey(u));

// Функция несколько раз перерасчитывает значение <tex>g(s)</tex> у ненасыщенных вершин в неубывающем порядке их ключей. // Такой перерасчет значения <tex>g(s)</tex> будем называть ''расширением'' вершины. '''ComputeShortestPathfunction'''computeShortestPath(): '''while (''' U.TopKeytopKey() < CalcKeycalcKey(t) OR '''or''' rhs(t) <tex>\ne</tex> g(t)) u = U.Poppop(); '''if ''' g(u) > rhs(u) g(u) = rhs(u); '''for ''' <tex>s </tex> <tex>\in</tex> Succ(u) UpdateVertex(s); '''else''' g(u) = <tex>+\infty</tex>; '''for ''' s <tex>\in</tex> Succ(u) <tex>\cup</tex> <tex>\{u\}</tex> UpdateVertexupdateVertex(s);

|statement=После выполнения функции '''ComputeShortestPath''' можно проследить восстановить путь из <tex>f</tex> в <tex>t</tex>. Для этого, начиная с вершины <tex>t</tex>, нужно постоянно передвигаться к такой вершине <tex>s'</tex>, входящей в <tex>t</tex>, чтобы <tex>g(s') + c(s',s)</tex> было минимальным, до тех пора, пока не будет достигнута вершина <tex>f</tex>.

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

Пока что был описан только алгоритм LPA*. Он способен неоднократно определять находит кратчайшее расстояние между начальной и конечной вершинами при любом изменении данного графа. Его первоначальный поиск полностью совпадает с алгоритмом A*, но последующие итерации способны использовать информацию из предыдущих поисков.

[[Файл:Схема_движения_робота_Dstar.png|350px|thumb|right|Схема движения "робота" в процессе работы алгоритма D*. Информация о серых клетках ему неизвестна до определенной итерациитех пор, пока они не попадут в его зону обзора. В данном примере зона обзора составляет 1 клетку в 8-ми направлениях.]]

'''CalcKeyfunction'''calcKey(s): '''return ''' [min(g(s),rhs(s)) + h(f,s); , min(g(s),rhs(s))];

'''Initializefunction'''initialize(): U = <tex>\varnothing</tex>; '''for ''' s <tex>\in</tex> V

U.Insertinsert(t; CalcKey, calcKey(t));

'''UpdateVertexfunction'''UpdateVertex(u): '''if ''' u <tex>\ne</tex> t rhs(u) = <tex>\min\limits_{s' \in Succ(u)}(c(u,s')+g(s'));</tex> '''if ''' u <tex>\in</tex> U U.Removeremove(u); '''if ''' g(u) <tex>\ne</tex> rhs(u) U.Insertinsert(u; CalcKey, calcKey(u));

'''ComputeShortestPathfunction'''ComputeShortestPath(): '''while (''' U.TopKeytopKey() < CalcKeycalcKey(f) OR or rhs(f) <tex>\ne</tex> g(f)) u = U.Poppop(); '''if ''' (g(u) > rhs(u)) g(u) = rhs(u); '''for ''' s <tex>\in</tex> Pred(u) UpdateVertexupdateVertex(s); '''else''' g(u) = <tex>+\infty</tex>; '''for ''' <tex>s </tex> <tex>\in</tex> Pred(u) <tex>\cup</tex> {u} UpdateVertexupdateVertex(s);

'''Mainfunction'''main(): '''Initialize'''initialize() computeShortestPath(); '''ComputeShortestPathwhile'''(); while (<tex>f \ne t</tex>) <font color="green">// '''if ''' (g(f) = <tex>+\infty</tex>) тогда путь на данной итерации не найден.</font>

Передвинулись вдоль найденного пути и изменили вершину <tex>f</tex>;

'''if (''' граф изменился) '''for ''' всех ориентированных ребер <tex>(u; , v) </tex> с измененными весами: Обновляем результат функции <tex>c(u; , v);</tex> updateVertex(u) '''UpdateVertexfor'''(u); for <tex>s </tex> <tex>\in</tex> U U.Updateupdate(s; ''', CalcKey'''(s)); '''ComputeShortestPath'''computeShortestPath();

Допустим, что после того, как робот продвинется вдоль найденного пути на предыдущих итерациях, из вершины <tex>s </tex> в <tex>s'</tex>, он обнаружит изменения в графе. Первая компонента ключей <tex>k_1(s')</tex> может уменьшится максимум на <tex>h(s,s')</tex> (по определению ключа). Вторая компонента не зависит от функции h. Аналогично первой версии алгоритма, мы должны уменьшить первую компоненту ключа у всех вершин в очереди U. Очевидно, что <tex>h(s,s')</tex> будет одинаковым для всех вершин из U. Порядок в очереди не изменится, если произвести уменьшение. Следовательно уменьшение можно отложить, тем самым очередь не придется перестраивать на каждой итерации. Так же исходя из нового определения функции <tex>h</tex>, её значение будет всегда меньше, чем разность первых компонент ключей у соседних по приоритету вершин. Таким образом мы можем добавлять h(s,s') ко всем <tex>k_1(s')</tex> у ключей вершин из U.

Будем называть <tex>K_m</tex> ключевым модификатором. В нем мы и будет хранить сумму <tex>h(s,s')</tex>, которые нужно добавить ко всем вершинам из U.

'''CalcKeyfunction'''calcKey(s): '''return ''' [min(g(s);, rhs(s)) + h(f;, s) + <tex>K_m</tex>;, min(g(s); , rhs(s))];

'''Initializefunction'''initialize(): U = <tex>\varnothing</tex>;

'''for ''' s <tex>\in</tex> V

U.Insertinsert(t; , CalcKey(t));

'''UpdateVertexfunction'''updateVertex(u): '''if (''' u <tex>\ne</tex> t) rhs(u) = <tex>\min\limits_{s' \in Succ(u)}(c(u,s')+g(s'));</tex> '''if (''' u <tex>\in</tex> U) U.Removeremove(u); '''if (''' g(u) <tex>\ne</tex> rhs(u)) U.Insertinsert(u; CalcKey, calcKey(u));

'''ComputeShortestPathfunction'''computeShortestPath(): '''while (''' U.TopKeytopKey() < CalcKeycalcKey(f) OR '''or''' rhs(f) <tex>\ne</tex> g(f)) <tex>K_{old}</tex> = U.TopKeytopKey(); u = U.Poppop();

'''if (''' <tex>K_{old}</tex> < '''CalcKey'''calcKey(u)) U.Insertinsert(u; '''CalcKey''', calcKey(u));

'''if ''' (g(u) > rhs(u)) g(u) = rhs(u); '''for ''' <tex>s </tex> <tex>\in</tex> Pred(u) UpdateVertexupdateVertex(s); '''else''' g(u) = <tex>+\infty</tex>; '''for ''' <tex>s </tex> <tex>\in</tex> Pred(u) <tex>\cup</tex> <tex>\{u\} </tex> '''UpdateVertex'''updateVertex(s);

'''Mainfunction'''main():

'''Initialize'''initialize() computeShortestPath(); '''ComputeShortestPathwhile'''(); while (f <tex>\ne</tex> t) <font color="green">// if (g(f) = <tex>+\infty</tex>) тогда путь на данной итерации не найден.</font>

Передвинулись вдоль найденного пути и изменили вершину <tex>f</tex>;.

'''if (''' граф изменился) <tex>K_m = K_m + h(s_{last}, h_{start})</tex>; <tex>s_{last} = f</tex>; '''for ''' всех ориентированных ребер (u; , v) с измененными весами: Обновляем результат функции c(u; , v); '''UpdateVertex'''updateVertex(u); '''ComputeShortestPath'''computeShortestPath() === Асимптотика === С помощью введения ключевого модификатора <tex>K_m</tex> и отложенного обновления ключей вершин получилось убрать из итерации алгоритма <tex>O(n \cdot \log(n))</tex> операций, которые тратились на обновление очереди <tex>U</tex>. Очевидно, что на основе теорем, приведенных выше, алгоритм использовал <tex>O(2 \cdot n \cdot \log(n);)</tex> операций. Итак, нам удалось уменьшить константу в 2 раза, что дает существенный рост производительности на практических задачах.

==СсылкиИсточники информации==