Изменения

'''Алгоритм D* (pronounced "D star") is any one of the following three related incremental search algorithms''' {{---}} алгоритм поиска кратчайшего пути во [[Основные определения теории графов|взвешенном ориентированном графе]], где структура графа неизвестна заранее или постоянно подвергается изменению. Разработан Свеном Кёнигом и Максимом Лихачевым в 2002 году.

== Алгоритм LPA*Обозначим множество <tex>S</tex> как множество вершин графа.Обозначим множество <tex>Succ(s) \in S</tex> как множество вершин, исходящих из вершины <tex>s</tex>. Аналогично множество <tex>Pred(s) \in S</tex> как множество вершин, входящих в вершину <tex>s</tex>. ==

Функция === Постановка задачи ===Дан [[Основные определения теории графов|взвешенный ориентированный граф]] <tex>0 <= сG(sV, s'E) <= +inf/tex>. Даны вершины: стартовая вершина <tex>f</tex> и конечная вершина <tex>t</tex> будет возвращать перехода из вершины . Требуется после каждого изменения графа <tex>sG</tex> в вершину уметь вычислять функцию <tex>g(s')</tex>. При этом для каждой известной вершины <tex>s' \in Succ(s)V</tex>.

=== Описание ===Функция <tex>g(s) </tex> будет возвращать последнее известное значение расстояние от наименьшую стоимость пути из вершины <tex>s_{start}f</tex> в <tex>s</tex> до . Её значение для алгоритма будет почти аналогичным значению в [[Алгоритм A* | алгоритме A*]], за исключением того, что в данном алгоритме наc интересуют только <tex>g(s)</tex>-значения известных вершин на данной итерации.

