3622
правки
Изменения
м
Теперь опишем {{Определение|definition=Будем называть '''rhs-значением''' (англ. ''right-hand side value'') такую функцию <tex>rhs(s)</tex>. Эта функция будет использовать минимальные расстояние из минимальных расстояний от <tex>s_{start}</tex> до вершин, входящих в данную вершины <tex>s</tex>. Потенциально это и которая будет нам давать информацию о возвращать потенциальное минимальное расстояние от <tex>s_{start}f</tex> до <tex>s</tex>.по следующим правилам:
Функция {{Определение|definition=Будем называть '''ключом''' вершины такую функцию <tex>key(s)</tex>, где <tex>s</tex> - вершина, которая возвращает вектор из 2-ух значений <tex>k_1(s)</tex>, <tex>k_2(s)</tex>. * <tex>k_1(s) = \min(g(s), rhs(s)) + h(s, s_{goal}t)</tex>. * <tex>k_2(s) = \min(g(s), rhs(s))</tex>.,где <tex>s</tex> - вершина из множества <tex>V</tex>}}Если в конце поиска пути <tex>g(s_{goal}t) = +\infty</tex>, то мы не смогли найти путь от <tex>s_{start}f</tex> до <tex>s_{goal}t</tex> на текущей итерации. Но после следующего изменения графа путь вполне может найтись.
Теперь опишем составные элементы подробнееФункция инициализации исходного графа устанавливает для всех вершин кроме стартовой (<tex>s_{start}</tex>) значения <tex>g(s)</tex> и <tex>rhs(s)</tex> равными бесконечности. Для стартовой <tex>g(s_{start})=0</tex>. Очевидно, что минимальное расстояние от стартовой Обновляет данные вершины до самой себя должно быть равным 0, но <tex>rhs(s_{start})=+\infty</tex>в соответствие с данными выше определениями. Это сделано для Также поддерживает инвариант того, чтобы стартовая вершина была ненасыщенной и имела право попасть что в приоритетную очередьочереди U лежат только ненасыщенные вершины. '''Initializefunction'''updateVertex(u): { //Заведем приоритетную очередь '''if''' u <tex>U\ne</tex>, в которую будем помещать вершины. Сортировка будет производиться по функции f <tex>keyrhs(su)</tex>. <tex>U = \varnothing;min\limits_{s' \in Pred(u)}(g(s') + c(s',u))</tex> for '''if''' u <tex>s \in S</tex>U <tex>rhsU.remove(su) = '''if''' g(su) = \infty;</tex> \ne</tex>rhs(s_{start}u) = 0;</tex> U.Insertinsert(<tex>s_{start}</tex>; CalcKeyu, calcKey(<tex>s_{start}</tex>u)); }
//Функция <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>]; }=== Асимптотика ===
{{Теорема|about=О монотонности изменения ключей|statement=В течение выполнения функции '''UpdateVertexComputeShortestPath'''(<tex>u<вершины, взятые из очереди, монотонно не убывают.|proof=Доказательство [http://www.cs.cmu.edu/~maxim/files/tex>):aij04.pdf]}} {{Теорема if (<tex>u \ne s_{start}</tex>) |about=О необратимой насыщенности <tex>rhs(u) |statement= min_{sЕсли в функции '''ComputeShortestPath' \in Pred(u)}(g(s') + c(s'была взята переполненная вершина,u));<то на следующей итерации она станет насыщенной.|proof=Доказательство [http:/tex> if (<tex>u \in U</tex>) Uwww.cs.cmu.Remove(u); if (<tex>g(u) \ne rhs(u)<edu/tex>) U.Insert(<tex>u<~maxim/tex>; CalcKey(<tex>u<files/tex>));aij04.pdf] }}
// Функция неоднократно перерасчитывает значение {{Теорема|statement=После выполнения функции '''ComputeShortestPath''' можно восстановить путь из <tex>g(s)f</tex> у ненасыщенных вершин в неубывающем порядке их ключей. Такой перерасчет значения <tex>g(s)t</tex> будем называть ''расширением'' . Для этого, начиная с вершины. '''ComputeShortestPath'''(): { while (U.TopKey() < CalcKey(<tex>s_{goal}t</tex>) OR rhs(, нужно постоянно передвигаться к такой вершине <tex>s_{goal}) \ne g(s_{goal}s'</tex>)) u = U.Pop(); if (g(u) , входящей в <tex> rhs(u)) g(u) = rhs(u); for t</tex>s \in Succ(u), чтобы </tex> UpdateVertexg(s'); else g+ c(us',s) = <tex>+\infty</tex>; for было минимальным, до тех пора, пока не будет достигнута вершина <tex>s \in Succ(u) \cup \{u\}f</tex>. UpdateVertex(s);|proof=Доказательство [http://www.cs.cmu.edu/~maxim/files/aij04.pdf] }}
Теперь на основе LPA* опишем алгоритм D*Дан [[Основные определения теории графов|взвешенный ориентированный граф]] <tex> G(V, который способен определять расстояние между текущей вершиной E) </tex>. Даны вершины <tex>s_{start}f</tex>, и <tex>t</tex>. Требуется в процессе движения по кратчайшему пути в которой, допустим, находится курсорграфе <tex>G</робот, и конечной вершиной tex> обновлять значения функции <tex>s_{goal}g(s)</tex> при каждом изменении графа в то время, как наш робот движется вдоль найденного путипоступлении новой информации о графе <tex>G</tex>.
[[Файл:Схема_движения_робота_Dstarv2_1.png|350px|thumb|right|Итерации Допустим, что после того, как робот продвинется вдоль найденного пути на предыдущих итерациях, из вершины <tex>s</tex> в функции <tex>s'</tex>, он обнаружит изменения в графе. Первая компонента ключей <tex>k_1(s')</tex> может уменьшится максимум на <tex>h(s,s'ComputeShortestPath)</tex> (по определению ключа). Вторая компонента не зависит от функции h. Аналогично первой версии алгоритма, мы должны уменьшить первую компоненту ключа у всех вершин в очереди U. Очевидно, что <tex>h(s,s')</tex> будет одинаковым для всех вершин из U. Порядок в очереди не изменится, если произвести уменьшение. Следовательно уменьшение можно отложить, тем самым очередь не придется перестраивать на каждой итерации. Так же исходя из нового определения функции <tex>h</tex>, её значение будет всегда меньше, чем разность первых компонент ключей у соседних по приоритету вершин. Таким образом мы можем добавлять h(s,s') ко всем <tex>k_1(s' на исходном графе)</tex> у ключей вершин из U.]]
[[Файл:Схема_движения_робота_Dstarv2_2Будем называть <tex>K_m</tex> ключевым модификатором.png|350px|thumb|right|Итерации в функции В нем мы и будет хранить сумму <tex>h(s,s'''ComputeShortestPath''' после изменения графа)</tex>, которые нужно добавить ко всем вершинам из U. (Второй вызов функции)]]
→Ссылки
'''Алгоритм D*''' {{---}} алгоритм поиска кратчайшего пути во [[Основные определения теории графов|взвешенном ориентированном графе]], где структура графа неизвестна заранее или постоянно подвергается изменению. Разработан Свеном Кёнигом и Максимом Лихачевым в 2002 году.
== Алгоритм LPA* ==
=== Постановка задачи ===
Дан [[Основные определения теории графов|взвешенный ориентированный граф]] <tex> G(V, E) </tex>. Даны вершины : стартовая вершина <tex>s_{start}f</tex> и конечная вершина <tex>s_{goal}t</tex>. Требуется после каждого изменения графа <tex>G</tex> уметь вычислять функцию <tex>g(s)</tex> для каждой известной вершины <tex>s \in V</tex>
=== Описание ===
Функция <tex>g(s)</tex> будет возвращать последнее известное (и самое минимальное) значение расстояния от наименьшую стоимость пути из вершины <tex>s_{start}f</tex> в <tex>s</tex> до . Её значение для алгоритма будет почти аналогичным значению в [[Алгоритм A* | алгоритме A*]], за исключением того, что в данном алгоритме наc интересуют только <tex>g(s)</tex>-значения известных вершин на данной итерации.
Будем поддерживать для каждой вершины два вида смежных с ней вершин:
* Обозначим множество <tex>Succ(s) \in subseteq V</tex> как множество вершин, исходящих из вершины <tex>s</tex>. * Обозначим множество <tex>Pred(s) \in subseteq V</tex> как множество вершин, входящих в вершину <tex>s</tex>. Ясно, что обязано соблюдаться условие: <tex>Succ(s) \subseteq V</tex> и <tex>Pred(s) \subseteq V</tex>.
Функция <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>не существует.
<tex>rhs(s) =
\begin{cases}
0,& \text{if } s = s_{start} f \\min_\min\limits_{s' \in Pred(s)}(g(s') + c(s', s),& \text{otherwise}
\end{cases}
</tex>
Так как rhs-значение использует минимальное значение из минимальных расстояний от <tex>f</tex> до вершин, входящих в данную вершину <tex>s</tex>, это будет нам давать информацию об оценочном расстоянии от <tex>f</tex> до <tex>s</tex>.
}}
{{Определение
|definition=Вершина <tex>s</tex> называется '''насыщенной''' (англ. ''locally consistent''), если <tex>g(s) = rhs(s)</tex>
}}
{{Определение|definition=Вершина <tex>s</tex> может быть 3-х видов:* насыщенаназывается '''переполненной''' (англ. ''locally overconsistent''), если <tex>g(s) = > rhs(s)</tex>* переполнена, если }} {{Определение|definition=Вершина <tex>g(s) > rhs(s)</tex>* ненасыщенаназывается '''ненасыщенной''' (англ. ''locally underconsistent''), если <tex>g(s) < rhs(s)</tex>}}
Очевидно, что если все вершины насыщены, то мы можем найти расстояние от стартовой вершины до любой. Такой граф будем называть устойчивым (насыщенным).
[[Эвристики для поиска кратчайших путей|Эвристическая функция]] <tex>h(s,s')</tex> теперь должна быть неотрицательная и выполнять неравенство треугольника, т.е.
<tex>h(s_{goal}t,s_{goal}t) = 0</tex> и <tex>h(s, s_{goal}t) \leqslant c(s,s') + h(s',s_{goal}t)</tex> для всех <tex>s \in V</tex> и <tex>s' \in Succ(s)</tex>
=== Псевдокод ===
Основная функция, описывающая алгоритм
'''Mainfunction'''main(): { initialize() '''Initializewhile'''(); while (true) { '''ComputeShortestPath'true'' computeShortestPath(); <font color="green">// В данный момент мы знаем кратчайший путь из <tex>s_{start}</tex> f в <tex>s_{goal}t.</texfont>.
Ждем каких-либо изменений графа.
'''for ''' всех ориентированных ребер <tex>(u; , v)</tex> с измененными весами: { Обновляем результат функции c(u, v) updateVertex(v) Функция инициализации исходного графа устанавливает для всех вершин кроме стартовой вершины <tex>f</tex> значения <tex>g(s)</tex> и <tex>crhs(s)</tex> равными бесконечности. Для стартовой <tex>rhs(f)=0</tex>. Очевидно, что минимальное расстояние от стартовой вершины до самой себя должно быть равным 0, но <tex>g(u; vf)=+\infty</tex>;. Это сделано для того, чтобы стартовая вершина была ненасыщенной и имела право попасть в приоритетную очередь. '''UpdateVertexfunction'''initialize(): <font color="green">// Заведем [[Двоичная куча|приоритетную очередь]] U, в которую будем помещать вершины.</font> <font color="green">// Сортировка будет производиться по функции key(s).</font> U = <tex>v\varnothing</tex> '''for''' s <tex>\in</tex>V rhs(s) = g(s);= <tex>+\infty</tex> } rhs(f) = 0 }U.insert(f, calcKey(f)) Функция <tex>key(s)</tex>. Возвращаемые значения сортируются в лексографическом порядке, то есть сначала сортируется по <tex>k_1(s)</tex>, потом по <tex>k_2(s)</tex> }'''function''' calcKey(s): '''return''' [min(g(s), rhs(s)) + h(s, t), min(g(s), rhs(s))]
Функция несколько раз перерасчитывает значение <tex>g(s)</tex> у ненасыщенных вершин в неубывающем порядке их ключей. Такой перерасчет значения <tex>g(s)</tex> будем называть ''расширением'' вершины.
'''function''' 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''' <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>
updateVertex(s)
Таким образом мы описали алгоритм LPA*. Он неоднократно определяет путь вычисляет длину кратчайшего пути между вершинами <tex>s_{start}f</tex> и <tex>s_{goal}t</tex>, используя при этом данные из предыдущих итераций. Очевидно, что в худшем случае (а именно когда все ребра вокруг текущей вершины изменили свой вес) алгоритм будет работать как последовательные вызовы алгоритма А* за <tex>O(n^2 \cdot m \cdot \log(n))</tex>. Улучшим эту оценку с помощью алгоритма D* lite.
'''Примечание''': на практике же такой подход тоже имеет место на плотных графах (или матрицах), так как в среднем дает оценку <tex>O(n \cdot \log(n))</tex>.
== Алгоритм D* (Первая версия) ==Пока что был описан только алгоритм LPA*. Он способен неоднократно определять находит кратчайшее расстояние между начальной и конечной вершинами при любом изменении данного графа. Его первоначальный поиск полностью совпадает с алгоритмом A*, но последующие итерации способны использовать информацию из предыдущих поисков.
=== Постановка задачи ===
Теперь на основе LPA* опишем алгоритм D*, который способен определять расстояние между текущей вершиной <tex>f</tex>, в которой, допустим, находится способный к сканированию местности "робот", и конечной вершиной <tex>t</tex> при каждом изменении графа в то время, как наш "робот" движется вдоль найденного пути. [[Файл:Схема_движения_робота_Dstar.png|350px|thumb|right|Схема движения курсора/"робота " в процессе работы алгоритма D*. Информация о серых клетках ему неизвестна до определенной итерациитех пор, пока они не попадут в его зону обзора. В данном примере зона обзора составляет 1 клетку в 8-ми направлениях.]]
=== Описание ===
Опишем первую версию алгоритма D*. ОчевидноТак как при движении по кратчайшему пути путь может только сокращаться и происходит изменение только стартовой вершины, что большинство вершин в процессе движения робота остаются неизменными, поэтому мы можем то можно применить алгоритм идею из алгоритма LPA*.
'''Примечание''': Большинство функций переходят в данный алгоритм без изменений, поэтому опишем только измененные части.
Для начала мы поменяем направление поиска в графе.
Теперь функция g(s) хранит минимальное известное расстояние от <tex>s_{goal}t</tex> до <tex>s</tex>. Свойства остаются прежними.
[[Эвристики для поиска кратчайших путей|Эвристическая функция]] <tex>h(s,s')</tex> теперь должна быть неотрицательная и обратно-устойчивая, т.е.
<tex>h(s_{start}f,s_{start}f) = 0</tex> и <tex>h(s_{start}f, s) \leqslant h(s_{start}f,s') + c(s',s)</tex> для всех <tex>s \in S</tex> и <tex>s' \in Pred(s)</tex>. Очевидно, что при движении робота <tex>s_{start}f</tex> изменяется, поэтому данные свойства должны выполняться для всех <tex>s_{start} f \in V</tex>.
Дополнительное условие выхода также меняется, т.е. при <tex>g(s_{start}f) = +\infty</tex> путь не найден на данной итерации. Иначе путь найден и "робот " может проследовать по нему.
'''Примечание''': Так же следует отметить, что функция '''Initialize''' не обязана инициализировать абсолютно все вершины перед стартом алгоритма. Это важно, так как в на практике число вершин может быть огромным , и только немногие будут пройдены робот роботом в процессе движения. Так же это дает возможность добавления/удаления ребер без потери устойчивости всех подграфов данного графа.
=== Псевдокод (Первая версия) ===При такой постановке задачи псевдокод не сильно меняется. Но , но функция '''Main''' все-таки претерпевает значительные изменения.
'''CalcKeyfunction'''calcKey(s): '''return ''' [<tex>\min(g(s);, rhs(s)) + h(s_{start};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(s_{goal}t) = 0</tex> U.Insertinsert(<tex>s_{goal}</tex>; CalcKeyt, calcKey(<tex>s_{goal}</tex>t));
'''UpdateVertexfunction'''UpdateVertex(u): '''if (''' u <tex>u \ne s_{goal}</tex>) t rhs(u) = <tex>min_\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>s_{start}</tex>f) or rhs(f) OR <tex>rhs(s_{start}) \ne g(s_{start})</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>s_{start} f \ne s_{goal}t</tex>) <font color="green">// '''if ''' (<tex>g(s_{start}f) = <tex>+\infty</tex>) тогда путь на данной итерации не найден.</font> <tex>s_{start}f</tex> = такая вершина s', что <tex>min_\min\limits_{s' \in Succ(s_{start}f)}(c(s_{start}f, s') + g(s'))</tex> Передвинулись вдоль найденного пути и изменили вершину <tex>s_{start}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>)); ComputeShortestPathcomputeShortestPath(); === Асимптотика ===
{{Теорема
|about=Об устойчивой насыщенности вершин
|statement=Функция '''ComputeShortestPath''' в данной версии алгоритма ''расширяет'' вершину максимум 2 раза, а именно 1 раз, если вершина ненасыщена, и максимум 1 раз, если она переполнена.
|proof=Доказательство [http://www.cs.cmu.edu/~maxim/files/aij04.pdf]
}}
== Описание Алгоритм D* (2 Вторая версия) == === Описание ===В первой версии алгоритма была серьезная проблема в том, что для каждой вершины в приоритетной очереди нужно было обновлять ключ суммарно за <tex>O(n \cdot \log(n))</tex>. Это дорогая операция, так как очередь может содержать огромное число вершин. Воспользуемся оригинальным методом поиска и изменим основной цикл, чтобы избежать постоянного перестроения очереди <tex>U</tex>.
Теперь эвристическая функция должна поддерживать неравенство треугольника для всех вершин <tex>s,s',s'' \in V</tex>, т.е. <tex>h(s,s'') \leqslant h(s, s') + h(s',s'')</tex>. Так же должно выполняться свойство <tex>h(s,s') \leqslant c^*(s,s')</tex>, где <tex>c^*(s,s')</tex> - стоимость перехода по кратчайшему пути из <tex>s</tex> в <tex>s'</tex>, при этом <tex>s</tex> и <tex>s'</tex> не должны быть обязательно смежными. Такие свойства не противоречат свойствами из первой версии, а лишь усиливают их.
=== Псевдокод (Вторая версия) ===
'''CalcKeyfunction'''calcKey(s): '''return ''' [<tex>\min(g(s);, rhs(s)) + h(s_{start};f, s) + K_m</tex>;K_m</tex>\, min(g(s); , rhs(s))</tex>];
'''Initializefunction'''initialize(): U = <tex>\varnothing</tex>;
<tex>K_m = 0</tex>
'''for ''' s <tex>s \in S</tex>V <tex>rhs(s) = g(s) = <tex>+\infty</tex> <tex>rhs(s_{goal}t) = 0</tex> U.Insertinsert(<tex>s_{goal}</tex>; t, CalcKey(<tex>s_{goal}</tex>t));
'''UpdateVertexfunction'''updateVertex(u): '''if (''' u <tex>u \ne s_{goal}</tex>) t rhs(u) = <tex>min_\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>s_{start}</tex>f) '''or''' rhs(f) OR <tex>rhs(s_{start}) \ne g(s_{start})</tex>g(f) <tex>K_{old} </tex> = U.TopKeytopKey()</tex>; u = U.Poppop();
'''if (''' <tex>K_{old}</tex> < CalcKeycalcKey(<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> UpdateVertexupdateVertex(s);
'''Mainfunction'''main(): <tex>s_{last} = s_{start}f</tex> '''Initialize'''initialize() computeShortestPath(); '''ComputeShortestPathwhile'''(); while (f <tex>s_{start} \ne s_{goal}</tex>)t <font color="green">// if (<tex>g(s_{start}f) = <tex>+\infty</tex>) тогда путь на данной итерации не найден.</font> <tex>s_{start}f</tex> = такая вершина s', что <tex>min_\min\limits_{s' \in Succ(s_{start}f)}(c(s_{start}f, s') + g(s'))</tex> Передвинулись вдоль найденного пути и изменили вершину <tex>s_{start}f</tex>;.
Сканируем роботом какие-либо изменения в графе или убеждаемся, что граф остается прежним.
'''if (''' граф изменился) <tex>K_m = K_m + h(s_{last}, h_{start})</tex>; <tex>s_{last} = s_{start}f</tex>; '''for ''' всех ориентированных ребер <tex>(u; , v)</tex> с измененными весами: Обновляем результат функции c(u, v) updateVertex(u) computeShortestPath() === Асимптотика === С помощью введения ключевого модификатора <tex>K_m</tex> и отложенного обновления ключей вершин получилось убрать из итерации алгоритма <tex>O(n \cdot \log(n))</tex>cопераций, которые тратились на обновление очереди <tex>U</tex>. Очевидно, что на основе теорем, приведенных выше, алгоритм использовал <tex>O(2 \cdot n \cdot \log(u; vn))</tex>операций. Итак, нам удалось уменьшить константу в 2 раза, что дает существенный рост производительности на практических задачах. === Пример работы ==={| class="wikitable" |- | style="width:50%;text-align:center;" | [[Файл:Схема_движения_робота_Dstarv2_1.png|400px]] || style="width:50%;text-align:center;" | [[Файл:Схема_движения_робота_Dstarv2_2.png|400px]] |- | style="width:50%;text-align:center;" | Итерации в функции '''UpdateVertexComputeShortestPath'''(u)на исходном графе. || style="width:50%;text-align:center; " | Итерации в функции '''ComputeShortestPath''' после изменения графа. (Второй вызов функции);|}
==СсылкиИсточники информации==
* [http://en.wikipedia.org/wiki/D* Wikipedia:D*]
* [http://idm-lab.org/project-a.html Sven Koenig` web page]
