Алгоритм D*

2013-12-19T12:18:00Z

217.66.152.119:

D* (pronounced "D star") is any one of the following three related incremental search algorithms.

LPA*
Обозначим множество <tex>S</tex> как множество вершин графа.
Обозначим множество <tex>Succ(s) \in S</tex> как множество вершин, исходящих из вершины <tex>s</tex>.
Аналогично множество <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) будет возвращать последнее известное значение расстояние от вершины <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_{goal}) = +inf</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>];
}

'''Initialize'''():
{
<tex>U = null;</tex>
<tex>for all s \in S</tex>
<tex>rhs(s) = g(s) = 1;</tex>
<tex>rhs(s_start) = 0;</tex>
<tex>U.Insert(s_{start};CalcKey(s_{start}));</tex>
}

'''UpdateVertex'''(<tex>u</tex>):
{
if (<tex>u != s_{start}</tex>)
<tex>rhs(u) = min_{s' \in Pred(u)}(g(s')+c(s',u));</tex>
if (<tex>u \in U</tex>)
U.Remove(u);
if (g(u) != rhs(u))
U.Insert(<tex>u</tex>;CalcKey(<tex>u</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))
g(u) = rhs(u);
for all s 2 Succ(u) UpdateVertex(s);
else
g(u) = 1;
for all <tex>s \in Succ(u) perec {u}</tex>
UpdateVertex(s);
}

'''Main'''():
{
Initialize();
while (<tex>s_{start} != s_{goal}</tex>)
{
ComputeShortestPath();
Wait for changes in edge costs;
for all directed edges (u;v) with changed edge costs
{
Update the edge cost c(u;v);
UpdateVertex(v);
}
}
}

Таким образом мы описали алгоритм LPA*. Он неоднократно определяет путь между вершинами <tex>s_start</tex> и <tex>s_goal</tex>, используя при этом данные из предыдущих итераций. Очевидно, что в худшем случае (а именно когда все ребра вокруг текущей вершины изменили свой вес) алгоритм будет работать как последовательные вызовы алгоритма А* за <tex>O(n^2*log(n))</tex>. Улучшим эту оценку с помощью алгоритма D* lite.

'''Примечание''': на практике же такой подход тоже имеет место на плотных графах (или матрицах), так как в среднем дает оценку О(n*log(n)).

== Алгоритм D* ==

'''CalcKey'''(s):
return [<tex>min(g(s);rhs(s)) + h(sstart;s)</tex>;<tex>min(g(s); rhs(s))</tex>];

'''Initialize'''():
U = null;
for all <tex>s \in S</tex>
<tex>rhs(s) = g(s) = 1</tex>
<tex>rhs(s_{goal}) = 0</tex>
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();

Викиконспекты - Вклад участника [ru]

Алгоритм D*