2

重み付き無向グラフ G = (V,E) があるとします。各頂点には要素のリストがあります。

頂点ルートから開始し、値xを持つ要素のすべての出現を探し始めます。値xを持つ要素のすべての出現を明らかにするために、(エッジの重みに関して) 最小量の距離を移動したいと考えています。

私の考えでは、MST にはすべての頂点 (したがって、条件を満たすすべての頂点) が含まれます。したがって、すべてのオカレンスを明らかにするアルゴリズムは、ルートから他のすべての頂点への最短パスを見つけることで実行できます(これはもちろん MST で実行されます)。

編集: ルイが指摘したように、ルートが任意に選択された場合、MST はすべての場合に機能するとは限りません。ただし、明確にするために、ルートは入力の一部であるため、可能な MST は 1 つだけです (エッジの重みが異なる場合)。このスパニング ツリーには、ルートから始まるグラフ内の他のすべての頂点へのすべての最小コスト パスがあります。

4

4 に答える 4

4

これはうまくいかないと思います。次の例を検討してください。

 x
 |
 3
 |
 y--3--root
 |     /
 5    3
 |   /
 |  /
  x

最小全域木には重み 3 の 3 つのエッジがすべて含まれていますが、これは明らかに最適解ではありません。

私が問題を正しく理解していれば、x とラベル付けされたすべての頂点を含むグラフ内の最小重みツリーを見つける必要があります。(つまり、正解は重みの合計が 8 で、この図面で垂直に描かれた 2 つのエッジになります。) しかし、これには、任意に選択したルートはまったく含まれていません。

Prim のアルゴリズムの次のバリエーションが機能すると確信しています。ただし、それが最適かどうかはわかりません。

探しているラベルが L であるとしましょう。

  1. 全ペア最短経路アルゴリズムを使用して、すべての v、w について d(v, w) を計算します。
  2. L というラベルの付いたノードを選択します。これをルートと呼びます。(L とラベル付けされたすべてのノードが含まれているため、これが結果ツリーに含まれることは確実です。)
  3. 0 に初期化されたルートでプライオリティ キューを初期化します。
  4. プライオリティ キューが空でない場合は、次の操作を行います。
    1. キューの一番上の頂点を選択します。それを v と呼び、木からの距離を d とします。
    2. v からツリー (v を含む) までのパス上の各頂点 w について、w に最も近い L ラベル付きノード x を見つけ、x を優先度キューに追加するか、その優先度を更新します。ツリーに w を追加します。
于 2011-11-17T02:05:11.743 に答える
1

私が正しく理解していれば、答えはノーです。最小スパニング ツリーを見つけると、すべての頂点 V が含まれますが、値xを持つ頂点のみを見つけたいとします。したがって、MST の結果には余分なパスの長さを追加する不要な頂点があるため、最適ではない可能性があります。

于 2011-11-17T03:02:57.483 に答える
0

ルートからのMSTM1が、すべてのxノードを含むがルートを含まないMSTM2とは異なる例が示されています。

ルートが両方のMSTにある例を次に示します。グラフGにノードR、S、T、U、V（R =ルート）と時計回りのパスRSTUVRが含まれ、エッジの重みが1,1,3,2,2で時計回りになっているとします。 、およびxはR、S、T、Uにあります。最初のMSTであるM1には、Rの下にサブツリーSTとVUがあり、コストは6 = 2 + 4で、コスト3のエッジTUはM1に含まれていません。ただし、M2にはRの下にサブツリーSTU（のみ）があり、コストは5です。

于 2011-11-17T05:28:29.557 に答える
0

ネガティブ。「x」を含むすべてのノードについて、ルートからそのノードへの個別のパスを見つけ、パスの総コストを最小限に抑えることが目的である場合は、ルートから始まるすべてのノードに対して単純な最短パス計算を個別に使用できます。パスをまとめます。

これらの最短パスの一部は最小スパニング ツリーに含まれないため、これが目標である場合、MST ソリューションは機能しません。MST は、ルートからノードへのパスのコストの合計ではなく、ツリーのコストを最適化します。

ルートから始まり、「x」を含むすべてのノードを通過する1 つのパスを見つけることを考えている場合、これは巡回セールスマン問題であり、NP 完全最適化問題、つまり非常に難しい問題です。

于 2011-11-17T05:52:08.330 に答える