Алгоритм D*

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

LPA*

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

Если s = s_start rhs(s) = 0 Иначе rhs(s) = min_s' in pred(s) (g(s') + c(s', s)

Будем говорить, что вершина s @A vertex s is called locally consistent@ Очевидно, что если все вершины "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))