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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (Ссылки)
 
(не показано 17 промежуточных версий 2 участников)
Строка 4: Строка 4:
  
 
=== Постановка задачи ===
 
=== Постановка задачи ===
Дан [[Основные определения теории графов|взвешенный ориентированный граф]] <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(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>f</tex> до <tex>s</tex>. Её значение будет почти аналогичным значению в [[Алгоритм A* | алгоритме A*]], за исключением того, что в данном алгоритме наc интересуют только <tex>g(s)</tex>-значения известных вершин на данной итерации.
+
Функция <tex>g(s)</tex> будет возвращать наименьшую стоимость пути из вершины <tex>f</tex> в <tex>s</tex>. Её значение для алгоритма будет почти аналогичным значению в [[Алгоритм A* | алгоритме A*]], за исключением того, что в данном алгоритме наc интересуют только <tex>g(s)</tex>-значения известных вершин на данной итерации.
  
 
Будем поддерживать для каждой вершины два вида смежных с ней вершин:
 
Будем поддерживать для каждой вершины два вида смежных с ней вершин:
Строка 13: Строка 13:
 
* Обозначим множество <tex>Pred(s) \subseteq V</tex> как множество вершин, входящих в вершину <tex>s</tex>.
 
* Обозначим множество <tex>Pred(s) \subseteq V</tex> как множество вершин, входящих в вершину <tex>s</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> не существует.
  
 
{{Определение
 
{{Определение
|definition=Будем называть '''rhs-значением''' (''right-hand side value'') такую функцию <tex>rhs(s)</tex>, которая будет возвращать потенциальное минимальное расстояние от <tex>f</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}
Строка 27: Строка 27:
  
 
{{Определение
 
{{Определение
|definition=Вершина <tex>s</tex> называется '''насыщенной''' (''locally consistent''), если <tex>g(s) = rhs(s)</tex>
+
|definition=Вершина <tex>s</tex> называется '''насыщенной''' (англ. ''locally consistent''), если <tex>g(s) = rhs(s)</tex>
 
}}
 
}}
  
 
{{Определение
 
{{Определение
|definition=Вершина <tex>s</tex> называется '''переполненной''' (''locally overconsistent''), если <tex>g(s) > rhs(s)</tex>
+
|definition=Вершина <tex>s</tex> называется '''переполненной''' (англ. ''locally overconsistent''), если <tex>g(s) > rhs(s)</tex>
 
}}
 
}}
  
 
{{Определение
 
{{Определение
|definition=Вершина <tex>s</tex> называется '''ненасыщенной''' (''locally underconsistent''), если <tex>g(s) < rhs(s)</tex>
+
|definition=Вершина <tex>s</tex> называется '''ненасыщенной''' (англ. ''locally underconsistent''), если <tex>g(s) < rhs(s)</tex>
 
}}
 
}}
  
Строка 54: Строка 54:
  
 
Основная функция, описывающая алгоритм
 
Основная функция, описывающая алгоритм
   '''Main'''():
+
   '''function''' main():
     '''Initialize'''();
+
     initialize()
     while (true)
+
     '''while''' ''true''
      '''ComputeShortestPath'''();
+
      computeShortestPath()
       //В данный момент мы знаем кратчайший путь из f в t.
+
       <font color="green">// В данный момент мы знаем кратчайший путь из f в t.</font>
 
       Ждем каких-либо изменений графа.
 
       Ждем каких-либо изменений графа.
       for всех ориентированных ребер (u; v) с измененными весами:
+
       '''for''' всех ориентированных ребер (u, v) с измененными весами:
         Обновляем результат функции c(u; v);
+
         Обновляем результат функции c(u, v)
         '''UpdateVertex'''(v);
+
         updateVertex(v)
  
Теперь опишем составные элементы подробнее
+
Функция инициализации исходного графа устанавливает для всех вершин кроме стартовой вершины <tex>f</tex> значения <tex>g(s)</tex> и <tex>rhs(s)</tex> равными бесконечности. Для стартовой <tex>rhs(f)=0</tex>. Очевидно, что минимальное расстояние от стартовой вершины до самой себя должно быть равным 0, но <tex>g(f)=+\infty</tex>. Это сделано для того, чтобы стартовая вершина была ненасыщенной и имела право попасть в приоритетную очередь.
Функция инициализации исходного графа устанавливает для всех вершин кроме стартовой (<tex>f</tex>) значения <tex>g(s)</tex> и <tex>rhs(s)</tex> равными бесконечности. Для стартовой <tex>rhs(f)=0</tex>. Очевидно, что минимальное расстояние от стартовой вершины до самой себя должно быть равным 0, но <tex>g(f)=+\infty</tex>. Это сделано для того, чтобы стартовая вершина была ненасыщенной и имела право попасть в приоритетную очередь.
+
   '''function''' initialize():
   '''Initialize'''():
+
     <font color="green">// Заведем [[Двоичная куча|приоритетную очередь]] U, в которую будем помещать вершины.</font>
     //Заведем [[Двоичная куча|приоритетную очередь]] U, в которую будем помещать вершины. Сортировка будет производиться по функции key(s).
+
    <font color="green">// Сортировка будет производиться по функции key(s).</font>
     U = <tex>\varnothing</tex>;
+
     U = <tex>\varnothing</tex>
     for s <tex>\in</tex> V
+
     '''for''' s <tex>\in</tex> V
       rhs(s) = g(s) = <tex>\infty;</tex>
+
       rhs(s) = g(s) = <tex>+\infty</tex>
     rhs(f) = 0;
+
     rhs(f) = 0
     U.Insert(f; CalcKey(f));
+
     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>key(s)</tex>. Возвращаемые значения сортируются в лексографическом порядке, т.е. сначала <tex>k_1(s)</tex>, потом <tex>k_2(s)</tex>
+
Обновляет данные вершины в соответствие с данными выше определениями. Также поддерживает инвариант того, что в очереди U лежат только ненасыщенные вершины.
  '''CalcKey'''(s):
+
   '''function''' updateVertex(u):
    return [min(g(s); rhs(s)) + h(s; t); min(g(s); rhs(s))];
+
    '''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))
  
   '''UpdateVertex'''(u):
+
Функция несколько раз перерасчитывает значение <tex>g(s)</tex> у ненасыщенных вершин в неубывающем порядке их ключей. Такой перерасчет значения <tex>g(s)</tex> будем называть ''расширением'' вершины.
     if u <tex>\ne</tex> f
+
   '''function''' computeShortestPath():
       <tex>rhs(u) = \min\limits_{s' \in Pred(u)}(g(s') + c(s',u));</tex>
+
     '''while''' U.topKey() < calcKey(t) '''or''' rhs(t) <tex>\ne</tex> g(t)
    if u <tex>\in</tex> U
+
       u = U.pop()
      U.Remove(u);
+
      '''if''' g(u) > rhs(u)
    if g(u) <tex>\ne</tex> rhs(u)
+
        g(u) = rhs(u)
      U.Insert(u; CalcKey(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)
  
  // Функция несколько раз перерасчитывает значение <tex>g(s)</tex> у ненасыщенных вершин в неубывающем порядке их ключей. Такой перерасчет значения <tex>g(s)</tex> будем называть ''расширением'' вершины.
+
=== Асимптотика ===
  '''ComputeShortestPath'''():
 
    while (U.TopKey() < CalcKey(t) OR rhs(t) <tex>\ne</tex> g(t))
 
      u = U.Pop();
 
      if g(u) > rhs(u)
 
        g(u) = rhs(u);
 
        for s <tex>\in</tex> Succ(u)
 
          UpdateVertex(s);
 
      else
 
        g(u) = <tex>+\infty</tex>;
 
        for s <tex>\in</tex> Succ(u) <tex>\cup</tex> {u}
 
          UpdateVertex(s);
 
  
Таким образом мы описали алгоритм LPA*. Он неоднократно определяет путь между вершинами <tex>f</tex> и <tex>t</tex>, используя при этом данные из предыдущих итераций. Очевидно, что в худшем случае (а именно когда все ребра вокруг текущей вершины изменили свой вес) алгоритм будет работать как последовательные вызовы алгоритма А* за <tex>O(n^2 \cdot \log(n))</tex>. Улучшим эту оценку с помощью алгоритма D* lite.
+
{{Теорема
 +
|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>.
 
'''Примечание''': на практике же такой подход тоже имеет место на плотных графах (или матрицах), так как в среднем дает оценку <tex>O(n \cdot \log(n))</tex>.
  
 
== Алгоритм D* (Первая версия) ==
 
== Алгоритм D* (Первая версия) ==
Пока что был описан только алгоритм LPA*. Он способен неоднократно определять кратчайшее расстояние между начальной и конечной вершинами при любом изменении данного графа. Его первоначальный поиск полностью совпадает с алгоритмом A*, но последующие итерации способны использовать информацию из предыдущих поисков.
+
Пока что был описан только алгоритм LPA*. Он находит кратчайшее расстояние между начальной и конечной вершинами при любом изменении данного графа. Его первоначальный поиск полностью совпадает с алгоритмом A*, но последующие итерации способны использовать информацию из предыдущих поисков.
  
 
=== Постановка задачи ===
 
=== Постановка задачи ===
Строка 112: Строка 131:
 
Теперь на основе LPA* опишем алгоритм D*, который способен определять расстояние между текущей вершиной <tex>f</tex>, в которой, допустим, находится способный к сканированию местности "робот", и конечной вершиной <tex>t</tex> при каждом изменении графа в то время, как наш "робот" движется вдоль найденного пути.
 
Теперь на основе LPA* опишем алгоритм D*, который способен определять расстояние между текущей вершиной <tex>f</tex>, в которой, допустим, находится способный к сканированию местности "робот", и конечной вершиной <tex>t</tex> при каждом изменении графа в то время, как наш "робот" движется вдоль найденного пути.
  
[[Файл:Схема_движения_робота_Dstar.png|350px|thumb|right|Схема движения "робота" в процессе работы алгоритма D*. Информация о серых клетках ему неизвестна до определенной итерации.]]
+
[[Файл:Схема_движения_робота_Dstar.png|350px|thumb|right|Схема движения "робота" в процессе работы алгоритма D*. Информация о серых клетках ему неизвестна до тех пор, пока они не попадут в его зону обзора. В данном примере зона обзора составляет 1 клетку в 8-ми направлениях.]]
  
 
=== Описание ===
 
=== Описание ===
Опишем первую версию алгоритма D*. Очевидно, что большинство вершин в процессе движения робота остаются неизменными, поэтому мы можем применить алгоритм LPA*.  
+
Опишем первую версию алгоритма D*. Так как при движении по кратчайшему пути путь может только сокращаться и происходит изменение только стартовой вершины, то можно применить идею из алгоритма LPA*.
  
 
'''Примечание''': Большинство функций переходят в данный алгоритм без изменений, поэтому опишем только измененные части.
 
'''Примечание''': Большинство функций переходят в данный алгоритм без изменений, поэтому опишем только измененные части.
Строка 133: Строка 152:
 
При такой постановке задачи псевдокод не сильно меняется, но функция '''Main''' все-таки претерпевает значительные изменения.
 
При такой постановке задачи псевдокод не сильно меняется, но функция '''Main''' все-таки претерпевает значительные изменения.
  
   '''CalcKey'''(s):
+
   '''function''' calcKey(s):
     return [<tex>\min(g(s);rhs(s)) + h(f;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(t) = 0</tex>
+
     rhs(t) = 0
     U.Insert(<tex>t</tex>; CalcKey(<tex>t</tex>));
+
     U.insert(t, calcKey(t))
  
   '''UpdateVertex'''(u):
+
   '''function''' UpdateVertex(u):
     if (<tex>u \ne t</tex>)
+
     '''if''' u <tex>\ne</tex> t
       rhs(u) = <tex>\min\limits_{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>f</tex>) OR <tex>rhs(f) \ne g(f)</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>f \ne t</tex>)
+
     '''while''' <tex>f \ne t</tex>
       // if (<tex>g(f) = \infty</tex>) тогда путь на данной итерации не найден.
+
       <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> = такая вершина s', что <tex>\min\limits_{s' \in Succ(f)}(c(f, s') + g(s'))</tex>
       Передвинулись вдоль найденного пути и изменили вершину <tex>f</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()
 +
 
 +
=== Асимптотика ===
  
 
{{Теорема
 
{{Теорема
Строка 183: Строка 206:
 
|about=Об устойчивой насыщенности вершин
 
|about=Об устойчивой насыщенности вершин
 
|statement=Функция '''ComputeShortestPath''' в данной версии алгоритма ''расширяет'' вершину максимум 2 раза, а именно 1 раз, если вершина ненасыщена, и максимум 1 раз, если она переполнена.
 
|statement=Функция '''ComputeShortestPath''' в данной версии алгоритма ''расширяет'' вершину максимум 2 раза, а именно 1 раз, если вершина ненасыщена, и максимум 1 раз, если она переполнена.
 +
|proof=Доказательство [http://www.cs.cmu.edu/~maxim/files/aij04.pdf]
 
}}
 
}}
  
Строка 191: Строка 215:
  
 
Теперь эвристическая функция должна поддерживать неравенство треугольника для всех вершин <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(f;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(t) = 0</tex>
+
     rhs(t) = 0
     U.Insert(<tex>t</tex>; CalcKey(<tex>t</tex>));
+
     U.insert(t, CalcKey(t))
  
   '''UpdateVertex'''(u):
+
   '''function''' updateVertex(u):
     if (<tex>u \ne t</tex>)
+
     '''if''' u <tex>\ne</tex> t
       rhs(u) = <tex>\min\limits_{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>f</tex>) OR <tex>rhs(f) \ne g(f)</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} = f</tex>
 
     <tex>s_{last} = f</tex>
     '''Initialize'''();
+
     initialize()
     '''ComputeShortestPath'''();
+
    computeShortestPath()
    while (<tex>f \ne t</tex>)
+
     '''while''' f <tex>\ne</tex> t
       // if (<tex>g(f) = \infty</tex>) тогда путь на данной итерации не найден.
+
       <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> = такая вершина s', что <tex>\min\limits_{s' \in Succ(f)}(c(f, s') + g(s'))</tex>
       Передвинулись вдоль найденного пути и изменили вершину <tex>f</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} = f</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 раза, что дает существенный рост производительности на практических задачах.
  
 
=== Пример работы ===
 
=== Пример работы ===
Строка 255: Строка 287:
 
|}
 
|}
  
==Ссылки==
+
==Источники информации==
 
* [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 после изменения графа. (Второй вызов функции)

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