0

入力ファイルがあるとします。

<total vertices>
<x-coordinate 1st location><y-coordinate 1st location>
<x-coordinate 2nd location><y-coordinate 2nd location>
<x-coordinate 3rd location><y-coordinate 3rd location>
...

Prim のアルゴリズムを使用して、これらの場所の MST を見つけるにはどうすればよいでしょうか? この問題は通常、隣接行列を使用して解決されることを理解しています。該当する場合は、すべての参照が素晴らしいでしょう。

4

2 に答える 2

0

Prim のいくつかの実装について説明するだけで、うまくいけば、どこかに到達できることを願っています。

まず、あなたの質問は、エッジがプログラムにどのように入力されるかを指定していません。頂点の総数とそれらの頂点の位置があります。どれが接続されているかをどうやって知るのですか？

エッジ (およびそれらのエッジの重み。@doomster が上で述べたように、ポイントは座標であるため、ポイント間の平面距離である可能性があります) があると仮定すると、実装について考え始めることができます。ウィキペディアでは、3 つの異なる実行時間になる 3 つの異なるデータ構造について説明しています: http://en.wikipedia.org/wiki/Prim 's_algorithm#Time_complexity

最も単純なのは隣接行列です。名前から推測できるように、マトリックスは「隣接する」ノードを表します。正確には、|v|行と列があります (|v|は頂点の数です)。at の値adjacencyMatrix[i][j]は使用状況によって異なります。私たちの場合、それはノードiとノードの間のエッジの重み (つまり、距離)jです (これは、何らかの方法で頂点にインデックスを付ける必要があることを意味します。たとえば、頂点をリストに追加し、リスト内の位置を使用する場合があります)。 .

この隣接行列を使用すると、アルゴリズムは次のようになります。

  1. すべての頂点を含み、「距離」をキーとするディクショナリを作成します。最初は、すべてのノードの距離は無限大です。
  2. 「親」を追跡するために別の辞書を作成します。これを使用して MST を生成します。エッジを追跡する方が自然ですが、実際には「親」を追跡することで実装が簡単になります。ツリーをルート化する (つまり、あるノードをルートとして指定する) 場合、すべてのノード (ルートを除く) は正確に 1 つの親を持つことに注意してください。したがって、この親の辞書を作成することで、MST を取得できます。
  3. 元のリストからランダムに選択されたノードで新しいリストを作成しますv。
    1. 距離ディクショナリから削除vし、null を親として親ディクショナリに追加します (つまり、「ルート」です)。
    2. そのノードの隣接行列の行を調べます。接続されているノードw(接続されていないノードの場合は、隣接行列の値を特別な値 (0、-1、int最大など) に設定する必要があります) に対して、辞書内の「距離」を に更新しadjacencyMatrix[v][w]ます。アイデアは、もはや「無限に遠く」ではないということですv....
  4. ディクショナリが空でない間 (つまり、まだ接続する必要があるノードがある間)
    1. 辞書を調べて、距離が最小の頂点を見つけますx
    2. 頂点の新しいリストに追加します
    3. 隣接するそれぞれについて、それらの距離を にmin(adjacencyMatrix[x][neighbor], distance[neighbor])更新し、親も に更新しxます。基本的に、到達するためのより高速な方法がある場合は、neighborそれを反映するように距離辞書を更新する必要があります。次に、新しいリストに追加neighborすると、実際に追加したエッジがわかります (親ディクショナリには、その親が であると記載されているためx)。
  5. 終わったね。必要に応じて MST を出力します (必要なものはすべて親辞書に含まれています)。

上記で概説したように、ウィキペディアのページから実際の実装に少し飛躍があることは認めます。このギャップにアプローチする最善の方法は、コードをブルート フォースすることだと思います。つまり、疑似コードが「[foo] が true となる最小 [blah] を見つける」と言う場合、それを実行するために必要なコードを記述し、それを別のメソッドに貼り付けます。それは間違いなく非効率的ですが、有効な実装になります。グラフ アルゴリズムの問​​題は、それらを実装する方法が 30 あり、すべてパフォーマンスが大きく異なることです。ウィキペディアのページでは、アルゴリズムを概念的にしか説明できません。良いことは、それを実装すると、そうすることで、最適化をすばやく見つけることができます (「ああ、この別のデータ構造でこの状態を追跡できれば、このルックアップをより高速に行うことができます!」)。ちなみに、これの実行時間はO(|V|^2). 私はその分析を詳述するのが面倒ですが、おおよその理由は次のとおりです。

  1. すべての初期化がO(|V|)悪化しています
  2. ループO(|V|)時間を実行O(|V|)し、ディクショナリを調べて最小ノードを見つけます。したがって、基本的に、最小ノードを複数回見つけるための合計時間はO(|V|^2)です。
  3. 距離ディクショナリの更新にかかる時間は、O(|E|)各エッジを 1 回しか処理しないためです。これも|E|あるからO(|V|^2)O(|V|^2)
  4. 親を追跡することは、O(|V|)
  5. ツリーの出力はO(|V| + |E|) = O(|E|)最悪です
  6. これらをすべて加算すると ((2) 内を除いて、どれも乗算してはいけません)、次のようになります。O(|V|^2)

ヒープを使用した実装はO(|E|log(|V|)、上記と非常によく似ています。唯一の違いは、距離の更新は(ヒープであるため)ではなく、最小要素の検索/削除はO(log|V|)(O(1)ヒープであるため) ではないことです。時間の複雑さは分析でも非常に似ており、最終的には希望どおりの結果が得られます。O(log|V|)O(|V|)O(|V|log|V| + |E|log|V|) = O(|E|log|V|)

実際...隣接行列の実装が隣接行列であることを気にする理由が少し混乱しています。隣接リストを使用して実装することもできます。重要な部分は、距離をどのように保存するかだと思います。上記で概説した私の実装ではかなりずれている可能性がありますが、Prim のアルゴリズムを実装することは、ウィキペディアで概説されている時間の複雑さの制約を満たしていると確信しています。

于 2013-04-14T12:14:09.123 に答える
0

すでに prim を知っていれば簡単です。隣接行列を作成する adj[i][j] = 位置 i と位置 j の間の距離

于 2013-04-14T06:22:57.600 に答える