8

私は初めて A* を開発しました。ノードがクローズ セットだけでなく、オープン セットにも含まれているかどうかを確認する必要があることに気付くまで、オープン セットに priority_queue を使用していました。

つまり、プライオリティ キューを反復処理することはできません..では、なぜ誰もがオープン セットにプライオリティ キューを推奨するのでしょうか? それはまだ最良の選択肢ですか？それを反復する唯一の方法は、コピーを作成して、そこからすべてをポップできるようにすることだと思います（莫大なコスト）。

A* で使用するのに最適なデータ構造は?

4

3 に答える 3

7

プライオリティ キュー (PQ) は抽象データ構造 (ADS) です。それらを実装する可能性はたくさんあります。残念ながら、C++ 標準ライブラリで提供される priority_queue はかなり制限されており、他の実装は A* の実装に適しています。ネタバレ: std::priority_queue の代わりに std::set/multiset を使用できます。しかし、読んでください：

A* を実装するためにプライオリティ キューから必要なものは次のとおりです。

  1. コストが最も低いノードを取得する
  2. 任意の要素のコストを削減

任意のプライオリティ キューで 1. を実行できますが、2. の場合は「変更可能な」プライオリティ キューが必要です。Standard-Lib はこれを行うことができません。また、キーを減らす場所を見つけるために、優先度キューでエントリを見つける簡単な方法が必要です (A* が既に開いているノードへのより良いパスを見つけた場合)。これには 2 つの基本的な方法があります。グラフ ノード内に優先キュー要素へのハンドルを格納する (または、マップを使用して各グラフ ノードのハンドルを格納する)、またはグラフ ノード自体を挿入します。

各ノードのハンドルを格納する最初のケースでは、プライオリティ キューに std::multiset を使用できます。std::multiset::first() は常に「最もコストの低い」キーであり、キーをセットから削除し、値を変更して再挿入し、ハンドルを更新することでキーを減らすことができます。または、「キーの減少」を直接サポートする Boost.Heap の変更可能な優先度キューを使用することもできます。

2 番目のケースでは、ある種の「押し付けがましい」バイナリ ツリーが必要になります。これは、経路探索ノード自体が優先キューにある必要があるためです。自分で作成したくない場合は、Boost.Intrusive の順序付けられた連想コンテナーを参照してください。

于 2012-09-03T22:54:16.037 に答える
3

主題は非常に大きいので、さまざまな可能性を知り、どのデータ構造が自分の状況に適しているかをよく理解したい場合は、このページを読むことをお勧めします: http://theory.stanford.edu/~amitp/GameProgramming/ ImplementationNotes.html#set-representation

私の場合、バイナリ ヒープは実装の難しさとパフォーマンスのバランスが取れており、まさに私が求めていたものでした。しかし、おそらくあなたは何か違うものを探していますか？

ドキュメントの残りの部分は、ゲーム開発のための A* の非常に優れたリファレンスです http://theory.stanford.edu/~amitp/GameProgramming/index.html

于 2012-09-03T20:37:15.333 に答える
-1

それらは、必ずしも言語に付属する std::priority_queue クラスではない優先キューを意味します。組み込みのもので必要なことを実行できない場合は、独自のものを作成するか、別のものを見つけてください。

于 2012-09-03T21:46:53.557 に答える