2

A* パスファインディング アルゴリズムの 1 つのステップでは、現在対話しているノードの開いているノードのリストを検索し、そのノードがまだ存在しない場合はリストに追加するか、存在する場合はその値と親を更新する必要があります。ただし、ノードの現在のバージョンよりも重みが高くなります。

これらの動作は、STL の priority_queue 構造体ではサポートされていません。そのステップをどのように実装すればよいですか？

この質問は多くのビューを獲得しているため、更新:

  • std::priority_queue はこれに適しているように見えるかもしれませんが、そうではありません。

  • A* を自分で実装することは非常に自信を高めますが、それを実行した後は、boost によって提供されるものを使用するように切り替えるようにしてください。この質問をしたとき、私はそれをインストールすることに神経質になりましたが、インストールは非常に簡単で、複雑なことはありません。また、boost が提供する便利な機能は A* だけではありません。(特に、文字列処理機能を使用しない場合は、独自のコピーを作成することになります。個人的な経験から話します...)

4

5 に答える 5

2

STL に制限されている場合は、STL セットを使用して、要素を常に消去して再挿入することができます (新しい優先順位で)。

Set< pair<int,int> > s; // < priority,value >
s.insert( make_pair(0,5) );

// Decrease Key operation //
s.erase( s.find( make_pair(0,5) ) );
s.insert( make_pair(1,5) );

時間の複雑さは依然として O(log N) ですが、大規模なセットの場合はおそらくもっと時間がかかります。

于 2012-08-11T08:04:59.903 に答える
2

STLpriority_queueは A* 実装には適していません。increase既に挿入されている項目の優先度を変更する操作をサポートするヒープ構造が必要です。多くの従来のヒープの実装にはBoost.Heapを使用します。

編集: Boost.Graph ライブラリにはA* 検索も実装されています。

于 2012-08-11T07:18:28.710 に答える
1

単純なベクトルまたは配列を使用して要素を格納し、、、、、およびを使用しstd::make_heapてstd::push_heapそれを管理できます。std::pop_heapstd::sort_heapstd::is_heapstd::is_heap_until

これにより、標準操作を自分で実装することなく、封じ込めを破り、優先キューにカスタム操作を実装できます。

于 2012-08-11T08:15:27.307 に答える
0

これには、次の 3 つの解決策が考えられます。

  1. プライオリティ キューとは関係なく、現在開いているノードのリストを追跡します。閉じたノードの場合と同じ方法でノードのリストを作成してみてください。

  2. 開閉状態へのノードのマップ (座標別) を作成します。

  3. A* のテンプレート化された実装を含む Boost ライブラリをインストールします (私は にあると思います<graph>)。

于 2012-08-11T07:04:05.243 に答える