誰かが2つのアルゴリズムのいくつかのアプリケーション、それらを使用できる場所とアプリケーションを教えてもらえますか？
40767 次
6 に答える
20
配線の総コストを最小化する方法で電気ネットワークをレイアウトする方法について、最小全域木が最初に研究されました。最小スパニングツリーでは、すべてのノード（住宅）は、最小のコストと冗長性を備えた方法でワイヤーによって電力に接続されます（ワイヤーを切断すると、必然的に電力網が2つに切断されます）。
それ以来、この問題は十分に研究されており、より複雑なアルゴリズムのサブルーチンとしてよく使用されています。巡回セールスマン問題の近似解を見つけるためのクリストフィードのアルゴリズムは、シュタイナー木を見つけるためのいくつかのアルゴリズムと同様に、重要なステップでそれを使用します。
迷路を生成するために、最小全域木も使用されています。クラスカル法とプリム法の両方のアルゴリズムがこのように使用されており、多くの場合、高品質の迷路が作成されます。
最小スパニングツリーの問題、そのアプリケーション、およびそのアルゴリズムの完全な履歴に興味がある場合は、これらすべてをカバーする本当に優れた論文がここにあります。ぜひお読みください。
お役に立てれば！
于 2011-09-06T17:18:46.370 に答える
4
ウィキペディアの引用：
一例として、ケーブルテレビ会社が新しい近所にケーブルを敷設します。特定のパスに沿ってのみケーブルを埋めるように制約されている場合、それらのパスによって接続されているポイントを表すグラフが表示されます。これらのパスのいくつかは、長いため、またはケーブルをより深く埋める必要があるため、より高価になる可能性があります。これらのパスは、より大きな重みを持つエッジで表されます。そのグラフのスパニングツリーは、サイクルがないがすべての家に接続しているパスのサブセットになります。可能なスパニングツリーがいくつかある可能性があります。最小スパニングツリーは、総コストが最も低いものになります。
于 2011-09-06T13:20:27.797 に答える
1
まず、プリム法とクラスカル法の両方のアルゴリズムが、グラフ内の最小全域木を見つけるのに役立つことを理解する必要があります。最小スパニングツリーの実用的なアプリケーションの1つは、同じ会社の異なるオフィスを最小のコストで接続することです。
于 2011-09-06T13:27:10.557 に答える
1
PrimsアルゴリズムとKruskalアルゴリズムの両方を使用して、最小全域木を見つけます。現在、クラスカル法とプリム法のアプリケーションは、基本的にMSTのアプリケーションです。では、MSTのアプリケーションは何ですか？
さて、いくつか答えるために、ここにあなたがそれらを使用できると思ういくつかの分野があります：
- 高速道路または鉄道ネットワークを使用して複数の都市を接続する場合は、これらのアルゴを使用して、これらすべての都市を接続する道路/鉄道の最小の長さを見つけることができます。
- ネットワーク設計-複数のオフィスを持つビジネスがあるとします。これらすべてのオフィスを接続するには、電話ケーブルをリースする必要があります。したがって、これらのアルゴを利用して、電話ケーブルの使用を最小限に抑えてすべてのオフィスを接続するための最小コストを調べることができます。
- 巡回セールスマン問題を見つけるために使用できます。これは、MSTを使用する非常に有名な問題です。
- 電力、電話回線、下水道などの家のセットを適用したいとします。
- ローカルエリアネットワークの設計。
于 2019-11-24T19:27:01.397 に答える
0
- トポロジー
- 地図作成
- ジオメトリ
- クラスタリング
- ルーティングアルゴリズム
- 迷路の生成
- 機械/電気/コンピュータネットワーク
- 化学における分子結合の研究
于 2012-06-09T10:19:21.320 に答える
0
クラスカル法とプリム法のアルゴリズムのアプリケーションは、多くの場合、コンピューターネットワーキングで登場します。たとえば、多数のスイッチを備えた大規模なLANがある場合、最小数のパケットのみがネットワークを介して送信されるようにするには、最小スパニングツリーを見つけることが重要です。
于 2014-11-08T15:21:34.510 に答える