7

プリムのアルゴリズムまたはクラスカルのアルゴリズムを使用して、頂点/ノードおよびエッジ/リンクのコレクションの最小全域木/グラフを見つけることができます。私が欲しいのは、このコレクションの最小スパニンググラフを見つけるアルゴリズムですが、結果のグラフには、すべてのノードではなく、任意に選択されたノードのみを含める必要があります。結果のグラフに、必要なノードよりも多くのノードが含まれていても問題ありません。

そのようなアルゴリズムは存在しますか？おそらく、必要なノードのみを含むようにグラフを変更した後、プリム（またはクラスカル）アルゴリズムを使用することができますか？しかし、接続性を維持しながらグラフを変更する方法がわかりません。

たとえば、ひし形の開始グラフ（括弧内のリンクのコストを含む）があるとします。

    A
(2)/ \(1)
  B   C
(2)\ /(5)
    D

ここで、ノードAとDのみが必要であると任意に決定します。Aから始めた場合でも、（（2 + 2）<（1 + 5））であるため、左側のパスを使用する必要があります。

グラフを少し変更するとします。

    A
(2)/ \(1) (2)
  B   C ------E
(2)\ /(5)
    D

ノードA、D、およびEのみが必要であると判断した場合、最小コストのパスが必ずしもリンク数が最も少ないパスであるとは限らないことがわかります。A--B--DとA--C--Eの費用は7ですが、A--C--DとC--Eの費用は8です。

4

1 に答える 1

7

求めたいのは、離散シュタイナー木です。グラフのすべての頂点が必須ではなく、オプションの頂点でツリーを分割できる場合、問題は NP 困難です。

ウィキペディア (上記リンク) は、この問題について次のように述べています。一般に、多項式時間では、任意に適切な近似比を達成することはできないと考えられています。最小シュタイナー ツリーの係数 1.39 近似を求める多項式時間アルゴリズムがあります。

于 2012-10-30T20:04:00.173 に答える