12

0からU-1までの範囲の非負の整数エッジ長を持つ有向グラフがあるとします。このグラフの最小全域木を計算するための最速のアルゴリズムは何ですか？クラスカルのアルゴリズムO（m log n））やプリムのアルゴリズム（O（m + n log n））など、既存の最小スパニングツリーアルゴリズムを引き続き使用できます。ただし、Uが小さい場合は、もっとうまくできるはずだと思います。

エッジの長さが一定の範囲に制限されているという事実を利用できる、従来のMSTアルゴリズムと競合するアルゴリズムはありますか？

ありがとう！

4

2 に答える 2

9

Fredman–Willardは、ユニットコストRAMの整数エッジ長に対してO（m + n）アルゴリズムを提供しました。

これはおそらくそれほど改善されていません。エッジの長さに制限がない場合（つまり、長さは比較のみをサポートする不透明（OPAQUE）型）、ChazelleはO（m alpha（m、n）+ n）アルゴリズムを提供しました（alphaは逆アッカーマン関数）とKarger–Klein–Tarjanは、ランダム化されたO（m + n）アルゴリズムを提供しました。

ダレンのアイデアがO（m + n + U）時間アルゴリズムにつながるとは思いません。Jarnik（ "Prim"）は優先キューを単調に使用しないため、バケットは複数回スキャンされる可能性があります。クラスカル法は素集合データ構造を必要としますが、これはO（m + n）にすることはできません。

于 2012-01-16T18:22:44.683 に答える
4

O(1)整数のエッジウェイトを使用すると、バケットを使用して、最悪の場合の複雑さで優先キューを実現できますが、O(U)スペースの複雑さが増します。

あなたが言及したMSTアルゴリズム内で、比較ベースの優先度キューをこの整数構造に置き換えることができるはずです。したがってO(log(n))、複雑さの要件の依存性を取り除くことができます。のスタイルは全体的に複雑になると思いますO(n + m)。

基本的に、圧縮されたリンクリストのセットを設定します。各リストは、そのバケットに関連付けられた（整数！）コストによってインデックスが付けられます。

struct bucket_list
{
    _cost; // array[0..N-1] holding current cost for each item

    _head; // array[0..U-1] holding index of first item in each bucket

    _next; // array[0..N-1] where _next[i] is the next item 
           // in a list for the ith item

    _prev; // array[0..N-1] where _prev[i] is the last item 
           // in a list for the ith item
};

この構造は、各アイテムが一度に1つのバケットリストにしか存在できないという事実に基づいています。

この構造に基づいて、これらの操作の最悪の場合のO(1)複雑さを実現できます。

push(item, cost); // push an item onto the head of the appropriate bucket list

_pop(item, cost); // _pop an item from (anywhere!) within a bucket list

update(item, old_cost, new_cost); // move an item between buckets by combining
                                  // push and _pop

この構造を優先キューとして使用するには、スキャンする現在の最小バケットを指すインデックスを維持するだけです。次に低コストのアイテムを取得したい場合は、このバケットからヘッドアイテムをポップするだけです。バケットが空の場合は、空でないバケットインデックスが見つかるまでバケットインデックスをインクリメントします。

もちろん、Uスペースが非常に複雑になり、バケット全体にアイテムがまばらに分散する可能性がある場合、この種のアプローチは魅力的ではなくなる可能性があります。

于 2012-01-16T00:39:09.767 に答える