418
правок
Изменения
Нет описания правки
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))
