グラフ アプリケーションのデータ構造として STL priority_queue を使用しています。Prim のスパニング ツリー アルゴリズムの高度なバージョンのように安全に想定できます。アルゴリズムでは、(最小ノードだけでなく) 優先度キュー内のノードを効率的に見つけたいと考えています。[ノードのコストが変更される可能性があり、priority_queue で修正する必要があるため、これが必要です] priority_queue を作成し、ノード キーにも基づいてインデックスを作成します。STLでこれを行う方法が見つかりません。STLでそれを行う方法をもっとよく知っている人はいますか?
3365 次
1 に答える
2
はstd::priority_queue<T>、ノードの効率的なルックアップをサポートしていません。通常、 d-ary ヒープd == 2を使用します。この表現は、ノードを配置したままにしません。Prim のアルゴリズムでa を本当に使用したい場合std::priority_queue<T>、唯一の方法は、現在の最短距離でノードを追加し、場合によっては各ノードを複数回追加することです。O(E)ただし、これにより のサイズが の代わりに に変わりO(N)ます。つまり、多くのエッジを持つグラフの場合、はるかに複雑になります。
次のようなものを使用できますstd::map<...>が、実際にはほとんど同じ問題に悩まされています。効率的に抽出する次のノードを見つけるか、効率的に更新するノードを見つけることができます。
「適切な」アプローチは、ノードベースのプライオリティ キュー、たとえばフィバノッチ ヒープを使用することです。ノードは配置されたままであるため、ノードを挿入するときにヒープからハンドルを取得し、扱う。最も近いノードへのアクセスは、ヒープのツリー セット内のいくつかのトップ ノードを使用することで効率的になります。基本的なヒープ操作 ( push()、top()、およびpop()) の全体的なパフォーマンスは、d-ary ヒープよりもフィボナッチ ヒープの方が遅くなりますが、個々のノードの効率的な更新により、使用する価値があります。Prim のアルゴリズムでは、厳密な複雑さの境界を達成するために実際にフィボナッチ ヒープが必要だったことを思い出すようです。
Boostに Fibonacci-heaps の実装があることは知っています。フィボナッチ ヒープの効率的な実装は完全に簡単というわけではありませんが、単に理論的な関心を引くよりも効率的です。
于 2013-11-15T00:27:51.783 に答える