Алгоритм 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] будет возвращать перехода из вершины s в вершину s'. При этом s' in Succ(s).

Функция g(s) будет возвращать последнее известное значение расстояние от вершины s_start до s.

Если [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@, если g(s) = rhs(s) Очевидно, что если все вершины "locally consistent", то мы можем найти расстояние от стартовой вершины до любой.

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

Если в конце поиска пути g(s_goal) = +inf, то мы не смогли найти путь от s_start до s_goal

Псевдокод:

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

 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);
 }

 procedure Main()
 {
   Initialize();
   while (s_start != s_goal)
   {
     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)).