Если Будем поддерживать для каждой вершины два вида смежных с ней вершин:* Обозначим множество <tex>Succ(s = s_{start}) \subseteq V</tex>как множество вершин, исходящих из вершины <tex>rhs(s) = 0</tex>. Иначе * Обозначим множество <tex>rhsPred(s) = min_{s' \in pred(s)}(g(s') + c(s'subseteq V</tex> как множество вершин, входящих в вершину <tex>s)</tex>.

Будем говоритьФункция <tex>0 \leqslant c(s, что вершина s @A vertex ') \leqslant +\infty</tex> будет возвращать стоимость ребра <tex>(s is called locally consistent@, если s')</tex>. При этом <tex>gc(s, s') = rhs+\infty</tex> будет тогда и только тогда, когда ребра <tex>(s, s')</tex>Очевидно, что если все вершины "locally consistent", то мы можем найти расстояние от стартовой вершины до любойне существует.

Функция {{Определение|definition=Будем называть '''rhs-значением''' (англ. ''right-hand side value'') такую функцию <tex>keyrhs(s)</tex>, где которая будет возвращать потенциальное минимальное расстояние от <tex>sf</tex> - вершина, возвращает вектор из 2-ух значений до <tex>k_1(s)</tex>, по следующим правилам:<tex>k_2rhs(s)</tex>. <tex>k_1(= \begin{cases}0,& \text{if } s) = f \\\min(g\limits_{s' \in Pred(s), rhs}(g(s)') + hc(s', s_goals),& \text{otherwise}\end{cases}</tex>. Так как rhs-значение использует минимальное значение из минимальных расстояний от <tex>f</tex> до вершин, входящих в данную вершину <tex>k_2(s) = min(g(s)</tex>, rhs(это будет нам давать информацию об оценочном расстоянии от <tex>f</tex> до <tex>s))</tex>.}}

Если в конце поиска пути {{Определение|definition=Вершина <tex>g(s_{goal}) = +infs</tex>называется '''насыщенной''' (англ. ''locally consistent''), то мы не смогли найти путь от если <tex>s_{start}g(s) = rhs(s)</tex> до <tex>s_{goal}}</tex>

'''CalcKey'''(s): {{Определение return [|definition=Вершина <tex>min(g(s); rhs(s)) + h(s;s_{goal})</tex>;называется '''ненасыщенной''' (англ. ''locally underconsistent''), если <tex>min(g(s); < rhs(s))</tex>]; }}

'''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> }

'''UpdateVertex'''([[Эвристики для поиска кратчайших путей|Эвристическая функция]] <tex>uh(s,s')</tex>): {теперь должна быть неотрицательная и выполнять неравенство треугольника, т.е. if (<tex>u !h(t,t) = s_{start}0</tex>) и <tex>rhsh(us, t) = min_{s' \in Pred(u)}(gleqslant c(s,s')+ch(s',ut));</tex> if (для всех <tex>u s \in UV</tex>) U.Remove(u); if (g(u) != rhs(u)) U.Insert(<tex>uи </tex>;CalcKeys' \in Succ(<tex>us)</tex>)); }

{{Определение|definition=Будем называть '''ComputeShortestPathключом'''вершины такую функцию <tex>key(): { while (U.TopKey(s)< CalcKey(/tex>, которая возвращает вектор из 2-ух значений <tex>s_{goal}k_1(s)</tex>) OR rhs(, <tex>s_{goal}k_2(s) != g(s_{goal}</tex>)). u = U.Pop* <tex>k_1(s); if = \min(g(us) > , rhs(us))+ h(s, t)</tex> g* <tex>k_2(us) = rhs\min(g(u); for all s 2 Succ(u) UpdateVertex, rhs(s);)</tex>, elseгде <tex>s</tex> - вершина из множества <tex>V</tex> }}Если в конце поиска пути <tex>g(ut) = 1; for all +\infty</tex>, то мы не смогли найти путь от <tex>f</tex> до <tex>s \in Succ(u) perec {u}t</tex> UpdateVertex(s); }на текущей итерации. Но после следующего изменения графа путь вполне может найтись.

'''Main'''(): { Initialize(); while (<tex>s_{start} != s_{goal}</tex>) { 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*. Он неоднократно определяет путь между вершинами '''function''' main(): initialize() '''while''' ''true'' computeShortestPath() <texfont color="green">s_start</tex> и <tex>s_goal/ В данный момент мы знаем кратчайший путь из f в t.</texfont>, используя при этом данные из предыдущих итераций Ждем каких-либо изменений графа. Очевидно '''for''' всех ориентированных ребер (u, что в худшем случае v) с измененными весами: Обновляем результат функции c(а именно когда все ребра вокруг текущей вершины изменили свой весu, v) алгоритм будет работать как последовательные вызовы алгоритма А* за O(n^2*log updateVertex(n)v). Улучшим эту оценку с помощью алгоритма D* lite.

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

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

Функция несколько раз перерасчитывает значение <tex>g(s)</tex> у ненасыщенных вершин в неубывающем порядке их ключей. Такой перерасчет значения <tex>g(s)</tex> будем называть ''расширением'' вершины. '''Initializefunction'''computeShortestPath(): '''while''' U.topKey() < calcKey(t) '''or''' rhs(t) <tex>\ne</tex> g(t) u = U .pop() '''if''' g(u) > rhs(u) g(u) = null;rhs(u) '''for all ''' <tex>s </tex> <tex>\in S</tex>Succ(u) <tex>rhs UpdateVertex(s) = '''else''' g(su) = 1<tex>+\infty</tex> '''for''' s <tex>\in</tex>rhsSucc(s_u) <tex>\cup</tex> <tex>\{goalu\}) = 0</tex> U.Insert updateVertex(sgoal;CalcKey(sgoal)s);

'''UpdateVertex'''(u): if (u 6= s_{goal}) rhs(u) = mins02Succ(u)(c(u;s0) + g(s0));f07’g if (u 2 U) U.Remove(u);f08’g if (g(u) 6= rhs(u)) U.Insert(u;CalcKey(u));Асимптотика ===

{{Теорема|about=О монотонности изменения ключей|statement=В течение выполнения функции '''ComputeShortestPath'''() while (Uвершины, взятые из очереди, монотонно не убывают.TopKey()<_ CalcKey(s_{start}) OR rhs(s_{start}) 6= g(s_{start})) u |proof= UДоказательство [http://www.cs.cmu.Pop();edu/~maxim/files/aij04.pdf] if (g(u) > rhs(u)) g(u) = rhs(u); for all s 2 Pred(u) UpdateVertex(s); else g(u) = 1; for all s 2 Pred(u) [ fug UpdateVertex(s);}}

{{Теорема|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 \cdot m \cdot \log(n))</tex>. Улучшим эту оценку с помощью алгоритма D* lite. '''Примечание''': на практике же такой подход тоже имеет место на плотных графах (или матрицах), так как в среднем дает оценку <tex>O(n \cdot \log(n))</tex>. == Алгоритм D* (Первая версия) ==Пока что был описан только алгоритм LPA*. Он находит кратчайшее расстояние между начальной и конечной вершинами при любом изменении данного графа. Его первоначальный поиск полностью совпадает с алгоритмом A*, но последующие итерации способны использовать информацию из предыдущих поисков. === Постановка задачи ===Дан [[Основные определения теории графов|взвешенный ориентированный граф]] <tex> G(V, E) </tex>. Даны вершины <tex>f</tex> и <tex>t</tex>. Требуется в процессе движения по кратчайшему пути в графе <tex>G</tex> обновлять значения функции <tex>g(s)</tex> при поступлении новой информации о графе <tex>G</tex>. Теперь на основе LPA* опишем алгоритм D*, который способен определять расстояние между текущей вершиной <tex>f</tex>, в которой, допустим, находится способный к сканированию местности "робот", и конечной вершиной <tex>t</tex> при каждом изменении графа в то время, как наш "робот" движется вдоль найденного пути. [[Файл:Схема_движения_робота_Dstar.png|350px|thumb|right|Схема движения "робота" в процессе работы алгоритма D*. Информация о серых клетках ему неизвестна до тех пор, пока они не попадут в его зону обзора. В данном примере зона обзора составляет 1 клетку в 8-ми направлениях.]] === Описание ===Опишем первую версию алгоритма D*. Так как при движении по кратчайшему пути путь может только сокращаться и происходит изменение только стартовой вершины, то можно применить идею из алгоритма LPA*. '''Примечание''': Большинство функций переходят в данный алгоритм без изменений, поэтому опишем только измененные части. Для начала мы поменяем направление поиска в графе.  Теперь функция g(s) хранит минимальное известное расстояние от <tex>t</tex> до <tex>s</tex>. Свойства остаются прежними. [[Эвристики для поиска кратчайших путей|Эвристическая функция]] <tex>h(s,s')</tex> теперь должна быть неотрицательная и обратно-устойчивая, т.е. <tex>h(f,f) = 0</tex> и <tex>h(f, s) \leqslant h(f,s') + c(s',s)</tex> для всех <tex>s \in S</tex> и <tex>s' \in Pred(s)</tex>. Очевидно, что при движении робота <tex>f</tex> изменяется, поэтому данные свойства должны выполняться для всех <tex>f \in V</tex>. Дополнительное условие выхода также меняется, т.е. при <tex>g(f) = +\infty</tex> путь не найден на данной итерации. Иначе путь найден и "робот" может проследовать по нему. '''Примечание''': Так же следует отметить, что функция '''Initialize''' не обязана инициализировать абсолютно все вершины перед стартом алгоритма. Это важно, так как на практике число вершин может быть огромным, и только немногие будут пройдены роботом в процессе движения. Так же это дает возможность добавления/удаления ребер без потери устойчивости всех подграфов данного графа. === Псевдокод ===При такой постановке задачи псевдокод не сильно меняется, но функция '''Main''' все-таки претерпевает значительные изменения.  '''function''' calcKey(s): '''return''' [min(g(s), rhs(s)) + h(f,s), min(g(s), rhs(s))]  '''function''' initialize(): U = <tex>\varnothing</tex> '''for''' s <tex>\in</tex> V rhs(s) = g(s) = <tex>+\infty</tex> rhs(t) = 0 U.insert(t, calcKey(t))  '''Mainfunction'''UpdateVertex(u): Initialize'''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.remove(u); '''if''' g(u) <tex>\ne</tex> rhs(u) U.insert(u, calcKey(u))  '''function''' ComputeShortestPath();: '''while ''' U.topKey() < calcKey(f) or rhs(f) <tex>\ne</tex> g(f) u = U.pop() '''if''' (g(u) > rhs(u)) g(u) = rhs(u) '''for''' s <tex>\in</tex> Pred(u) updateVertex(s) '''else''' g(u) = <tex>+\infty</tex> '''for''' <tex>s</tex> <tex>\in</tex> Pred(s_u) <tex>\cup</tex> {startu} 6 updateVertex(s)  '''function''' main(): initialize() computeShortestPath() '''while''' <tex>f \ne t</tex> <font color="green">// '''if''' (g(f) = s_<tex>+\infty</tex>) тогда путь на данной итерации не найден.</font> <tex>f</tex> = такая вершина s', что <tex>\min\limits_{goals' \in Succ(f)}(c(f, s') + g(s'))</tex> Передвинулись вдоль найденного пути и изменили вершину <tex>f</tex> Сканируем роботом какие-либо изменения в графе или убеждаемся, что граф остается прежним. '''if ''' граф изменился '''for''' всех ориентированных ребер <tex>(u, v)</tex> с измененными весами: Обновляем результат функции <tex>c(u, v)</tex> updateVertex(u) '''for''' <tex>s</tex> <tex>\in</tex> U U.update(s, CalcKey(gs)) computeShortestPath(sstart)  = == Асимптотика === {{Теорема|author=Свен Кёниг|about=Об устойчивой насыщенности вершин|statement=Функция '''ComputeShortestPath''' в данной версии алгоритма ''расширяет'' вершину максимум 2 раза, а именно 1 раз, если вершина ненасыщена, и максимум 1раз, если она переполнена.|proof=Доказательство [http://www.cs.cmu.edu/~maxim/files/aij04.pdf]}} == Алгоритм D* (Вторая версия) == === Описание ===В первой версии алгоритма была серьезная проблема в том, что для каждой вершины в приоритетной очереди нужно было обновлять ключ суммарно за <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') then there is no known path + 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> не должны быть обязательно смежными. Такие свойства не противоречат свойствами из первой версии, а лишь усиливают их. Допустим, что после того, как робот продвинется вдоль найденного пути на предыдущих итерациях, из вершины <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. sstart === Псевдокод === argmins02Succ  '''function''' calcKey(s): '''return''' [min(g(s), rhs(s)) + h(f, s) + <tex>K_m</tex>, min(g(sstarts), rhs(s))]  '''function''' initialize(c): U = <tex>\varnothing</tex> <tex>K_m = 0</tex> '''for''' s <tex>\in</tex> V rhs(s) = g(sstart;s) = <tex>+\infty</tex> rhs(t) = 0 U.insert(t, CalcKey(t))  '''function''' 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.remove(u) '''if''' g(u) <tex>\ne</tex> rhs(u) U.insert(u, calcKey(u)) 0 '''function''' computeShortestPath(): '''while''' U.topKey() < calcKey(f) '''or''' rhs(f) <tex>\ne</tex> g(f) <tex>K_{old}</tex> = U.topKey() u = U.pop() '''if''' <tex>K_{old}</tex> < calcKey(u) U.insert(u, calcKey(u)) '''if''' (g(u) > rhs(u)) g(u)= rhs(u);f22’g Move to sstart; '''for''' <tex>s</tex> <tex>\in</tex> Pred(u) updateVertex(s) '''else''' g(u) = <tex>+\infty</tex>f23’g Scan graph '''for changed edge costs;''' <tex>s</tex> <tex>\in</tex> Pred(u) <tex>\cup</tex> <tex>\{u\}</tex> updateVertex(s)  '''function''' main(): <tex>s_{last} = f</tex> initialize() computeShortestPath() '''while''' f <tex>\ne</tex> t <font color="green">// if (g(f) = <tex>+\infty</tex>) тогда путь на данной итерации не найден.</font> <tex>f</tex> = такая вершина s', что <tex>\min\limits_{s' \in Succ(f)}(c(f, s') + g(s'))</tex> Передвинулись вдоль найденного пути и изменили вершину <tex>f</tex>. Сканируем роботом какие-либо изменения в графе или убеждаемся, что граф остается прежним.f24’g '''if any edge costs changed''' граф изменилсяf25’g <tex>K_m = K_m + h(s_{last}, h_{start})</tex> <tex>s_{last} = f</tex> '''for all directed edges ''' всех ориентированных ребер (u;, v) with changed edge costsс измененными весами:f26’g Update the edge cost Обновляем результат функции c(u;, v);f27’g UpdateVertex updateVertex(u);f28’g for all s 2 U computeShortestPath() === Асимптотика === f29’g С помощью введения ключевого модификатора <tex>K_m</tex> и отложенного обновления ключей вершин получилось убрать из итерации алгоритма <tex>O(n \cdot \log(n))</tex> операций, которые тратились на обновление очереди <tex>U</tex>.UpdateОчевидно, что на основе теорем, приведенных выше, алгоритм использовал <tex>O(s;CalcKey2 \cdot n \cdot \log(sn))</tex> операций. Итак, нам удалось уменьшить константу в 2 раза, что дает существенный рост производительности на практических задачах. === Пример работы ==={| class="wikitable" |- | style="width:50%;text-align:center;" | [[Файл:Схема_движения_робота_Dstarv2_1.png|400px]] || style="width:50%;text-align:center;" | [[Файл:Схема_движения_робота_Dstarv2_2.png|400px]]f30’g |- | style="width:50%;text-align:center;" | Итерации в функции '''ComputeShortestPath''' на исходном графе. || 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]* [http://www.cs.cmu.edu/~maxim/files/aij04.pdf LPA*]* [http://pub1.willowgarage.com/~konolige/cs225b/dlite_tro05.pdf D* lite] [[Категория: Алгоритмы и структуры данных]][[Категория: Кратчайшие пути в графах ]]