2

与えられた重みの最小値が既にわかっている場合、プリムのアルゴリズムをどのように変更できますか? たとえば、グラフがエッジの重み 0 と 1 で構成されている場合、プリムのアルゴリズムを高速化するにはどうすればよいでしょうか?

4

1 に答える 1

6

最初の戦略は、プライオリティ キューを改善してデータを活用することです。重みが C 未満の離散値であることがわかっている場合は、通常使用されるバイナリ ヒープを基数ヒープに置き換えることができます。このようにして、実装がはるかに困難なフィボナッチ ヒープと同じか、それ以上のアルゴリズムの複雑さを簡単に得ることができます。ダイクストラのアルゴリズムはまったく同じデータ構造を使用しており、基数ヒープを実装する方法の完全な説明を次に示します。

http://www.cosc.canterbury.ac.nz/tad.takaoka/alg/spalgs/radixheap.txt

サンプル コード radixheap.cpp は次の場所にあります。

http://www.cosc.canterbury.ac.nz/tad.takaoka/alg/spalgs/spalgs.html

そのテキストがダイクストラのアルゴリズムについて説明しているように、同じデータ構造をプリムのアルゴリズムに適用するだけで、複雑さ O(m + n log C) を取得できます。ここで、m はエッジ、n は頂点、C は最大エッジの重みです。エッジの重みが小さい整数のみである場合、これは非常に優れています。

基数ヒープの概念を要約すると、アイテムは優先度 (整数でなければなりません) に従ってバケットに配置されます。バケット N がカバーする値の範囲は、おおよそ 2^N のサイズであるため、適切なバケットを見つけることは、可能な最大数の対数に比例します。優先度が最も低いアイテムを抽出すると、アイテムが下位のバケットに再分配されることがあり、償却も対数的複雑度になります。

エッジの重みが 0 から 1 の間の任意の浮動小数点数であることを意味している場合、それは最適化を許可しません。明らかに、すべてのエッジの重みを最大のエッジの重みで除算することで、すべてのグラフを変換して、すべてのエッジの重みを 0 から 1 にすることができます。結果をまったく変更せずに、すべてのエッジに同じ数を追加するか、同じ正の数を掛けることで、すべてのエッジを変換できます。

于 2012-04-29T19:47:14.137 に答える