8

Boost::Graph の Koenig と Likhachev による2002 年の記事で説明されているように、D*-Lite 経路探索アルゴリズムを実装しようとしています。基本的なアイデアとその背後にある理論については十分に理解できたと思いますが、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();
4

2 に答える 2

8

基本的な考え方や理論をきちんと把握していなかったことが判明しました...「後継者」と「前任者」の意味を誤解しました。「パスの順序で」という意味だと思っていたのでv0->v1->v2、v0の前身でv1ありv2、後継者です。

しかし、意味していたのは単に隣人でした。先行セットは、指定された頂点への「インエッジ」を持つすべての頂点のセットであり、後続セットには「アウトエッジ」がありました。

于 2011-08-15T16:15:37.087 に答える
0

LPA* の論文を読めば、それらが何であるかがわかります。基本的に、LPA* では開始位置から検索を開始します。したがって、後続ノードは u.Pop ノードの周囲のノードになります。これは、現在のノードから移動するノードであることを意味します。Pred は単なるマザー ノードです。これは後継者の Pred が u.Pop であることを意味します。

D Lite では、すべてが逆になります。検索はゴール位置から始まります。だから、それはあなたにとって少し混乱しています。D Liteの後継機はLPA※のPredです。つまり、後継者＝U.pop。D Lite の Pred は LPA の後継です。したがって、Pred は、サクセサーから移動するノードです。

私の拙い英語を理解していただければ幸いです。

于 2014-10-22T16:58:03.863 に答える