2

openSet で std::priority_queue を使用して A* アルゴリズムを実装しています。ウィキペディアの疑似コードのように、アルゴリズムのある時点で:

else if tentative_g_score < g_score[neighbor]
    tentative_is_better := true

に続く

if tentative_is_better = true
    came_from[neighbor] := current
    g_score[neighbor] := tentative_g_score
    f_score[neighbor] := g_score[neighbor] + h_score[neighbor]

つまり、priority_queue で検索を実行し、その要素の 1 つの値を変更する必要がありますが、これは不可能です (私が理解している限り)。

また、この行で：

if neighbor not in openset

優先度キューで検索できないため、これをpriority_queueで実装できない場合は、openSetにある要素のみを通知するstd::setを作成することで解決しました(そのため、1つの要素を追加/削除するとstd::set と std::priority_queue の両方に追加/削除します)。

したがって、最初の問題をどのように回避できるか、またはこの特定の (まだ一般的な A*) 実装にどの std::container を実際に使用する必要があるのか​​ 疑問に思います。

より一般的に言えば、std コンテナーを使用した A* への効率的なアプローチはどれでしょうか?

4

4 に答える 4

2

以前に STL を使用して A* アルゴリズムを実装し、ほぼ同じ状況を経験しました。

私は std::vector のみで作業し、push_heap や pop_heap (priority_queue が使用するもの) などの標準アルゴリズムを使用してそれらを整理しました。

明確にするために、ベクトルで実装し、アルゴリズムを使用してベクトルを操作し、それらを良好な状態に保つ必要があります。いくつかの代替手段を使用してそのようにするよりもはるかに簡単で、潜在的に効率的です。

アップデート：

今日、私は確かに次のような Boost コンテナをいくつか試してみます: http://www.boost.org/doc/libs/1_55_0/doc/html/heap.htmlただし、Boost の使用が許可されている場合のみたとえば、私自身のコードの場合）。

于 2012-05-01T06:53:15.730 に答える
1

これは、アルゴリズムの動作に依存することで解決できます。標準priority_queueの を使用しますが、increase/decrease_key 操作の代わりに、新しいノードを優先キューに挿入します。両方のサクセサがプライオリティ キューに存在します。優先度の高いものが最初に取得され、次に展開されてクローズド リストに追加されます。優先度の高い追加ノードが取り出されると、それはすでにクローズされているため、破棄されます。

于 2014-01-31T18:18:26.267 に答える
0

残念ながら、std::コンテナーは現在、必要な操作をサポートしていません。本当に必要なのは、decrease/increase_keyスタイル操作をサポートする「インデックス付き」の優先キューです。

1 つのオプションは、これを行う独自のコンテナーを (拡張されたバイナリ ヒープに基づいて) ロールすることです。これがあまりにも手間がかかるように思われる場合は、拡張されたデータ構造を利用することでほぼ偽装できます。両方のオプションについては、こちらstd::setで詳しく説明します。 .

他の人が言ったように、別のオプションは、優先度キューを完全に削除して、並べ替えられたを維持しようとすることstd::vectorです。O(log(n))このアプローチは確実に機能し、コーディングを最小限に抑える必要があるかもしれませんが、アルゴリズム全体の漸近スケーリングに重大な影響を及ぼします。ソートされた順序を維持しながらキューの高速更新を実現することはもはや不可能です。 .

お役に立てれば。

于 2012-05-01T07:25:58.020 に答える
0

がなければdecrease_key、代わりにノードをオープン セットに再度追加することができます。オープン セットからノードをポップするときはいつでも、そのキーがそのノードの現在のスコアよりも大きいかどうかを確認してください。その場合は、ノードを処理せずに続行します。これは A* の効率性の証明を損なうものですが、実際には深刻な問題ではありません。

于 2014-01-31T18:17:59.400 に答える