23

重み付けされていない接続グラフがあります。特定のノード セットを確実に含み、エクストラをできるだけ少なくした、接続されたサブグラフを見つけたいと考えています。これはどのように達成できますか？

念のため、より正確な言葉を使用して質問を言い直します。G(V,E) を無向、無向、連結グラフとします。N を V の部分集合とします。N が V' の部分集合となるような G(V,E) の最小連結部分グラフ G'(V',E') を見つける最良の方法は何ですか?

近似は問題ありません。

4

4 に答える 4

12

これはまさによく知られている NP 困難なSteiner Tree問題です。インスタンスがどのように見えるかについての詳細がなければ、適切なアルゴリズムについてアドバイスすることは困難です.

于 2010-10-20T13:00:49.397 に答える
6

最適な解を見つけるための効率的なアルゴリズムは考えられませんが、入力グラフが密集していると仮定すると、次の方法で十分に機能する可能性があります。

  1. G(V, E)入力グラフを加重グラフに変換しますG'(N, D)。ここで、Nは対象とする頂点のサブセットでD、 は元のグラフの対応する頂点間の距離 (パスの長さ) です。これにより、必要のないすべての頂点がエッジに「折りたたまれます」。

  2. の最小スパニング ツリーを計算しG'ます。

  3. 次の手順で最小スパニング ツリーを「拡張」します。最小スパニング ツリーのすべてのエッジについてd、グラフ内の対応するパスを取得し、Gパス上のすべての頂点 (エンドポイントを含む) を結果セットに追加し、V'パス内のすべてのエッジを結果セットE'。

このアルゴリズムは簡単につまずいて、次善のソリューションを提供します。例: 角、辺の中点、および三角形の中央に頂点があり、辺に沿って、角から三角形の中央までのエッジがある正三角形。角をカバーするには、三角形の 1 つの中間点を選択するだけで十分ですが、このアルゴリズムは辺を選択する可能性があります。それでも、グラフが密集している場合は問題なく動作するはずです。

于 2010-10-20T08:25:01.353 に答える
5

最も簡単な解決策は次のとおりです。

a）mstに基づく：-最初は、VのすべてのノードがV'にあります-グラフG（V、E）の最小全域木を構築します-それをTと呼びます。-
ループ：Tにないすべてのリーフvに対してN、V'からvを削除します。
-Tのすべての葉がNになるまでループを繰り返します。

b）別の解決策は次のとおりです-最短経路ツリーに基づいています。
-N内の任意のノードを選択し、それをvと呼び、vをツリーのルートT={v}とします。-Nからvを削除します。

  • ループ：1）Tの任意のノードとNの任意のノードから最短経路を選択します。最短経路p：{v、...、u}ここで、vはTにあり、uはNにあります。2）pのすべてのノードV'に追加されます。3）pとNのすべてのノードがNから削除されます。---Nが空になるまでループを繰り返します。

アルゴリズムの開始時：既知の効率的なアルゴリズムを使用して、Gのすべての最短経路を計算します。

個人的には、このアルゴリズムを私の論文の1つで使用しましたが、分散環境に適しています。Nを相互接続する必要のあるノードのセットとします。グラフGの最小接続支配集合を構築し、Nのノードに優先順位を付けます。各ノードに一意の識別子id（u）を与えます。uがNの場合はw（u）= 0とし、そうでない場合はw（1）とします。ノードuごとにペア（w（u）、id（u））を作成します。

  • 各ノードuは、マルチセットリレーノードを構築します。つまり、各2ホップネイバーがM（u）の少なくとも1つのノードのネイバーになるような1ホップネイバーのセットM（u）です。[最小のM（u）、より良い解決策]。

  • uは、次の場合にのみV'になります。uがすべての隣接ノードの中で最小のペア（w（u）、id（u））を持っている場合。または、M（v）でuが選択されます。ここで、vは、最小（w（u）、id（u））のuの1ホップネイバーです。

-このアルゴリズムを一元的に実行する場合の秘訣は、2ホップネイバーの計算を効率的に行うことです。O（n ^ 3）から得られる最善の方法は、行列の乗算によってO（n ^ 2.37）を取得することです。

-私は本当にこの最後の解決策の近似比が何であるか知りたいです。

シュタイナー木のヒューリスティックに関するこのリファレンスが好きです。シュタイナー木問題、ファンフランク; リチャーズ・ダナ1955-ウィンター・パヴェル1952

于 2012-09-04T02:44:00.573 に答える
2

次のことを試みることができます。

  1. 目的のノードの最小限の頂点カバーを作成しますN。

  2. これらの、おそらく接続されていないサブグラフを「大きな」ノードに折りたたみます。つまり、サブグラフごとにグラフから削除し、新しいノードに置き換えます。この一連のノードを呼び出しN'ます。

  3. のノードの最小限の頂点カバーを実行しN'ます。

  4. のノードを「開梱」しN'ます。

特定の範囲内で近似値が得られるかどうかはわかりません。アルゴリズムをだまして、本当にばかげた決定を下すことさえできるかもしれません。

于 2010-10-20T07:58:02.667 に答える