Алгоритм 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;sgoal);min(g(s); rhs(s))]; }

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

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

procedure ComputeShortestPath() { while (U.TopKey()< CalcKey(sgoal) OR rhs(sgoal) != g(sgoal)) 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); } } }