Алгоритм 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]Succ(s) \in V[/math] как множество вершин, исходящих из вершины [math]s[/math].

Аналогично множество [math]Pred(s) \in V[/math] как множество вершин, входящих в вершину [math]s[/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]s[/math] может быть 3-х видов:

насыщена, если [math]g(s) = rhs(s)[/math]
переполнена, если [math]g(s) \gt rhs(s)[/math]
ненасыщена, если [math]g(s) \lt 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}) = +\infty[/math], то мы не смогли найти путь от [math]s_{start}[/math] до [math]s_{goal}[/math] на текущей итерации. Но после следующего изменения графа путь вполне может найтись.

Псевдокод

Основная функция, описывающая алгоритм

 Main():
 {
   Initialize();
   while (true)
   {
     ComputeShortestPath();
     В данный момент мы знаем кратчайший путь из [math]s_{start}[/math] в [math]s_{goal}[/math].
     Ждем каких-либо изменений графа.
     for всех ориентированных ребер [math](u; v)[/math] с измененными весами:
     {
       Обновляем результат функции [math]c(u; v)[/math];
       UpdateVertex([math]v[/math]);
     }
   }
 }

Теперь опишем составные элементы подробнее

 Initialize():
 {
   //Заведем приоритетную очередь [math]U[/math], в которую будем помещать вершины. Сортировка будет производиться по функции [math]key(s)[/math].
   [math]U = \varnothing;[/math]
   for [math]s \in S[/math]
     [math]rhs(s) = g(s) = \infty;[/math]
   [math]rhs(s_{start}) = 0;[/math]
   U.Insert([math]s_{start}[/math]; CalcKey([math]s_{start}[/math]));
 }

 Функция [math]key(s)[/math]. Возвращаемые значения сортируются в лексографическом порядке, т.е. сначала [math]k_1(s)[/math], потом [math]k_2(s)[/math]
 CalcKey(s):
 {
   return [[math]\min(g(s); rhs(s)) + h(s; s_{goal})[/math]; [math]\min(g(s); rhs(s))[/math]];
 }

 UpdateVertex([math]u[/math]):
 {
   if ([math]u \ne 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 ([math]g(u) \ne rhs(u)[/math])
     U.Insert([math]u[/math]; CalcKey([math]u[/math]));
 }

 ComputeShortestPath():
 {
   while (U.TopKey() < CalcKey([math]s_{goal}[/math]) OR rhs([math]s_{goal}) \ne g(s_{goal}[/math]))
     u = U.Pop();
     if (g(u) > rhs(u))
       g(u) = rhs(u);
       for [math]s \in Succ(u)[/math]
         UpdateVertex(s);
     else
       g(u) = [math]+\infty[/math];
       for [math]s \in Succ(u) \cup \{u\}[/math]
         UpdateVertex(s);
 }

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

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