8

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

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

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

編集

より一般的な説明：グラフG（V、E）が与えられた場合、Gにv1からv2へのパスが存在する場合、Gにv1とv2の間にパスが存在するように、グラフG'（V、E'）を見つけます。 'およびE'の各eiの合計は可能な限り最小です。したがって、最小の同等のグラフを見つけるのと似ていますが、ここでのみ、エッジの合計ではなく、エッジの重みの合計を最小化します。

編集：

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

4

7 に答える 7

12

あなたの問題は最小スパニングストロングサブ（ディ）グラフ（MSSS）、またはより一般的には最小コストスパニングサブ（ディ）グラフとして知られており、確かにNPハードです。別の本も参照してください: 501ページと480 ページ。

三角形の不等式を満たさないすべてのエッジを削除することから始めます。a -> b -> c の方が安価な場合は、エッジ a -> c を削除できます。これは TSP を思い出させますが、それがどこにつながるかはわかりません。

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

于 2009-10-10T20:14:31.623 に答える
2

動的プログラミングのような方法でこれを試してみます。

0 - グラフをリストに入れる

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

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

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

4- 新しいリストの最良のグラフを現在の最良のグラフと比較し、より良い場合は、新しい現在の最良のグラフを設定します

5- 新しいリストが空の場合、現在のベストがソリューションです。それ以外の場合は、再帰/ループ/goto 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、読者の演習として残されています。

于 2009-10-08T08:30:27.980 に答える
1

この問題は、ここで説明されている問題と同等です：http: //www.facebook.com/careers/puzzles.php?puzzle_id=1

于 2010-01-04T19:40:36.550 に答える
1

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

前処理ステップ:

  1. プルーニング: より安価なエッジまたは同じコストパスがある場合は、すべてのエッジ ab を削除します(例: acb)。

  2. グラフの分解: グラフに分節点がある場合、副問題を解決できます

  3. 出力エッジが 1 つしかない場合は、頂点を 1 つの仮想頂点にマージします。

計算ステップ:

  1. 訪問を繰り返して指示された TSP を使用して近似解を取得します。Floyd Warshall を使用してから、代入問題 O(N^3) をハンガリー法で解きます。サイクルが 1 回である場合は、TSP ソリューションを使用します。そうでない場合は、分岐とバインドされた TSP を使用します。その後、上限値、つまり最小コストのサイクルがあります。

  2. 正確な解決策 - 分岐限定アプローチ。最短サイクルから頂点を取り除き、上限よりも少ないコストで強連結グラフを構築しようとします。

それはすべての人々です。ソリューションをテストしたい場合は、こちらで試してください: http://codercharts.com/puzzle/caribbean-salesman

于 2012-05-31T14:15:48.337 に答える
0

基本的に必要なのは、ノードを複数回訪問することが許可されている巡回セールスマンにとって最適なソリューションのようです。

編集：

うーん。基本的に各ノードiを反復処理し、そのノードiを指すすべてのエッジの最小スパニングツリーを実行し、そのノードから離れる方向を指すすべてのエッジの別の最小スパニングツリーと結合することでこれを解決できますか？

于 2009-10-08T07:12:50.960 に答える
0

ダイクストラアルゴリズムを使用したいようです

于 2009-10-08T07:17:38.060 に答える