最小コストの強接続有向グラフ

https://stackoverflow.com/questions/1536067

20-09-2019
|

質問

強く結びついた有向グラフがあります（すなわち、グラフ G) のノードの各ペア (i, j) には、i から j へ、および j から i へのパスがあります。このグラフの中から、すべてのエッジの合計が最小になるような強く接続されたグラフを見つけたいと考えています。

言い換えると、エッジを削除した後も、グラフが強く接続され、エッジの合計のコストが最小になるような方法でエッジを削除する必要があります。

NP の難しい問題だと思います。20 ノードのような小さなデータセットに対して、近似ではなく最適なソリューションを探しています。

編集

より一般的な説明:グラフ G(V,E) が与えられた場合、G に v1 から v2 へのパスが存在する場合、G' には v1 と v2 の間にパスが存在し、それぞれの合計が存在するようなグラフ G'(V,E') を見つけます。 E' の ei は可能な限り最小です。したがって、最小の等価グラフを見つけるのと似ていますが、ここではエッジの合計ではなくエッジの重みの合計を最小化する必要があるだけです。

編集：

これまでの私のアプローチ:複数回の訪問でTSPを使用して解決しようと考えましたが、それは正しくありません。ここでの私の目標は、最小コストのパスを使用して各都市をカバーすることです。つまり、カバーセットの問題に近いのではないかと思いますが、正確にはわかりません。総コストが最小となるパスを使用してすべての都市をカバーする必要があるため、すでに訪問したパスを複数回訪問してもコストは追加されません。

解決

あなたの問題は次のように知られています 最小スパンの強力なサブ(ディ)グラフ (MSSS)、またはより一般的には、サブ(ダイ)グラフにまたがる最小コストであり、確かにNP難しい. 。別の本も参照してください。 501ページそして 480ページ.

まず、三角不等式を満たさないすべてのエッジを削除します。a -> b -> c の方がコストが安い場合は、エッジ a -> c を削除できます。これを聞くと TSP を思い出しますが、それが何かにつながるかどうかはわかりません。

私の以前の答えは、 Chu-Liu/Edmonds アルゴリズムどれが解決しますか樹木状問題;Kazoom と ShreevatsaR が指摘したように、これは役に立ちません。

他のヒント

私は道の動的なプログラミング種類でこれをしようとするだろう。

0-リストにグラフを置く

1-新しいサブグラフごとに一つの異なるエッジを削除する前のリスト、各グラフの新しいサブグラフのリストを作る。

2-新しいリストから重複を削除

、3-強く接続されていない新しいリストからすべてのグラフを削除する

4-良くならば、

新しい現在のベストを設定し、現在最高で、新しいリストから最高のグラフを比較します

5新しいリストが空の場合、現在の最高はそれ以外の場合は、再帰/ループ/後藤1

、ソリューションです。

Lispでは、それはおそらく、このようになります：

(defun best-subgraph (digraphs &optional (current-best (best digraphs)))
  (let* ((new-list (remove-if-not #'strongly-connected
                                  (remove-duplicates (list-subgraphs-1 digraphs)
                                                     :test #'digraph-equal)))
         (this-best (best (cons current-best new-list))))
    (if (null new-list)
        this-best
        (best-subgraph new-list this-best))))

strongly-connected、list-subgraphs-1、digraph-equal、best、及びbetterの定義は、読者のための課題として残されている。

ます。http：// WWW

この問題は、ここで説明した問題と等価です.facebook.com /キャリア/ puzzles.php？puzzle_id = 1 の

有名なフェイスブルパズルを解くのに役立ったいくつかのアイデア:

前処理ステップ:

剪定:安いものや持っているものがある場合は、すべてのエッジ a ～ b を削除します。 同じコスト パス、たとえば:a-c-b。
グラフの分解:グラフに関節点がある場合は部分問題を解決できます
出力エッジが 1 つしかない場合は、頂点を 1 つの仮想頂点にマージします。

計算ステップ:

繰り返し訪問して、有向 TSP を使用して近似解を取得します。Floyd Warshall を使用し、ハンガリアン法を使用して割り当て問題 O(N^3) を解きます。1 回のサイクルを取得した場合は、ダイレクト TSP ソリューションです。そうでない場合は、分岐およびバインドされた TSP を使用します。その後、上限値、つまり最小コストのサイクルが決まります。
正確な解決策 - 分岐限定アプローチ。最短サイクルから頂点を削除し、上限よりも低いコストで強く接続されたグラフの構築を試みます。

以上です。ソリューションをテストしたい場合は、ここで試してみてください。 http://codercharts.com/puzzle/caribbean-salesman

あなたはダイクストラアルゴリズムの

あなたは基本的にしたいことは、それが複数回訪問するノードに対して許可されている走行セールスマンのための最適なソリューションであるように、

に思えます。

編集ます：

うーん。あなたは私が離れての指しているすべてのエッジの別の最小スパニングツリーでUNION句、基本的に私は、各ノードを反復処理し、のへの指しているすべてのエッジの最小スパニングツリーを実行して、そのノードをこの問題を解決することができをそのノードから？

の 2 近似 最小の強接続部分グラフ は、最小の内部分岐と最小の外部分岐の結合を取得することによって取得されます。両方とも同じ (ただし任意の) 頂点をルートとします。

アン 外分岐, 、としても知られている樹木状の, 、すべての頂点にまたがる単一の頂点をルートとする有向ツリーです。イン分岐は逆エッジでも同様です。これらは次の方法で見つけることができますエドモンズのアルゴリズム時間内に O(VE), 、高速化があります O(Eログ(V)) (を参照してください。ウィキページ）。さえありますオープンソースの実装.

2 近似結果の元の参照は、 JaJa と Frederickson による論文, しかし、この論文は自由にアクセスできるわけではありません。

エイドリアン・ベッタによる 3/2 の近似もあります (PDF), ただし、上記よりも複雑です。

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow