Алгоритм D*

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

Алгоритм LPA*

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

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

Описание

Обозначим множество [math]S[/math] как множество вершин графа.

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

Аналогично множество [math]Pred(s) \in S[/math] как множество вершин, входящих в вершину [math]s[/math].

Функция [math]0 \le с(s, s') \le +inf[/math] будет возвращать перехода из вершины [math]s[/math] в вершину [math]s'[/math]. При этом [math]s' \in Succ(s)[/math].

Функция [math]g(s)[/math] будет возвращать последнее известное значение расстояние от вершины [math]s_{start}[/math] до [math]s[/math].

Если [math]s = s_{start}[/math] [math]rhs(s) = 0[/math] Иначе [math]rhs(s) = min_{s' \in pred(s)}(g(s') + c(s', s)[/math]

Будем говорить, что вершина [math]s[/math] насыщена, если [math]g(s) = rhs(s)[/math] переполнена ненасыщена Очевидно, что если все вершины насыщены, то мы можем найти расстояние от стартовой вершины до любой.

Функция [math]key(s)[/math], где [math]s[/math] - вершина, возвращает вектор из 2-ух значений [math]k_1(s)[/math], [math]k_2(s)[/math]. [math]k_1(s) = min(g(s), rhs(s)) + h(s, s_goal)[/math]. [math]k_2(s) = min(g(s), rhs(s))[/math]

Если в конце поиска пути [math]g(s_{goal}) = +inf[/math], то мы не смогли найти путь от [math]s_{start}[/math] до [math]s_{goal}[/math]

Псевдокод

 CalcKey(s):
 {
   return [[math]min(g(s); rhs(s)) + h(s;s_{goal})[/math];[math]min(g(s); rhs(s))[/math]];
 }

 Initialize():
 {
   [math]U = null;[/math]
   [math]for all s \in S[/math]
     [math]rhs(s) = g(s) = 1;[/math]
   [math]rhs(s_start) = 0;[/math]
   [math]U.Insert(s_{start};CalcKey(s_{start}));[/math]
 }

 UpdateVertex([math]u[/math]):
 {
   if ([math]u != s_{start}[/math]) 
     [math]rhs(u) = min_{s' \in Pred(u)}(g(s')+c(s',u));[/math]
   if ([math]u \in U[/math])
     U.Remove(u);
   if (g(u) != rhs(u))
     U.Insert([math]u[/math];CalcKey([math]u[/math]));
 }

 ComputeShortestPath():
 {
   while (U.TopKey()< CalcKey([math]s_{goal}[/math]) OR rhs([math]s_{goal}) != g(s_{goal}[/math]))
     u = U.Pop();
     if (g(u) > rhs(u))
       g(u) = rhs(u);
       for all s 2 Succ(u) UpdateVertex(s);
     else
       g(u) = 1;
     for all [math]s \in Succ(u) perec {u}[/math]
       UpdateVertex(s);
 }

 Main():
 {
   Initialize();
   while ([math]s_{start} != s_{goal}[/math])
   {
     ComputeShortestPath();
     Wait for changes in edge costs;
     for all directed edges (u;v) with changed edge costs
     {
       Update the edge cost c(u;v);
       UpdateVertex(v);
     }
   }
 }

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

Примечание: на практике же такой подход тоже имеет место на плотных графах (или матрицах), так как в среднем дает оценку О(n*log(n)).

Алгоритм D*

 CalcKey(s):
   return [[math]min(g(s);rhs(s)) + h(sstart;s)[/math];[math]min(g(s); rhs(s))[/math]];

 Initialize():
   U = null;
   for all [math]s \in S[/math]
     [math]rhs(s) = g(s) = 1[/math]
   [math]rhs(s_{goal}) = 0[/math]
   U.Insert(sgoal;CalcKey(sgoal));

 UpdateVertex(u):
   if (u 6= s_{goal}) rhs(u) = mins02Succ(u)

(c(u;s 0 ) + g(s 0 )); f07’g if (u 2 U) U.Remove(u); f08’g if (g(u) 6= rhs(u)) U.Insert(u;CalcKey(u));

 ComputeShortestPath()
   while (U.TopKey()<_ CalcKey(s_{start}) OR rhs(s_{start}) 6= g(s_{start}))
     u = U.Pop();
     if (g(u) > rhs(u))
       g(u) = rhs(u);
     for all s 2 Pred(u) UpdateVertex(s);
     else
       g(u) = 1;
     for all s 2 Pred(u) [ fug UpdateVertex(s);

 Main():
   Initialize();
   ComputeShortestPath();
   while (s_{start} 6= s_{goal})
     if (g(sstart) = 1) then there is no known path */
     sstart = argmins02Succ(sstart)

(c(sstart;s 0 ) + g(s 0 )); f22’g Move to sstart; f23’g Scan graph for changed edge costs; f24’g if any edge costs changed f25’g for all directed edges (u;v) with changed edge costs f26’g Update the edge cost c(u;v); f27’g UpdateVertex(u); f28’g for all s 2 U f29’g U.Update(s;CalcKey(s)); f30’g ComputeShortestPath();

Ссылки

• Wikipedia:D*
• Sven Koenig` web page