Алгоритм D*

D* (pronounced "D star") is any one of the following three related incremental search algorithms.

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

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

Функция [math]g(s) будет возвращать последнее известное значение расстояние от вершины \lt tex\gt 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]

Будем говорить, что вершина s @A vertex s is called locally consistent@, если [math]g(s) = rhs(s)[/math] Очевидно, что если все вершины "locally consistent", то мы можем найти расстояние от стартовой вершины до любой.

Функция [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(s_{goal}) OR rhs(s_{goal}) != g(s_{goal}))
     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 s \in Succ(u) perec {u}
       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], используя при этом данные из предыдущих итераций. Очевидно, что в худшем случае (а именно когда все ребра вокруг текущей вершины изменили свой вес) алгоритм будет работать как последовательные вызовы алгоритма А* за O(n^2*log(n)). Улучшим эту оценку с помощью алгоритма D* lite. Примечание: на практике же такой подход тоже имеет место на плотных графах (или матрицах), так как в среднем дает оценку О(n*log(n)).