1

make_heap/push_/pop_A* 操作の優先度キューにstd::vector を使用するよりも、std::set を使用する方が効率的 (wrt 時間) になるのはいつですか? 私の推測では、開いているリストの頂点が小さい場合は、ベクトルを使用する方が良いオプションです。しかし、これを経験した人はいますか？

4

5 に答える 5

1

優先キューを使用します。バイナリヒープベースのものは問題ありません（ベクターベースのstd優先度キューのように）。O（n）時間でヒープを構築でき、関連するすべての操作にO（logn）がかかります。それに加えて、a*に役立つ減少キー操作を実装できます。ただし、stdキューに実装するのは難しいかもしれません。セットでこれを行う唯一の方法は、要素を削除して、別の優先度で再挿入することです。

編集：あなたは使用を検討したいかもしれません

std::make_heap

（および関連する機能）。そうすれば、ベクターにアクセスでき、decrease_keyを簡単に実装できます。

編集2：make heapを使用するつもりだったので、decreaseキーを実装するだけです。

于 2009-06-13T15:43:28.617 に答える
1

A* 経路探索作業を行っている場合は、Dan Higgins による AI Wisdom の記事をチェックしてください。には、データ構造を高速に取得する方法の説明があります。彼は、最近のノードのホット キャッシュを持ち、データ構造の経路探索に対する多くのペナルティを回避するような「チープ リスト」について言及しています。

http://introgamedev.com/resource_aiwisdom.html

于 2010-08-16T14:25:27.547 に答える
0

リストのどこかに常に単一の要素を追加することになるため、A* 検索の優先度キューのベクトル ベースのデータ構造は良い考えではないと思います。フリンジ（これがあなたのやり方だと思います）が大きく、要素が途中で追加される場合、これは非常に非効率的です。

数週間前に Java で A* を実装したとき、プライオリティ ヒープに基づいていると思われる Java PriorityQueue を使用しました。setC++ での使用をお勧めします。

編集：ニキに感謝します。バイナリヒープが（配列を使用して）どのように実装されているかを理解し、質問で実際に何を求めているかを理解しました。a が最適なオプションだと思いますが、(Igor が言ったように) a に交換してそのパフォーマンスを確認するpriority_queueことは難しくありません。setプライオリティ キュー (少なくとも Java と C++) がバイナリ ヒープを使用して実装されているのには理由があると思います。

于 2009-06-13T04:10:19.267 に答える