418
правок
Изменения
Нет описания правки
Аналогично множество <tex>Pred(s) \in S</tex> как множество вершин, входящих в вершину <tex>s</tex>.
Функция <tex>0 <= с(s, s') <= +inf</tex> будет возвращать перехода из вершины <tex>s </tex> в вершину <tex>s'</tex>. При этом <tex>s' \in Succ(s)</tex>.
Функция <tex>g(s) будет возвращать последнее известное значение расстояние от вершины s_start <tex>s_{start}</tex> до <tex>s</tex>.
Если <tex>s = s_{start}</tex>
<tex>rhs(s) = 0</tex>
Иначе
<tex>rhs(s) = min_{s' \in pred(s)}(g(s') + c(s', s)</tex>
Будем говорить, что вершина s @A vertex s is called locally consistent@, если <tex>g(s) = rhs(s)</tex>
Очевидно, что если все вершины "locally consistent", то мы можем найти расстояние от стартовой вершины до любой.
Функция <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_goals_{goal}) = +inf</tex>, то мы не смогли найти путь от s_start <tex>s_{start}</tex> до s_goal<tex>s_{goal}</tex>
Псевдокод:
{
return [<tex>min(g(s); rhs(s)) + h(s;s_{goal})</tex>;<tex>min(g(s); rhs(s))</tex>];
}
'''Initialize'''():
{
<tex>U = null;</tex>
}
{
Initialize();
while (<tex>s_start != s_goal</tex>)
{
ComputeShortestPath();
Таким образом мы описали алгоритм LPA*. Он неоднократно определяет путь между вершинами <tex>s_start</tex> и <tex>s_goal</tex>, используя при этом данные из предыдущих итераций. Очевидно, что в худшем случае (а именно когда все ребра вокруг текущей вершины изменили свой вес) алгоритм будет работать как последовательные вызовы алгоритма А* за O(n^2*log(n)). Улучшим эту оценку с помощью алгоритма D* lite.
'''Примечание''': на практике же такой подход тоже имеет место на плотных графах (или матрицах), так как в среднем дает оценку О(n*log(n)).
== Алгоритм D* ==
