Изменения

'''Алгоритм D*''' {{---}} алгоритм поиска кратчайшего пути во [[Основные определения теории графов|взвешенном ориентированном графе]], где структура графа неизвестна заранее или постоянно подвергается изменению. Разработан Свеном Кёнигом и Максимом Лихачевым в 2002 году.

Дан [[Основные определения теории графов|взвешенный ориентированный граф ]] <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>Succg(s) \in V</tex> как множество вершин, исходящих будет возвращать наименьшую стоимость пути из вершины <tex>f</tex> в <tex>s</tex>. Её значение для алгоритма будет почти аналогичным значению в [[Алгоритм A* | алгоритме A*]], за исключением того, что в данном алгоритме наc интересуют только <tex>g(s)</tex>-значения известных вершин на данной итерации.

Аналогично Будем поддерживать для каждой вершины два вида смежных с ней вершин:* Обозначим множество <tex>Succ(s) \subseteq V</tex> как множество вершин, исходящих из вершины <tex>s</tex>. * Обозначим множество <tex>Pred(s) \in subseteq V</tex> как множество вершин, входящих в вершину <tex>s</tex>.

Функция <tex>0 \le сleqslant c(s, s') \le 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>grhs(s)</tex> , которая будет возвращать последнее известное потенциальное минимальное расстояние от <tex>f</tex> до <tex>s</tex> по следующим правилам:<tex>rhs(s) = \begin{cases}0,& \text{if } s = f \\\min\limits_{s' \in Pred(и самое s)}(g(s') + c(s', s),& \text{otherwise}\end{cases}</tex>Так как rhs-значение использует минимальное) значение расстояния из минимальных расстояний от <tex>f</tex> до вершин, входящих в данную вершину <tex>s</tex>, это будет нам давать информацию об оценочном расстоянии от вершины <tex>s_{start}f</tex> до <tex>s</tex>.}}

