4

Prim のアルゴリズムを実装しようとしています。そのためには、優先度キューの reduceKey メソッドが必要です (優先度キューのキー値を更新するため)。これを STL Priority Queue に実装できますか?

それが役立つ場合、これは私が従っているアルゴリズムです:

  • グラフ G の各頂点 u に対して
    • u のキーを INFINITY に設定
    • u の親を NIL に設定する
  • ソース頂点のキーを 0 に設定
  • 上記のキーを使用して、グラフ内のすべての頂点を優先度キュー Q にキューに入れます。
  • Q は空ではありません
    • Q の最小キーで頂点 u をポップする
    • u の各隣接頂点 v について
      • (v がまだ Q にある) かつ (key(u) + weight-function(u, v) < key(v)) の場合
        • u を v の親に設定する
        • update v's key to equal key(u) + weight-function(u, v) // この部分で問題が発生します。これは、優先度キューに reduceKey を実装する方法がわからないためです
4

4 に答える 4

9

STLコンテナに実装できるとは思いません。ベクトルに基づいて独自のヒープ (優先キュー) をいつでも作成できることを覚えておいてください。ただし、回避策があります。

あなたが持っている距離の配列を保持してくださいd。優先キューに、距離のペアとこの距離の頂点のインデックスを入れます。キューから値を削除する必要がある場合は、それを削除せずに、d配列の値を更新して新しいペアをキューに入れます。

キューから新しい値を取得するたびに、配列のように、ペアの距離が実際にそれほど良いかどうかを確認してくださいd。そうでない場合は無視してください。

時間は同じ O(MlogM) です。メモリは O(MlogM) で、M はエッジの数です。

別のアプローチがあります。RB-Tree を使用すると、O(logN) にキーを挿入および削除でき、最小値も取得できます。std::setコンテナー内の RB-Tree の STL で実装を見つけることができます。

ただし、時間計算量は同じですが、RB-Tree は動作が遅く、隠れ定数が大きいため、少し遅くなる可能性があります。5倍遅い。もちろん、データに依存します。

于 2013-01-19T09:13:45.810 に答える
2

他のアプローチの場合：std::setを使用するよりも優れています。btree :: btree_set（またはbtree :: safe_btree_set）を使用できます。これは、RB-Treeを使用するstlとは異なり、B-Treeを使用してgoogleによって作成されたstd::setと同じ実装です。これは、std :: setおよびO（logN）よりもはるかに優れています。パフォーマンスの比較を確認してください： http ：//code.google.com/p/cpp-btree/wiki/UsageInstructions また、メモリフットプリントもはるかに少なくなっています。

于 2013-02-26T12:39:27.277 に答える
0

ほとんどのソートは NLogN に限定されていると思うので、reduce key 操作にはソートよりも再挿入用の 2 LogN の方が適しているかもしれません。

もう1つは、ベクトルへの挿入はそれほどホットではありませんが、全体として、ベクトルw lower_boundのアイデアは検討する価値があるように見えますか?

ありがとう

于 2015-02-06T20:42:33.250 に答える
0

私は専門家ではないので、これがばかげていないことを願っていますが、lower_bound と組み合わせたベクトルは非常にうまく機能しますか?

lower_bound を使用して新しい値を挿入する正しい場所を見つけると、ベクターはビルド時に常に並べ替えられ、並べ替えは必要ありません。ベクトルがソートされている場合、lower_bound は対数クラスのパフォーマンスを持つバイナリ検索ではありませんか?

ソートされているため、最小値 (または最大値) を見つけるのは簡単です。

キーを削減するには、lower_bound 検索を実行し、削除してから、lower_bound を再度実行して、削減されたキーを挿入します。これは、2 つの対数クラス演算です。それでも悪くない。

または、キーを更新してベクトルをソートすることもできます。私はランダムアクセスで推測しますが、それはまだ対数クラスにあるはずですが、 stl がそこで何をするのか正確にはわかりません。

並べ替えられたベクトルを使用すると、候補キーがそこにあるキーよりも小さいことがわかっている場合、パフォーマンスをさらに向上させるために、値がすべて小さいベクトルの部分を並べ替えることができます。

もう1つの考慮事項は、セット/マップにはベクトルよりもかなり多くのメモリオーバーヘッドがあると思いますか?

于 2015-02-06T16:42:24.787 に答える