Алгоритм D * -Lite - PullRequest
Новая
       71

Алгоритм D * -Lite

8 голосов
/ 12 августа 2011

Я пытаюсь реализовать алгоритм поиска пути D * -Lite, как описано в статье *1002* 2002 года Кенига и Лихачева, для Boost :: Graph.Я думаю, что я достаточно хорошо понял основные идеи и теорию, лежащую в основе этого, но у меня проблемы с пониманием, когда обновляются наборы Pred и Succ.

Я предполагаю, что это происходит на шаге Move to sstart в Main, но тогда первый вызов ComputeShortestPath будет довольно бессмысленным?И должен ли набор Succ быть вставлен одновременно с Pred?Тогда Pred и Succ могут быть представлены как двусвязные списки?

Я вставил псевдокод алгоритма ниже.Наборы Pred и Succ являются предшественниками и преемниками соответственно.g, h, rhs и c - это разные затраты и веса.U - приоритетная очередь посещаемых вершин.

procedure CalculateKey(s)
{01’} return [min(g(s), rhs(s)) + h(sstart, s) + km; min(g(s), rhs(s))];

procedure Initialize()
{02’} U = ∅;
{03’} km = 0;
{04’} for all s ∈ S rhs(s) = g(s) = ∞;
{05’} rhs(sgoal) = 0;
{06’} U.Insert(sgoal, CalculateKey(sgoal));

procedure UpdateVertex(u)
{07’} if (u ≠ sgoal) rhs(u) = min s'∈Succ(u)(c(u, s') + g(s'));
{08’} if (u ∈ U) U.Remove(u);
{09’} if (g(u) ≠ rhs(u)) U.Insert(u, CalculateKey(u));

procedure ComputeShortestPath()
{10’} while (U.TopKey() < CalculateKey(sstart) OR rhs(sstart) ≠ g(sstart))
{11’}   kold = U.TopKey();
{12’}   u = U.Pop();
{13’}   if (kold ˙<CalculateKey(u))
{14’}     U.Insert(u, CalculateKey(u));
{15’}   else if (g(u) > rhs(u))
{16’}     g(u) = rhs(u);
{17’}     for all s ∈ Pred(u) UpdateVertex(s);
{18’}   else
{19’}     g(u) = ∞;
{20’}     for all s ∈ Pred(u) ∪ {u} UpdateVertex(s);

procedure Main()
{21’} slast = sstart;
{22’} Initialize();
{23’} ComputeShortestPath();
{24’} while (sstart ≠ sgoal)
{25’}   /* if (g(sstart) = ∞) then there is no known path */
{26’}   sstart = argmin s'∈Succ(sstart)(c(sstart, s') + g(s'));
{27’}   Move to sstart;
{28’}   Scan graph for changed edge costs;
{29’}   if any edge costs changed
{30’}     km = km + h(slast, sstart);
{31’}     slast = sstart;
{32’}     for all directed edges (u, v) with changed edge costs
{33’}       Update the edge cost c(u, v);
{34’}       UpdateVertex(u);
{35’}     ComputeShortestPath();

Ответы [ 2 ]

8 голосов
/ 15 августа 2011

Оказывается, у меня не было приличного понимания основных идей и теории ... Я неправильно понял значение слов "преемник" и "предшественник", поскольку я предполагал, что оно подразумевалось "«путь порядка», чтобы в пути v0->v1->v2, v0 был предшественником v1, а v2 - преемником.

Что подразумевалось под простыми соседями.Набор предшественников был набором всех вершин с «ребром» для данной вершины, а у преемников были «ребра».

0 голосов
/ 22 октября 2014

Прочтите LPA * бумагу, вы узнаете, что это такое.По сути, в LPA * поиск начинается с начальной позиции.Таким образом, преемниками будут узлы вокруг узла u.Pop.Это означает, что они являются узлами, к которым вы перейдете с текущего узла.И Пред, это просто материнский узел.Это означает, что Pred наследников - это u.Pop.

В D Lite все идет наоборот.Поиски начинаются с голевой позиции.Так что это немного смущает вас.Преемник D Lite находится в LPA *.Итак, преемник = U.pop.Пред D Lite является преемником в LPA .Итак, Pred - это узел, к которому вы перейдете от преемника.

Надеюсь, вы понимаете мой плохой английский.

...