418
правок
Изменения
Нет описания правки
Аналогично множество <tex>Pred(s) \in V</tex> как множество вершин, входящих в вершину <tex>s</tex>.
Функция <tex>0 \le lessgtr с(s, s') \le lessgtr +\infty</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>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}) = +\infty</tex>, то мы не смогли найти путь от <tex>s_{start}</tex> до <tex>s_{goal}</tex> на текущей итерации. Но после следующего изменения графа путь вполне может найтись.
'''CalcKey'''(s):
{
return [<tex>\min(g(s); rhs(s)) + h(s; s_{goal})</tex>;<tex>\min(g(s); rhs(s))</tex>];
}
}
Таким образом мы описали алгоритм LPA*. Он неоднократно определяет путь между вершинами <tex>s_starts_{start}</tex> и <tex>s_goals_{goal}</tex>, используя при этом данные из предыдущих итераций. Очевидно, что в худшем случае (а именно когда все ребра вокруг текущей вершины изменили свой вес) алгоритм будет работать как последовательные вызовы алгоритма А* за <tex>O(n^2*\dot log(n))</tex>. Улучшим эту оценку с помощью алгоритма D* lite.
'''Примечание''': на практике же такой подход тоже имеет место на плотных графах (или матрицах), так как в среднем дает оценку О(n*log(n)).
U.Insert(u; CalcKey(u));
'''ComputeShortestPath'''(): while (U.TopKey() <tex><=</tex> CalcKey(<tex>s_{start}</tex>) OR <tex>rhs(s_{start}) != \ne g(s_{start})</tex>)
u = U.Pop();
if (g(u) > rhs(u))
'''Main'''():
'''Initialize'''(); '''ComputeShortestPath'''();
while (<tex>s_{start} \ne s_{goal}</tex>)
// if (<tex>g(s_{start}) = \infty</tex>) тогда путь на данной итерации не найден.
<tex>s_{start} </tex> = argmins02Succтакая вершина s', что <tex>min_{s' \in Succ(sstarts_{start})}(c(s_{start}, s')+ g(s'))</tex> Move to Передвинулись вдоль найденного пути и изменили вершину <tex>s_{start}</tex>; Scan graph for changed edge costs;Ждем каких-либо изменений в графе или убеждаемся, что граф остается прежним. if any edge costs changed(если граф изменился) for all directed edges всех ориентированных ребер <tex>(u; v) with changed edge costs</tex> с измененными весами: Update the edge cost Обновляем результат функции <tex>c(u; v)</tex>; '''UpdateVertex'''(u);
for <tex>s \in U</tex>
U.Update(<tex>s</tex>; '''CalcKey'''(<tex>s</tex>));
ComputeShortestPath();
