Изменения

Функция <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));

Обновляет данные вершины в соответствие с данными выше определениями. Также поддерживает инвариант того, что в очереди U лежат только ненасыщенные вершины. //Функция '''function''' updateVertex(u): '''if''' u <tex>key(s)\ne</tex>. Возвращаемые значения сортируются в лексографическом порядке, т.е. сначала f <tex>k_1rhs(u) = \min\limits_{s' \in Pred(u)}(g(s') + c(s',u))</tex>, потом '''if''' u <tex>k_2(s)\in</tex>U U.remove(u) '''CalcKeyif'''(s): return [min(g(su); <tex>\ne</tex> rhs(su)) + h U.insert(s; t); min(g(s); rhsu, calcKey(su))];

Функция несколько раз перерасчитывает значение <tex>g(s)<// Обновляет данные вершины tex> у ненасыщенных вершин в соответствие с данными выше определенияминеубывающем порядке их ключей. Также поддерживает инвариант того, что в очереди U лежат только ненасыщенные Такой перерасчет значения <tex>g(s)</tex> будем называть ''расширением'' вершины. '''UpdateVertexfunction'''computeShortestPath(u): if u '''while''' U.topKey() < calcKey(t) '''or''' rhs(t) <tex>\ne</tex> fg(t) <tex>rhsu = U.pop(u) = \min\limits_{s '''if''' \in Predg(u)}> rhs(u) g(s'u) + c= rhs(s',u)); '''for''' <tex>s</tex> if u <tex>\in</tex> USucc(u) U.Remove UpdateVertex(us); if '''else''' g(u) = <tex>+\neinfty</tex> '''for''' s <tex>\in</tex> rhsSucc(u)<tex>\cup</tex> <tex>\{u\}</tex> U.Insert updateVertex(u; CalcKey(u)s);

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

{{Теорема|about=О монотонности изменения ключей|statement=В течение выполнения функции '''ComputeShortestPath''' вершины, взятые из очереди, монотонно не убывают.|proof=Доказательство [http://www.cs.cmu.edu/~maxim/files/aij04.pdf]}} {{Теорема|about=О необратимой насыщенности|statement=Если в функции '''ComputeShortestPath''' была взята переполненная вершина, то на следующей итерации она станет насыщенной.|proof=Доказательство [http://www.cs.cmu.edu/~maxim/files/aij04.pdf]}} {{Теорема|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>.|proof=Доказательство [http://www.cs.cmu.edu/~maxim/files/aij04.pdf]}} Таким образом мы описали алгоритм LPA*. Он неоднократно определяет путь вычисляет длину кратчайшего пути между вершинами <tex>f</tex> и <tex>t</tex>, используя при этом данные из предыдущих итераций. Очевидно, что в худшем случае (а именно когда все ребра вокруг текущей вершины изменили свой вес) алгоритм будет работать как последовательные вызовы алгоритма А* за <tex>O(n^2 \cdot m \cdot \log(n))</tex>. Улучшим эту оценку с помощью алгоритма D* lite.

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

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

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

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

'''Initializefunction'''initialize(): U = <tex>\varnothing</tex>; '''for ''' s <tex>s \in S</tex>V <tex>rhs(s) = g(s) = <tex>+\infty</tex> <tex>rhs(t) = 0</tex> U.Insertinsert(<tex>t</tex>; CalcKey, calcKey(<tex>t</tex>));

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

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

'''Mainfunction'''main(): '''Initialize'''initialize() computeShortestPath(); '''ComputeShortestPathwhile'''(); while (<tex>f \ne t</tex>) <font color="green">// '''if ''' (<tex>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 U</tex>U U.Updateupdate(<tex>s</tex>; ''', CalcKey'''(<tex>s</tex>)); '''ComputeShortestPath'''computeShortestPath(); === Асимптотика ===

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

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

'''for ''' s <tex>s \in S</tex>V <tex>rhs(s) = g(s) = <tex>+\infty</tex> <tex>rhs(t) = 0</tex> U.Insertinsert(<tex>t</tex>; , CalcKey(<tex>t</tex>));

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

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

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

'''if ''' (g(u) > rhs(u)) g(u) = rhs(u); '''for ''' <tex>s </tex> <tex>\in </tex> Pred(u)</tex> 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>f \ne t</tex>)t <font color="green">// if (<tex>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 ''' всех ориентированных ребер <tex>(u; , v)</tex> с измененными весами: Обновляем результат функции <tex>c(u; , v)</tex>; '''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 раза, что дает существенный рост производительности на практических задачах.

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