KruskalとPrimのアルゴリズムのアプリケーション

誰でも2つのアルゴリズムのどこのアプリケーションを使うことができますか？ウィキペディアを引用KruskalとPrimのアルゴリズムのアプリケーション

2011-09-06 vini

どこかへの参照が役に立ちます。 – Julian

配線の総コストを最小限に抑える方法で、電気ネットワークをレイアウトする方法について、最小限のスパニングツリーを最初に検討しました。最小限のスパニングツリーでは、すべてのノード（家屋）が最小のコストと冗長性を持つ方法で電線によって電力に接続されます（電線を切断すると必ず電力網が2つに切断されます）。

それ以来、問題は十分に研究されており、より複雑なアルゴリズムでサブルーチンとしてよく使用されています。旅行セールスマン問題の近似解を見つけるためのChristofides algorithmは、Steinerツリーを見つけるためのアルゴリズムと同様に、重要なステップでそれを使用します。

最小スパニングツリーもgenerate mazesに使用されています。 KruskalとPrimのアルゴリズムはどちらもこの方法で使用され、しばしば高品質な迷路を作成します。

あなたは最小全域木問題、その用途、およびそのアルゴリズムの完全な歴史に興味があるなら、これらのすべてをカバーし、真に優れた紙available hereがあります。私は強くそれを読むことをお勧めしたいと思います！

希望すると便利です。迷路の

出典

2011-09-06 17:18:46 templatetypedef

：

一つの例は、新しい近所にケーブルを敷設ケーブルテレビ会社になります。特定の経路に沿ってのみケーブルを埋設するように制約されている場合、それらの経路によってどの点が接続されているかを表すグラフが存在する。これらのパスの中には、ケーブルが長くなったり、ケーブルをより深く埋める必要があるため、高価なものがあります。これらの経路は、より大きな重みを有するエッジによって表される。そのグラフのスパニングツリーは、サイクルを持たずに各家につながっているパスのサブセットです。いくつかのスパニングツリーが存在する可能性があります。最小スパニングツリーは、総コストが最小のものになります。

出典：http://en.wikipedia.org/wiki/Minimum_spanning_tree

出典

2011-09-06 13:20:27 Simone

まず、プリムのとクラスカル法の両方がグラフでMinimum spanning Treeを見つけるために有用であることを理解する必要があります。最小限のスパニングツリーを使用するアプリケーションの1つとして、同じ会社の異なるオフィスを最小コストで接続することが考えられます。

出典

2011-09-06 13:27:10