Алгоритм D*

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

Содержание

1 Алгоритм LPA*
2 Алгоритм D*
3 Ссылки

Алгоритм 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]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_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)).