私が扱いたい大規模なネットワーク（小さな世界のグラフタイプ）は本質的に動的であり、新しいノードが頻繁に追加および削除されます。おそらく、A*ではなくD*を使用する方が、この動的な環境でパスを検出するためのより良い方法でしょうか？
D *はどれくらいしっかりしていますか？実世界での経験はありますか？暗号化アルゴリズムのように-D*は多くのピアレビューとテストによって強化されていますか？この問題にD*を使用しますか？
2976 次
2 に答える
15
私が理解しているように、初めて D* を実行すると、ほぼ同じ実行時間で A* と同じパスが検出されます。ただし、ノードがエッジ値を変更するかノードが追加されると、A* はすべてのパスを再計算しますが、D* は一貫性のないノードを全体ではなく 2 回目に再計算します。
Anthony Stentz の D* アルゴリズム (元のホワイトペーパーはこちら) は、彼の作品の派生物によってほとんど廃止されています。D* Lite と LPA* は最も一般的に使用されており、コーディングや実装がはるかに簡単です。
実世界での経験に関する限り、NASA のジェット推進研究所のジョセフ・カーステンとアート・ランキンは、火星探査機「スピリット」と「オポチュニティ」に D* Lite の要素を使用してフィールド D* のバージョンをインストールしました (D* を使用したローバーのスライドショーはこちら) 。 . 2007 年 2 月には、火星探査機を完全に自律的に操縦するために使用されました。
代替テキスト http://asm.arc.nasa.gov/Gallery/images/generic/rover.jpg
明らかに、D* はロボティクスの分野で非常に有用です。これは、ロボットに搭載されたセンサーが常にエッジ値を再評価しているためです。私自身の意見では、それはかなり「戦闘テスト済み」になります。
同様に、モバイル ゲームでの D* Lite アルゴリズムの使用について言及している別のホワイトペーパーも見つけました。
私はこれまで D* を実装したことがなく、A* のみを実装したことを述べて、この回答を終了します。複雑さが大幅に増加するため、D* (または D* Lite) は、グラフに重大かつ頻繁な変更がある場合にのみ使用する必要があると言えます。あなたはあなたの状況がそれに似ていると説明したので、間違いなくD * Liteに行くと思います. NASA がそれを使用する場合、徹底的に調査されていることは間違いありません。
于 2008-10-23T02:38:49.577 に答える
0
D* アルゴリズムと A* アルゴリズムの両方を実装しました。したがって、マップに動的な障害物がない場合は、A* を実装することをお勧めします。そうでなければ、D* を実装します。主な理由は次のとおりです。最初の検索で、D* はマップ内のすべてのノードを計算し、次に最短経路を表示しますが、A* はマップ内のゴールとスタート ポイント周辺の限られたエリアのみを計算します。したがって、D* よりもはるかに高速です。動的な環境では、D* は A* よりも高速で効率的です。途中でロボットが新しい障害物を検出した場合、予期しない障害物の周囲のいくつかのノードのみを更新するためです。一方、A* はすべてを再計算します。
于 2014-10-22T16:46:52.013 に答える