c++ - 最速の最小スパニング ツリー アルゴリズム

Question

http://en.wikipedia.org/wiki/Minimum_spanning_tree

最小スパニング ツリー アルゴリズムを最高のものと比較してベンチマークすることを検討しています。これらのアルゴリズムの C++ 実装がどこにあるか知っている人はいますか? 私はどんちゃん騒ぎしてグーグルで検索しましたが、何も見つかりませんでした。これらのアルゴリズムが最高の場合、C++ の実装がどこかにあるに違いありません。

これまでで最速の最小スパニング ツリー アルゴリズムは、David Karger、Philip Klein、Robert Tarjan によって開発され、Borůvka のアルゴリズムと逆削除アルゴリズムの組み合わせに基づく線形時間ランダム化アルゴリズムを発見しました.[2][3] Bernard Chazelle による最速の非ランダム化アルゴリズムは、おおよその優先順位キューであるソフト ヒープに基づいています。[4][5] その実行時間は O(m α(m,n)) です。ここで、m はエッジの数、n は頂点の数、α はアッカーマン関数の古典的な逆関数です。関数 α は非常にゆっくりと成長するため、すべての実用的な目的では、4 を超えない定数と見なすことができます。したがって、チャゼルのアルゴリズムは線形時間に非常に近くなります。エッジの重みがビット長が制限された整数の場合、次に、実行時間が線形である決定論的アルゴリズムが知られています[6]。一般的な重みの実行時間が線形である決定論的アルゴリズムが存在するかどうかは、まだ未解決の問題です。しかし、Seth Petie と Vijaya Ramachandran は、証明可能な最適な決定論的最小スパニング ツリー アルゴリズムを発見しましたが、その計算の複雑さは不明です [7]。

私はすでに Boost C++ のグラフ アルゴリズムに対してテストを行っています。

Answer 1

ウィキペディアのページに「最速の最小スパニング ツリー アルゴリズム」と書かれている場合、それが意味するのは、最小の漸近境界を持つアルゴリズムです。この場合、O(m α(m,n)) で、m、n、α が定義されています。あなたが貼り付けた引用のように。簡単に言えば、これは、入力値が非常に大きい場合、C のある値に対して、かかる時間は常に C*m*α(m,n) によって制限されることを意味します。ただし、C は非常に大きくなる可能性があることに注意してください。このアルゴリズムは、入力値が非常に大きい場合は他のアルゴリズムよりも高速ですが、小さい入力値に適用すると他のアルゴリズムよりも遅くなる可能性があります。

2 つのアルゴリズムの漸近境界を比較する場合、どちらが速いかを確認する「テスト」はありません。各アルゴリズムの漸近境界を証明し、どちらが低いかを確認するだけです。(「漸近的」とは、入力サイズが無限大になるときの動作を指します。また、無限サイズの入力値でテストを実行するのは困難です。)

ただし、漸近的に最速のアルゴリズムを使用しない場合があることに注意してください。「C」が非常に大きい場合は、より小さなデータ値に対してより単純なアルゴリズムを使用する方がよい場合があります。

私の推測では、アルゴリズムは C で改善される可能性がありますが、漸近境界では改善されない可能性があります。しかし、私がそれについて間違っている場合は、ACM に提出する必要があります。

詳細については、http: //en.wikipedia.org/wiki/Big_O_notationを参照してください。

Answer 2

「ソート、ヒープ、および最小スパニング ツリーについて」、Gonzalo Navarro および Rodrigo Paredes

コア内および外部メモリの測定結果の「ベスト オブ ザ ベスト」を示し、古い実装への参照を提供します。

I/O の数と CPU 時間をグラフ サイズの関数として報告し、テスト ケースを適切に説明しているため、原則として、テストを実行して、公開されているグラフと比較することができます。Prim2 リファレンス (多くの高速コードを自由に利用できるようにしている Peter Sanders のコード) を使用して、独自の測定値を調整できます。