Если {{Определение|definition=Вершина <tex>s = s_{start}</tex>:<tex dpi="120">rhsназывается '''насыщенной''' (sангл. ''locally consistent'') = 0, если </tex>Иначе :<tex dpi="120">rhsg(s) = min_{s' \in predrhs(s)}(g(s') + c(s', s)</tex>}}

{{Определение|definition=Вершина <tex>s</tex> может быть 3-х видов:* насыщена, если <tex>gназывается '''переполненной''' (sангл. ''locally overconsistent'') = rhs(s)</tex>* переполнена, если <tex>g(s) > rhs(s)</tex>* ненасыщена, если <tex>g(s) < rhs(s)</tex>}}

Очевидно{{Определение|definition=Вершина <tex>s</tex> называется '''ненасыщенной''' (англ. ''locally underconsistent''), что если все вершины насыщены, то мы можем найти расстояние от стартовой вершины до любой.<tex>g(s) < rhs(s)</tex>}}

Функция <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насыщенным)</tex>. <tex>k_2(s) = min(g(s), rhs(s))</tex>

[[Эвристики для поиска кратчайших путей|Эвристическая функция]] <tex>h(s,s')</tex> теперь должна быть неотрицательная и выполнять неравенство треугольника, т.е. <tex>h(t,t) = 0</tex> и <tex>h(s, t) \leqslant c(s,s') + h(s',t)</tex> для всех <tex>s \in V</tex> и <tex>s' \in Succ(s)</tex> {{Определение|definition=Будем называть '''ключом''' вершины такую функцию <tex>key(s)</tex>, которая возвращает вектор из 2-ух значений <tex>k_1(s)</tex>, <tex>k_2(s)</tex>. * <tex>k_1(s) = \min(g(s), rhs(s)) + h(s, 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> на текущей итерации. Но после следующего изменения графа путь вполне может найтись.

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

'''for ''' всех ориентированных ребер (u, v) с измененными весами: Обновляем результат функции c(u, v) updateVertex(v) Функция инициализации исходного графа устанавливает для всех вершин кроме стартовой вершины <tex>f</tex> значения <tex>g(s)</tex> и <tex>rhs(u; vs)</tex> равными бесконечности. Для стартовой <tex>rhs(f)=0</tex>. Очевидно, что минимальное расстояние от стартовой вершины до самой себя должно быть равным 0, но <tex>g(f)=+\infty</tex>. Это сделано для того, чтобы стартовая вершина была ненасыщенной и имела право попасть в приоритетную очередь. '''function''' 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.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))] Обновляет данные вершины в соответствие с измененными весамиданными выше определениями. Также поддерживает инвариант того, что в очереди U лежат только ненасыщенные вершины. '''function''' 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.remove(u) '''if''' g(u) <tex>\ne</tex> rhs(u) U.insert(u, calcKey(u)) Функция несколько раз перерасчитывает значение <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>cSucc(u) UpdateVertex(s) '''else''' g(u; v)= <tex>+\infty</tex>; '''UpdateVertexfor'''s <tex>\in</tex> Succ(u) <tex>\cup</tex> <tex>v\{u\}</tex> 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 \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))

'''Initializefunction'''ComputeShortestPath(): { //Заведем приоритетную очередь '''while''' U.topKey() < calcKey(f) or rhs(f) <tex>U\ne</tex>, в которую будем помещать вершиныg(f) u = U. Сортировка будет производиться по функции <texpop() '''if''' (g(u) >keyrhs(su))</tex>. <tex>U g(u) = \varnothing;</tex>rhs(u) '''for ''' s <tex>s \in S</tex>Pred(u) <tex>rhs updateVertex(s) = '''else''' g(su) = <tex>+\infty;</tex> '''for''' <tex>rhs(s_{start}) = 0;s</tex> U.Insert(<tex>s_{start}\in</tex>; CalcKeyPred(u) <tex>s_{start}\cup</tex>{u} updateVertex(s)); }

Функция '''function''' main(): initialize() computeShortestPath() '''while''' <tex>f \ne t</tex>key <font color="green">// '''if''' (g(sf)= <tex>+\infty</tex>) тогда путь на данной итерации не найден. Возвращаемые значения сортируются в лексографическом порядке</font> <tex>f</tex> = такая вершина s', т.е. сначала что <tex>k_1\min\limits_{s' \in Succ(f)}(c(f, s') + g(s'))</tex>, потом Передвинулись вдоль найденного пути и изменили вершину <tex>k_2(s)f</tex> Сканируем роботом какие-либо изменения в графе или убеждаемся, что граф остается прежним. '''if''CalcKey' граф изменился '''for'''всех ориентированных ребер <tex>(su, v)</tex> с измененными весами: { return [ Обновляем результат функции <tex>\minc(g(su, v); rhs</tex> updateVertex(su)) + h( '''for''' <tex>s; s_{goal})</tex>;<tex>\min(gin</tex> U U.update(s); rhs, CalcKey(s))</tex>]; } computeShortestPath()

'''UpdateVertex'''(<tex>u</tex>): { if (<tex>u \ne s_{start}</tex>) <tex>rhs(u) = min_{s' \in Pred(u)}(g(s') + c(s',u));</tex> if (<tex>u \in U</tex>) U.Remove(u); if (<tex>g(u) \ne rhs(u)</tex>) U.Insert(<tex>u</tex>; CalcKey(<tex>u</tex>)); }== Асимптотика ===

{{Теорема|author=Свен Кёниг|about=Об устойчивой насыщенности вершин|statement=Функция '''ComputeShortestPath'''в данной версии алгоритма ''расширяет'' вершину максимум 2 раза, а именно 1 раз, если вершина ненасыщена, и максимум 1 раз, если она переполнена.|proof=Доказательство [http://www.cs.cmu.edu/~maxim/files/aij04.pdf]}} == Алгоритм D* (Вторая версия):==  {=== Описание === while В первой версии алгоритма была серьезная проблема в том, что для каждой вершины в приоритетной очереди нужно было обновлять ключ суммарно за <tex>O(U.TopKeyn \cdot \log(n)) < CalcKey(/tex>. Это дорогая операция, так как очередь может содержать огромное число вершин. Воспользуемся оригинальным методом поиска и изменим основной цикл, чтобы избежать постоянного перестроения очереди <tex>s_{goal}U</tex>) OR rhs(. Теперь эвристическая функция должна поддерживать неравенство треугольника для всех вершин <tex>s_{goal}) s,s',s'' \ne g(s_{goal}in V</tex>)) u = U, т.е.Pop<tex>h(s,s''); if \leqslant h(gs, s') + h(us',s'') </tex> rhs. Так же должно выполняться свойство <tex>h(us,s')) g\leqslant c^*(us,s') = rhs</tex>, где <tex>c^*(us,s');</tex> - стоимость перехода по кратчайшему пути из <tex>s</tex> в <tex>s'</tex>, при этом <tex>s</tex> и <tex>s'</tex> не должны быть обязательно смежными. Такие свойства не противоречат свойствами из первой версии, а лишь усиливают их.  for Допустим, что после того, как робот продвинется вдоль найденного пути на предыдущих итерациях, из вершины <tex>s \in Succ</tex> в <tex>s'</tex>, он обнаружит изменения в графе. Первая компонента ключей <tex>k_1(us')</tex> UpdateVertexможет уменьшится максимум на <tex>h(s,s'); else g</tex> (uпо определению ключа) = . Вторая компонента не зависит от функции h. Аналогично первой версии алгоритма, мы должны уменьшить первую компоненту ключа у всех вершин в очереди U. Очевидно, что <tex>+\inftyh(s,s')</tex>; for будет одинаковым для всех вершин из U. Порядок в очереди не изменится, если произвести уменьшение. Следовательно уменьшение можно отложить, тем самым очередь не придется перестраивать на каждой итерации. Так же исходя из нового определения функции <tex>h</tex>, её значение будет всегда меньше, чем разность первых компонент ключей у соседних по приоритету вершин. Таким образом мы можем добавлять h(s,s \in Succ') ко всем <tex>k_1(us') \cup \{u\}</tex>у ключей вершин из U.  UpdateVertexБудем называть <tex>K_m</tex> ключевым модификатором. В нем мы и будет хранить сумму <tex>h(s,s');</tex>, которые нужно добавить ко всем вершинам из U. }=== Псевдокод ===

Таким образом мы описали алгоритм LPA*. Он неоднократно определяет путь между вершинами <tex>s_start</tex> и '''function''' calcKey(s): '''return''' [min(g(s), rhs(s)) + h(f, s) + <tex>s_goalK_m</tex>, используя при этом данные из предыдущих итераций. Очевидно, что в худшем случае min(g(а именно когда все ребра вокруг текущей вершины изменили свой весs) алгоритм будет работать как последовательные вызовы алгоритма А* за <tex>O(n^2*log, rhs(ns))</tex>. Улучшим эту оценку с помощью алгоритма D* lite.]

'''Примечаниеfunction'''initialize(): на практике же такой подход тоже имеет место на плотных графах U = <tex>\varnothing</tex> <tex>K_m = 0</tex> '''for''' s <tex>\in</tex> V rhs(s) = g(s) = <tex>+\infty</tex> rhs(или матрицахt)= 0 U.insert(t, так как в среднем дает оценку О(n*logCalcKey(nt)).

'''function''' updateVertex(u): '''if''' u <tex>\ne</tex> t rhs(u) == Алгоритм D* ==<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))

=== Псевдокод (Первая версия) === '''CalcKeyfunction'''computeShortestPath(s): return ['''while''' U.topKey() < calcKey(f) '''or''' rhs(f) <tex>\minne</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(su);> rhs(su)) g(u) + h= rhs(s_{start};u) '''for''' <tex>s)</tex>;<tex>\minin</tex> Pred(gu) updateVertex(s); rhs '''else''' g(u) = <tex>+\infty</tex> '''for''' <tex>s</tex> <tex>\in</tex> Pred(u))<tex>\cup</tex> <tex>\{u\}</tex>]; updateVertex(s)

'''Initializefunction'''main(): U = <tex>\varnothings_{last} = f</tex>; for initialize() computeShortestPath() '''while''' f <tex>s \in Sne</tex>t <texfont color="green">rhs// if (s) = g(sf) = <tex>+\infty</tex>) тогда путь на данной итерации не найден.</font> <tex>f</tex> = такая вершина s', что <tex>rhs\min\limits_{s' \in Succ(s_{goalf)}(c(f, s') + g(s')) = 0</tex> U Передвинулись вдоль найденного пути и изменили вершину <tex>f</tex>. Сканируем роботом какие-либо изменения в графе или убеждаемся, что граф остается прежним.Insert( '''if''' граф изменился <tex>K_m = K_m + h(s_{goallast}, h_{start})</tex>; CalcKey( <tex>s_{goallast}= f</tex> '''for''' всех ориентированных ребер (u, v)с измененными весами: Обновляем результат функции c(u, v) updateVertex(u) computeShortestPath();

'''UpdateVertex'''(u): if (<tex>u != s_{goal}</tex>) rhs(u) = min_{s' \in Succ(u)}(c(u,s')+g(s')); if (<tex>u \in U</tex>) U.Remove(u); if (<tex>g(u) != rhs(u)</tex>) U.Insert(u; CalcKey(u));Асимптотика ===

'''ComputeShortestPath'''() while (U.TopKey() С помощью введения ключевого модификатора <tex><=K_m</tex> CalcKey(<tex>s_{start}и отложенного обновления ключей вершин получилось убрать из итерации алгоритма </tex>) OR <tex>rhsO(s_{start}) != gn \cdot \log(s_{start}n)</tex>) u = U.Pop(); if (g(u) > rhs(u)) g(u) = rhs(u); for <tex>s \in Pred(u)</tex> UpdateVertex(s); else g(u) = операций, которые тратились на обновление очереди <tex>+\inftyU</tex>; for . Очевидно, что на основе теорем, приведенных выше, алгоритм использовал <tex>s \in PredO(u) 2 \cup cdot n \{ucdot \}log(n))</tex> UpdateVertex(s);операций. Итак, нам удалось уменьшить константу в 2 раза, что дает существенный рост производительности на практических задачах.

'''Main'''():=== Пример работы === Initialize();{| class="wikitable" ComputeShortestPath(); |- while (<tex>s_{start} \ne s_{goal}</tex>) // if (<tex>g(s_{start}) | style= \infty</tex>) тогда путь на данной итерации не найден"width:50%;text-align:center;" | [[Файл:Схема_движения_робота_Dstarv2_1. s_{start} png|400px]] || style= argmins02Succ(sstart) Move to <tex>s_{start}</tex>"width:50%; Scan graph for changed edge coststext-align:center;" | [[Файл:Схема_движения_робота_Dstarv2_2.png|400px]] if any edge costs changed |- for all directed edges (u | style="width:50%; v) with changed edge costs Update the edge cost c(utext-align:center; v)" | Итерации в функции '''ComputeShortestPath''' на исходном графе. || style="width:50%; UpdateVertex(u)text-align:center; for <tex>s \in U</tex> U" | Итерации в функции '''ComputeShortestPath''' после изменения графа.Update(<tex>s</tex>; CalcKey(<tex>s</tex>)Второй вызов функции); ComputeShortestPath();|}

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

* [http://www.cs.cmu.edu/~maxim/files/aij04.pdf LPA*]* [http://pub1.willowgarage.com/~konolige/cs225b/dlite_tro05.pdfD* lite]