418
правок
Изменения
Нет описания правки
LPA*
Обозначим множество <tex>S</tex> как множество вершин графа.
Обозначим множество <tex>Succ(s) \in S</tex> как множество вершин, исходящих из вершины <tex>s</tex>.
Аналогично множество <tex>Pred(s) \in S</tex> как множество вершин, входящих в вершину <tex>s</tex>.
'''ComputeShortestPath'''():
{
while (U.TopKey()< CalcKey(<tex>s_{goal}</tex>) OR rhs(<tex>s_{goal}) != g(s_{goal}</tex>))
u = U.Pop();
if (g(u) > rhs(u))
else
g(u) = 1;
for all <tex>s \in Succ(u) perec {u}</tex>
UpdateVertex(s);
}
{
Initialize();
while (<tex>s_start s_{start} != s_goals_{goal}</tex>)
{
ComputeShortestPath();
Таким образом мы описали алгоритм LPA*. Он неоднократно определяет путь между вершинами <tex>s_start</tex> и <tex>s_goal</tex>, используя при этом данные из предыдущих итераций. Очевидно, что в худшем случае (а именно когда все ребра вокруг текущей вершины изменили свой вес) алгоритм будет работать как последовательные вызовы алгоритма А* за O(n^2*log(n)). Улучшим эту оценку с помощью алгоритма D* lite.
'''Примечание''': на практике же такой подход тоже имеет место на плотных графах (или матрицах), так как в среднем дает оценку О(n*log(n)).
== Алгоритм D* ==
'''CalcKey'''(s):
return [min(g(s);rhs(s)) + h(sstart;s);min(g(s); rhs(s))];
'''Initialize'''():
U = null;
for all s 2 S rhs(s) = g(s) = 1;
rhs(sgoal) = 0;
U.Insert(sgoal;CalcKey(sgoal));
'''UpdateVertex'''(u):
if (u 6= s_{goal}) rhs(u) = mins02Succ(u)
(c(u;s
0
) + g(s
0
));
f07’g if (u 2 U) U.Remove(u);
f08’g if (g(u) 6= rhs(u)) U.Insert(u;CalcKey(u));
'''ComputeShortestPath'''()
while (U.TopKey()<_ CalcKey(s_{start}) OR rhs(s_{start}) 6= g(s_{start}))
u = U.Pop();
if (g(u) > rhs(u))
g(u) = rhs(u);
for all s 2 Pred(u) UpdateVertex(s);
else
g(u) = 1;
for all s 2 Pred(u) [ fug UpdateVertex(s);
'''Main'''():
Initialize();
ComputeShortestPath();
while (s_{start} 6= s_{goal})
if (g(sstart) = 1) then there is no known path */
sstart = argmins02Succ(sstart)
(c(sstart;s
0
) + g(s
0
));
f22’g Move to sstart;
f23’g Scan graph for changed edge costs;
f24’g if any edge costs changed
f25’g for all directed edges (u;v) with changed edge costs
f26’g Update the edge cost c(u;v);
f27’g UpdateVertex(u);
f28’g for all s 2 U
f29’g U.Update(s;CalcKey(s));
f30’g ComputeShortestPath();
