Алгоритм D* — различия между версиями

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

Текущая версия на 17:54, 16 сентября 2015

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

Алгоритм LPA*

Постановка задачи

Дан взвешенный ориентированный граф [math] G(V, E) [/math]. Даны вершины: стартовая вершина [math]f[/math] и конечная вершина [math]t[/math]. Требуется после каждого изменения графа [math]G[/math] уметь вычислять функцию [math]g(s)[/math] для каждой известной вершины [math]s \in V[/math]

Описание

Функция [math]g(s)[/math] будет возвращать наименьшую стоимость пути из вершины [math]f[/math] в [math]s[/math]. Её значение для алгоритма будет почти аналогичным значению в алгоритме A*, за исключением того, что в данном алгоритме наc интересуют только [math]g(s)[/math]-значения известных вершин на данной итерации.

Будем поддерживать для каждой вершины два вида смежных с ней вершин:

  • Обозначим множество [math]Succ(s) \subseteq V[/math] как множество вершин, исходящих из вершины [math]s[/math].
  • Обозначим множество [math]Pred(s) \subseteq V[/math] как множество вершин, входящих в вершину [math]s[/math].

Функция [math]0 \leqslant c(s, s') \leqslant +\infty[/math] будет возвращать стоимость ребра [math](s, s')[/math]. При этом [math]c(s, s') = +\infty[/math] будет тогда и только тогда, когда ребра [math](s, s')[/math] не существует.


Определение:
Будем называть rhs-значением (англ. right-hand side value) такую функцию [math]rhs(s)[/math], которая будет возвращать потенциальное минимальное расстояние от [math]f[/math] до [math]s[/math] по следующим правилам:

