KruskalおよびPrimのアルゴリズムのアプリケーション

Question

誰でも、2つのアルゴリズムのアプリケーションを提供してください。どこで、どのアプリケーションを使用できますか？

Answer 1

最小スパニングツリーは、配線の総コストを最小限に抑える方法で電気ネットワークをレイアウトする方法について最初に研究されました。最小スパニングツリーでは、すべてのノード（ハウス）が最小コストと冗長性を持つ方法でワイヤで電源に接続されます（ワイヤーを切ると、電源グリッドが2つのピースに削減されます）。

それ以来、問題はよく研究されており、より複雑なアルゴリズムのサブルーチンとしてよく使用されます。 Christofidesアルゴリズム 旅行セールスマンの問題に対するおおよそのソリューションを見つけるために、シュタイナーの木を見つけるためのいくつかのアルゴリズムと同様に、重要なステップでそれを使用します。

最小スパニングツリーも使用されています 迷路を生成します. 。 KruskalとPrimのアルゴリズムの両方がこの方法で使用されており、多くの場合、高品質の迷路を作成します。

最小スパニングツリーの問題、そのアプリケーション、およびそのアルゴリズムの完全な履歴に興味がある場合、本当に優れた論文があります こちらから入手できます これはこれらすべてをカバーしています。私はそれを読むことを強くお勧めします！

お役に立てれば！

Answer 2

ウィキペディアを引用：

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

ソース： http://en.wikipedia.org/wiki/minimum_spanning_tree

Answer 3

最初に、PrimとKruskalの両方のアルゴリズムが見つけるのに役立つことを理解する必要があります 最小スパニングツリー グラフで。最小限のスパニングツリーのプラチカルアプリケーションの1つは、同じ会社の異なるオフィスを最小コストで接続することです。

Answer 4

• トポロジー
• 地図作成
• ジオメトリ
• クラスタリング
• ルーティングアルゴリズム
• 迷路の生成
• 機械 /電気 /コンピューターネットワーク
• 化学における分子結合の研究

Answer 5

KruskalとPrimのアルゴリズムのアプリケーションは、多くの場合、コンピューターネットワーキングで発生します。たとえば、多くのスイッチを備えた大きなLANがある場合、最小のスパニングツリーを見つけることは、最小数のパケットのみがネットワーク全体に送信されるようにするために不可欠です。