418
правок
Изменения
Нет описания правки
'''Алгоритм D* (pronounced "D star") is any one of the following three related incremental search algorithms''' {{---}} алгоритм поиска кратчайшего пути во взвешенном ориентированном графе, где структура графа неизвестна заранее или постоянно подвергается изменению. Разработан Свеном Кёнигом и Максимом Лихачевым в 2002 году.
== Алгоритм LPA*== === Постановка задачи ===Дан взвешенный ориентированный граф <tex> G(V, E) </tex>. Даны вершины <tex>s_{start}</tex> и <tex>s_{goal}</tex>. Требуется после каждого изменения графа <tex>G</tex> уметь вычислять функцию <tex>g(s)</tex> для каждой известной вершины <tex>s \in V</tex> === Описание ===
Обозначим множество <tex>S</tex> как множество вершин графа.
Обозначим множество <tex>Succ(s) \in S</tex> как множество вершин, исходящих из вершины <tex>s</tex>.
Аналогично множество <tex>Pred(s) \in S</tex> как множество вершин, входящих в вершину <tex>s</tex>.
Функция <tex>0 <= \le с(s, s') <= \le +inf</tex> будет возвращать перехода из вершины <tex>s</tex> в вершину <tex>s'</tex>. При этом <tex>s' \in Succ(s)</tex>.
Функция <tex>g(s) </tex> будет возвращать последнее известное значение расстояние от вершины <tex>s_{start}</tex> до <tex>s</tex>.
Если <tex>s = s_{start}</tex>
<tex>rhs(s) = min_{s' \in pred(s)}(g(s') + c(s', s)</tex>
Будем говорить, что вершина <tex>s </tex> насыщена @A vertex s is called locally consistent@, если <tex>g(s) = rhs(s)</tex>
переполнена
Функция <tex>key(s)</tex>, где <tex>s</tex> - вершина, возвращает вектор из 2-ух значений <tex>k_1(s)</tex>, <tex>k_2(s)</tex>. <tex>k_1(s) = min(g(s), rhs(s)) + h(s, s_goal)</tex>. <tex>k_2(s) = min(g(s), rhs(s))</tex>
Если в конце поиска пути <tex>g(s_{goal}) = +inf</tex>, то мы не смогли найти путь от <tex>s_{start}</tex> до <tex>s_{goal}</tex>
=== Псевдокод:===
'''CalcKey'''(s):