[math]rhs(s) = \begin{cases} 0,& \text{if } s = f \\ \min\limits_{s' \in Pred(s)}(g(s') + c(s', s),& \text{otherwise} \end{cases} [/math]

Так как rhs-значение использует минимальное значение из минимальных расстояний от [math]f[/math] до вершин, входящих в данную вершину [math]s[/math], это будет нам давать информацию об оценочном расстоянии от [math]f[/math] до [math]s[/math].


Определение:
Вершина [math]s[/math] называется насыщенной (англ. locally consistent), если [math]g(s) = rhs(s)[/math]


Определение:
Вершина [math]s[/math] называется переполненной (англ. locally overconsistent), если [math]g(s) \gt rhs(s)[/math]


Определение:
Вершина [math]s[/math] называется ненасыщенной (англ. locally underconsistent), если [math]g(s) \lt rhs(s)[/math]


Очевидно, что если все вершины насыщены, то мы можем найти расстояние от стартовой вершины до любой. Такой граф будем называть устойчивым (насыщенным).

Эвристическая функция [math]h(s,s')[/math] теперь должна быть неотрицательная и выполнять неравенство треугольника, т.е. [math]h(t,t) = 0[/math] и [math]h(s, t) \leqslant c(s,s') + h(s',t)[/math] для всех [math]s \in V[/math] и [math]s' \in Succ(s)[/math]


Определение:
Будем называть ключом вершины такую функцию [math]key(s)[/math], которая возвращает вектор из 2-ух значений [math]k_1(s)[/math], [math]k_2(s)[/math].
  • [math]k_1(s) = \min(g(s), rhs(s)) + h(s, t)[/math]
  • [math]k_2(s) = \min(g(s), rhs(s))[/math],
где [math]s[/math] - вершина из множества [math]V[/math]

Если в конце поиска пути [math]g(t) = +\infty[/math], то мы не смогли найти путь от [math]f[/math] до [math]t[/math] на текущей итерации. Но после следующего изменения графа путь вполне может найтись.

Псевдокод

Основная функция, описывающая алгоритм

 function main():
   initialize()
   while true
     computeShortestPath()
     // В данный момент мы знаем кратчайший путь из f в t.
     Ждем каких-либо изменений графа.
     for всех ориентированных ребер (u, v) с измененными весами:
       Обновляем результат функции c(u, v)
       updateVertex(v)

Функция инициализации исходного графа устанавливает для всех вершин кроме стартовой вершины [math]f[/math] значения [math]g(s)[/math] и [math]rhs(s)[/math] равными бесконечности. Для стартовой [math]rhs(f)=0[/math]. Очевидно, что минимальное расстояние от стартовой вершины до самой себя должно быть равным 0, но [math]g(f)=+\infty[/math]. Это сделано для того, чтобы стартовая вершина была ненасыщенной и имела право попасть в приоритетную очередь.

 function initialize():
   // Заведем приоритетную очередь U, в которую будем помещать вершины.
   // Сортировка будет производиться по функции key(s).
   U = [math]\varnothing[/math]
   for s [math]\in[/math] V
     rhs(s) = g(s) = [math]+\infty[/math]
   rhs(f) = 0
   U.insert(f, calcKey(f))

Функция [math]key(s)[/math]. Возвращаемые значения сортируются в лексографическом порядке, то есть сначала сортируется по [math]k_1(s)[/math], потом по [math]k_2(s)[/math]

 function calcKey(s):
   return [min(g(s), rhs(s)) + h(s, t), min(g(s), rhs(s))]

Обновляет данные вершины в соответствие с данными выше определениями. Также поддерживает инвариант того, что в очереди U лежат только ненасыщенные вершины.

 function updateVertex(u):
   if u [math]\ne[/math] f
     [math]rhs(u) = \min\limits_{s' \in Pred(u)}(g(s') + c(s',u))[/math]
   if u [math]\in[/math] U
     U.remove(u)
   if g(u) [math]\ne[/math] rhs(u)
     U.insert(u, calcKey(u))

Функция несколько раз перерасчитывает значение [math]g(s)[/math] у ненасыщенных вершин в неубывающем порядке их ключей. Такой перерасчет значения [math]g(s)[/math] будем называть расширением вершины.

 function computeShortestPath():
   while U.topKey() < calcKey(t) or rhs(t) [math]\ne[/math] g(t)
     u = U.pop()
     if g(u) > rhs(u)
       g(u) = rhs(u)
       for [math]s[/math] [math]\in[/math] Succ(u)
         UpdateVertex(s)
     else
       g(u) = [math]+\infty[/math]
       for s [math]\in[/math] Succ(u) [math]\cup[/math] [math]\{u\}[/math]
         updateVertex(s)

Асимптотика

Теорема (О монотонности изменения ключей):
В течение выполнения функции ComputeShortestPath вершины, взятые из очереди, монотонно не убывают.
Доказательство:
[math]\triangleright[/math]
Доказательство [1]
[math]\triangleleft[/math]
Теорема (О необратимой насыщенности):
Если в функции ComputeShortestPath была взята переполненная вершина, то на следующей итерации она станет насыщенной.
Доказательство:
[math]\triangleright[/math]
Доказательство [2]
[math]\triangleleft[/math]
Теорема:
После выполнения функции ComputeShortestPath можно восстановить путь из [math]f[/math] в [math]t[/math]. Для этого, начиная с вершины [math]t[/math], нужно постоянно передвигаться к такой вершине [math]s'[/math], входящей в [math]t[/math], чтобы [math]g(s') + c(s',s)[/math] было минимальным, до тех пора, пока не будет достигнута вершина [math]f[/math].
Доказательство:
[math]\triangleright[/math]
Доказательство [3]
[math]\triangleleft[/math]

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

Примечание: на практике же такой подход тоже имеет место на плотных графах (или матрицах), так как в среднем дает оценку [math]O(n \cdot \log(n))[/math].

Алгоритм D* (Первая версия)

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

Постановка задачи

Дан взвешенный ориентированный граф [math] G(V, E) [/math]. Даны вершины [math]f[/math] и [math]t[/math]. Требуется в процессе движения по кратчайшему пути в графе [math]G[/math] обновлять значения функции [math]g(s)[/math] при поступлении новой информации о графе [math]G[/math].

Теперь на основе LPA* опишем алгоритм D*, который способен определять расстояние между текущей вершиной [math]f[/math], в которой, допустим, находится способный к сканированию местности "робот", и конечной вершиной [math]t[/math] при каждом изменении графа в то время, как наш "робот" движется вдоль найденного пути.

Схема движения "робота" в процессе работы алгоритма D*. Информация о серых клетках ему неизвестна до тех пор, пока они не попадут в его зону обзора. В данном примере зона обзора составляет 1 клетку в 8-ми направлениях.

Описание

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

Примечание: Большинство функций переходят в данный алгоритм без изменений, поэтому опишем только измененные части.

Для начала мы поменяем направление поиска в графе.

Теперь функция g(s) хранит минимальное известное расстояние от [math]t[/math] до [math]s[/math]. Свойства остаются прежними.

Эвристическая функция [math]h(s,s')[/math] теперь должна быть неотрицательная и обратно-устойчивая, т.е. [math]h(f,f) = 0[/math] и [math]h(f, s) \leqslant h(f,s') + c(s',s)[/math] для всех [math]s \in S[/math] и [math]s' \in Pred(s)[/math]. Очевидно, что при движении робота [math]f[/math] изменяется, поэтому данные свойства должны выполняться для всех [math]f \in V[/math].

Дополнительное условие выхода также меняется, т.е. при [math]g(f) = +\infty[/math] путь не найден на данной итерации. Иначе путь найден и "робот" может проследовать по нему.

Примечание: Так же следует отметить, что функция Initialize не обязана инициализировать абсолютно все вершины перед стартом алгоритма. Это важно, так как на практике число вершин может быть огромным, и только немногие будут пройдены роботом в процессе движения. Так же это дает возможность добавления/удаления ребер без потери устойчивости всех подграфов данного графа.

Псевдокод

При такой постановке задачи псевдокод не сильно меняется, но функция Main все-таки претерпевает значительные изменения.

 function calcKey(s):
   return [min(g(s), rhs(s)) + h(f,s), min(g(s), rhs(s))]
 function initialize():
   U = [math]\varnothing[/math]
   for s [math]\in[/math] V
     rhs(s) = g(s) = [math]+\infty[/math]
   rhs(t) = 0
   U.insert(t, calcKey(t))
 function UpdateVertex(u):
   if u [math]\ne[/math] t 
     rhs(u) = [math]\min\limits_{s' \in Succ(u)}(c(u,s')+g(s'))[/math]
   if u [math]\in[/math] U 
     U.remove(u)
   if g(u) [math]\ne[/math] rhs(u)
     U.insert(u, calcKey(u))
 function ComputeShortestPath():
   while U.topKey() < calcKey(f) or rhs(f) [math]\ne[/math] g(f)
     u = U.pop()
     if (g(u) > rhs(u))
       g(u) = rhs(u)
       for s [math]\in[/math] Pred(u)
         updateVertex(s)
     else
       g(u) = [math]+\infty[/math]
       for [math]s[/math] [math]\in[/math] Pred(u) [math]\cup[/math] {u}
         updateVertex(s)
 function main():
   initialize()
   computeShortestPath()
   while [math]f \ne t[/math]
     // if (g(f) = [math]+\infty[/math]) тогда путь на данной итерации не найден.
     
     [math]f[/math] = такая вершина s', что [math]\min\limits_{s' \in Succ(f)}(c(f, s') + g(s'))[/math]
     
     Передвинулись вдоль найденного пути и изменили вершину [math]f[/math]
     Сканируем роботом какие-либо изменения в графе или убеждаемся, что граф остается прежним.
     if граф изменился
       for всех ориентированных ребер [math](u, v)[/math] с измененными весами:
         Обновляем результат функции [math]c(u, v)[/math]
         updateVertex(u)
       for [math]s[/math] [math]\in[/math] U
         U.update(s, CalcKey(s))
       computeShortestPath()

Асимптотика

Теорема (Свен Кёниг, Об устойчивой насыщенности вершин):
Функция ComputeShortestPath в данной версии алгоритма расширяет вершину максимум 2 раза, а именно 1 раз, если вершина ненасыщена, и максимум 1 раз, если она переполнена.
Доказательство:
[math]\triangleright[/math]
Доказательство [4]
[math]\triangleleft[/math]

Алгоритм D* (Вторая версия)

Описание

В первой версии алгоритма была серьезная проблема в том, что для каждой вершины в приоритетной очереди нужно было обновлять ключ суммарно за [math]O(n \cdot \log(n))[/math]. Это дорогая операция, так как очередь может содержать огромное число вершин. Воспользуемся оригинальным методом поиска и изменим основной цикл, чтобы избежать постоянного перестроения очереди [math]U[/math].

Теперь эвристическая функция должна поддерживать неравенство треугольника для всех вершин [math]s,s',s'' \in V[/math], т.е. [math]h(s,s'') \leqslant h(s, s') + h(s',s'')[/math]. Так же должно выполняться свойство [math]h(s,s') \leqslant c^*(s,s')[/math], где [math]c^*(s,s')[/math] - стоимость перехода по кратчайшему пути из [math]s[/math] в [math]s'[/math], при этом [math]s[/math] и [math]s'[/math] не должны быть обязательно смежными. Такие свойства не противоречат свойствами из первой версии, а лишь усиливают их.

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

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

Псевдокод

 function calcKey(s):
   return [min(g(s), rhs(s)) + h(f, s) + [math]K_m[/math], min(g(s), rhs(s))]
 function initialize():
   U = [math]\varnothing[/math]
   [math]K_m = 0[/math]
   for s [math]\in[/math] V
     rhs(s) = g(s) = [math]+\infty[/math]
   rhs(t) = 0
   U.insert(t, CalcKey(t))
 function updateVertex(u):
   if u [math]\ne[/math] t 
     rhs(u) = [math]\min\limits_{s' \in Succ(u)}(c(u,s')+g(s'))[/math]
   if u [math]\in[/math] U 
     U.remove(u)
   if g(u) [math]\ne[/math] rhs(u)
     U.insert(u, calcKey(u))
 function computeShortestPath():
   while U.topKey() < calcKey(f) or rhs(f) [math]\ne[/math] g(f)
     [math]K_{old}[/math] = U.topKey()
     u = U.pop()
     
     if [math]K_{old}[/math] < calcKey(u)
       U.insert(u, calcKey(u))
     
     if (g(u) > rhs(u))
       g(u) = rhs(u)
       for [math]s[/math] [math]\in[/math] Pred(u) 
         updateVertex(s)
     else
       g(u) = [math]+\infty[/math]
       for [math]s[/math] [math]\in[/math] Pred(u) [math]\cup[/math] [math]\{u\}[/math] 
         updateVertex(s)
 function main():
   [math]s_{last} = f[/math]
   initialize()
   computeShortestPath()
   while f [math]\ne[/math] t
     // if (g(f) = [math]+\infty[/math]) тогда путь на данной итерации не найден.
     [math]f[/math] = такая вершина s', что [math]\min\limits_{s' \in Succ(f)}(c(f, s') + g(s'))[/math]
     Передвинулись вдоль найденного пути и изменили вершину [math]f[/math].
     Сканируем роботом какие-либо изменения в графе или убеждаемся, что граф остается прежним.
     if граф изменился
       [math]K_m = K_m + h(s_{last}, h_{start})[/math]
       [math]s_{last} = f[/math]
       for всех ориентированных ребер (u, v) с измененными весами:
         Обновляем результат функции c(u, v)
         updateVertex(u)
       computeShortestPath()

Асимптотика

С помощью введения ключевого модификатора [math]K_m[/math] и отложенного обновления ключей вершин получилось убрать из итерации алгоритма [math]O(n \cdot \log(n))[/math] операций, которые тратились на обновление очереди [math]U[/math]. Очевидно, что на основе теорем, приведенных выше, алгоритм использовал [math]O(2 \cdot n \cdot \log(n))[/math] операций. Итак, нам удалось уменьшить константу в 2 раза, что дает существенный рост производительности на практических задачах.

Пример работы

Схема движения робота Dstarv2 1.png Схема движения робота Dstarv2 2.png
Итерации в функции ComputeShortestPath на исходном графе. Итерации в функции ComputeShortestPath после изменения графа. (Второй вызов функции)

Источники информации