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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 16: Строка 16:
  
 
{{Определение
 
{{Определение
|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()
 
       <font color="green">// В данный момент мы знаем кратчайший путь из f в t.</font>
 
       <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>. Это сделано для того, чтобы стартовая вершина была ненасыщенной и имела право попасть в приоритетную очередь.
   Initialize():
+
   '''function''' initialize():
 
     <font color="green">// Заведем [[Двоичная куча|приоритетную очередь]] U, в которую будем помещать вершины.</font>
 
     <font color="green">// Заведем [[Двоичная куча|приоритетную очередь]] U, в которую будем помещать вершины.</font>
 
     <font color="green">// Сортировка будет производиться по функции key(s).</font>
 
     <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>
 
Функция <tex>key(s)</tex>. Возвращаемые значения сортируются в лексографическом порядке, то есть сначала сортируется по <tex>k_1(s)</tex>, потом по <tex>k_2(s)</tex>
   CalcKey(s):
+
   '''function''' calcKey(s):
 
     '''return''' [min(g(s), rhs(s)) + h(s, t), min(g(s), rhs(s))]
 
     '''return''' [min(g(s), rhs(s)) + h(s, t), min(g(s), rhs(s))]
  
 
Обновляет данные вершины в соответствие с данными выше определениями. Также поддерживает инвариант того, что в очереди U лежат только ненасыщенные вершины.
 
Обновляет данные вершины в соответствие с данными выше определениями. Также поддерживает инвариант того, что в очереди U лежат только ненасыщенные вершины.
   UpdateVertex(u):
+
   '''function''' updateVertex(u):
 
     '''if''' u <tex>\ne</tex> f
 
     '''if''' u <tex>\ne</tex> f
 
       <tex>rhs(u) = \min\limits_{s' \in Pred(u)}(g(s') + c(s',u))</tex>
 
       <tex>rhs(u) = \min\limits_{s' \in Pred(u)}(g(s') + c(s',u))</tex>
 
     '''if''' u <tex>\in</tex> U
 
     '''if''' u <tex>\in</tex> U
       U.Remove(u)
+
       U.remove(u)
 
     '''if''' g(u) <tex>\ne</tex> rhs(u)
 
     '''if''' g(u) <tex>\ne</tex> rhs(u)
       U.Insert(u, CalcKey(u))
+
       U.insert(u, calcKey(u))
  
 
Функция несколько раз перерасчитывает значение <tex>g(s)</tex> у ненасыщенных вершин в неубывающем порядке их ключей. Такой перерасчет значения <tex>g(s)</tex> будем называть ''расширением'' вершины.
 
Функция несколько раз перерасчитывает значение <tex>g(s)</tex> у ненасыщенных вершин в неубывающем порядке их ключей. Такой перерасчет значения <tex>g(s)</tex> будем называть ''расширением'' вершины.
   ComputeShortestPath():
+
   '''function''' computeShortestPath():
     '''while''' U.TopKey() < CalcKey(t) or rhs(t) <tex>\ne</tex> g(t)
+
     '''while''' U.topKey() < calcKey(t) '''or''' rhs(t) <tex>\ne</tex> g(t)
       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''' s <tex>\in</tex> Succ(u)
+
         '''for''' <tex>s</tex> <tex>\in</tex> Succ(u)
 
           UpdateVertex(s)
 
           UpdateVertex(s)
 
       '''else'''
 
       '''else'''
 
         g(u) = <tex>+\infty</tex>
 
         g(u) = <tex>+\infty</tex>
         '''for''' s <tex>\in</tex> Succ(u) <tex>\cup</tex> {u}
+
         '''for''' s <tex>\in</tex> Succ(u) <tex>\cup</tex> <tex>\{u\}</tex>
           UpdateVertex(s)
+
           updateVertex(s)
  
 
=== Асимптотика ===
 
=== Асимптотика ===
Строка 152: Строка 152:
 
При такой постановке задачи псевдокод не сильно меняется, но функция '''Main''' все-таки претерпевает значительные изменения.
 
При такой постановке задачи псевдокод не сильно меняется, но функция '''Main''' все-таки претерпевает значительные изменения.
  
   CalcKey(s):
+
   '''function''' calcKey(s):
 
     '''return''' [min(g(s), rhs(s)) + h(f,s), min(g(s), rhs(s))]
 
     '''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''' 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(t) = 0
 
     rhs(t) = 0
     U.Insert(t, CalcKey(t))
+
     U.insert(t, calcKey(t))
  
   UpdateVertex(u):
+
   '''function''' UpdateVertex(u):
 
     '''if''' u <tex>\ne</tex> t  
 
     '''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''' u <tex>\in</tex> U  
 
     '''if''' u <tex>\in</tex> U  
       U.Remove(u)
+
       U.remove(u)
 
     '''if''' g(u) <tex>\ne</tex> rhs(u)
 
     '''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(f) or rhs(f) <tex>\ne</tex> g(f)
+
     '''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''' s <tex>\in</tex> Pred(u)
 
         '''for''' s <tex>\in</tex> Pred(u)
           UpdateVertex(s)
+
           updateVertex(s)
 
       '''else'''
 
       '''else'''
 
         g(u) = <tex>+\infty</tex>
 
         g(u) = <tex>+\infty</tex>
         '''for''' s <tex>\in</tex> Pred(u) <tex>\cup</tex> {u}
+
         '''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>
 
       <font color="green">// '''if''' (g(f) = <tex>+\infty</tex>) тогда путь на данной итерации не найден.</font>
 
       <font color="green">// '''if''' (g(f) = <tex>+\infty</tex>) тогда путь на данной итерации не найден.</font>
Строка 195: Строка 195:
 
         '''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''' s <tex>\in</tex> U
+
         '''for''' <tex>s</tex> <tex>\in</tex> U
           U.Update(s, '''CalcKey'''(s))
+
           U.update(s, CalcKey(s))
         '''ComputeShortestPath'''()
+
         computeShortestPath()
  
 
=== Асимптотика ===
 
=== Асимптотика ===
Строка 222: Строка 222:
 
=== Псевдокод ===
 
=== Псевдокод ===
  
   CalcKey(s):
+
   '''function''' calcKey(s):
 
     '''return''' [min(g(s), rhs(s)) + h(f, s) + <tex>K_m</tex>, min(g(s), rhs(s))]
 
     '''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>
Строка 231: Строка 231:
 
       rhs(s) = g(s) = <tex>+\infty</tex>
 
       rhs(s) = g(s) = <tex>+\infty</tex>
 
     rhs(t) = 0
 
     rhs(t) = 0
     U.Insert(t, CalcKey(t))
+
     U.insert(t, CalcKey(t))
  
   UpdateVertex(u):
+
   '''function''' updateVertex(u):
 
     '''if''' u <tex>\ne</tex> t  
 
     '''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''' u <tex>\in</tex> U  
 
     '''if''' u <tex>\in</tex> U  
       U.Remove(u)
+
       U.remove(u)
 
     '''if''' g(u) <tex>\ne</tex> rhs(u)
 
     '''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(f) OR rhs(f) <tex>\ne</tex> g(f)
+
     '''while''' U.topKey() < calcKey(f) '''or''' rhs(f) <tex>\ne</tex> g(f)
       <tex>K_{old}</tex> = U.TopKey()
+
       <tex>K_{old}</tex> = U.topKey()
       u = U.Pop()
+
       u = U.pop()
 
        
 
        
       '''if''' <tex>K_{old}</tex> < CalcKey(u)
+
       '''if''' <tex>K_{old}</tex> < calcKey(u)
         U.Insert(u, CalcKey(u))
+
         U.insert(u, calcKey(u))
 
        
 
        
 
       '''if''' (g(u) > rhs(u))
 
       '''if''' (g(u) > rhs(u))
 
         g(u) = rhs(u)
 
         g(u) = rhs(u)
         '''for''' s <tex>\in</tex> Pred(u)  
+
         '''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''' s <tex>\in</tex> Pred(u) <tex>\cup</tex> {u}  
+
         '''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 (f <tex>\ne</tex> t)
+
     '''while''' f <tex>\ne</tex> t
 
       <font color="green">// if (g(f) = <tex>+\infty</tex>) тогда путь на данной итерации не найден.</font>
 
       <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>
Строка 272: Строка 272:
 
         '''for''' всех ориентированных ребер (u, v) с измененными весами:
 
         '''for''' всех ориентированных ребер (u, v) с измененными весами:
 
           Обновляем результат функции c(u, v)
 
           Обновляем результат функции c(u, v)
           UpdateVertex(u)
+
           updateVertex(u)
         ComputeShortestPath()
+
         computeShortestPath()
  
 
=== Асимптотика ===
 
=== Асимптотика ===

Версия 21:01, 17 ноября 2014

Алгоритм 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 после изменения графа. (Второй вызов функции)

Ссылки