Алгоритм D* — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Init)
 
Строка 1: Строка 1:
 
D* (pronounced "D star") is any one of the following three related incremental search algorithms.
 
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))

Версия 17:40, 17 декабря 2013

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))