問題タブ [minimum-cut]

重み付けされた連結グラフが与えられたとします。グラフから削除できるエッジのリストを見つけて、グラフを 2 つのコンポーネントに分割し、削除されたエッジの重みの合計が小さくなるようにしたいと考えています。理想的には、最小の合計を取得したいのですが、妥当な概算で解決します。

これは難しい問題のようです。これを行うための適切なアルゴリズムはありますか?

それが役立つ場合、私の場合、ノードの数は約 50 であり、グラフは密集している可能性があるため、ほとんどのノードのペアはそれらの間にエッジがあります。

スパニングツリーとカットは密接に関連していることはすでに見てきました。これが別の接続です。クラスカルのアルゴリズムがスパニングツリーに追加する最後のエッジを削除しましょう。これにより、ツリーが2つのコンポーネントに分割され、グラフにカット（S、S）が定義されます。このカットについて何が言えますか？使用しているグラフが重み付けされておらず、クラスカルのアルゴリズムがそれらを処理するために、そのエッジがランダムに均一に順序付けられていると仮定します。ここに注目すべき事実があります。少なくとも1/n ^ 2の確率で、（S、S）はグラフの最小カットであり、カットのサイズ（S、S）はSとSの間で交差するエッジの数です。これは、プロセスをO（n ^ 2）回繰り返し、見つかった最小カットを出力すると、Gの最小カットが高い確率で生成されることを意味します。重み付けされていない最小カットのO（mn ^ 2 log n）アルゴリズムです。

• これは、クラスカルのアルゴリズムを使用してグラフを処理するためのn ^ 2のユニークな方法があるという事実に依存しませんか？つまり、クラスカルのアルゴリズムが10ノードのグラフを処理するための3つの固有の方法しかない場合、この処理をn ^ 2回繰り返しても、n^2の固有の「最後のエッジ」は生成されません。一意の最終カットがn^2未満（つまり、一意の「最後のエッジ」がn ^ 2未満）のシナリオでは、どのように機能しますか？

• 合計でn^2未満のエッジがある場合はどうなりますか？たとえば、9つのエッジしかない10個のノードの連結グラフを作成できます。つまり、アルゴリズムを何度繰り返しても、n^2個の一意の「最後のエッジ」はありません。この状況でどのように機能しますか？

• すべてのエッジをループして、エッジが最小カットであるかどうかを確認する方が簡単ではないでしょうか。nノードのグラフでは、一意のエッジの最大数はn + n-1 + n-2 ... + 1エッジであり、n^2未満です。また、n^2がn^2 log n未満であることを考慮すると、これが高速であるため、すべてのエッジをループするだけではどうでしょうか。

ネットワーク G=(V,E) 、最大フロー f 、および E のエッジ e が与えられた場合、e を含む最小カットがあるかどうかを検出するために、efficeint アルゴリズムを見つける必要があります。別の質問は、e がいくつかの最小カットに含まれていることがわかった場合、それがカット全体の最も軽いエッジであるかどうかを検出することは可能ですか?

Ford-Fulkerson アルゴリズムを実行し、指定されたエッジの容量を増減して何が起こるかを確認することを考えましたが、問題の解決に役立つ可能性のあるものは思いつきませんでした。

誰かが私に解決策を教えてくれたらうれしいです。よろしくお願いします。

私はしばらくの間、これを修正しようと取り組んでいます。実際にはかなりの数週間が経ちましたが、可能な解決策や修正を使い果たしました。したがって、アルゴリズムは Randomized Karger Minimum Cut Algorithm であり、私の実装は以下のとおりです。

アルゴリズム：

無向グラフ用です。各頂点はハッシュマップのキーとして保存され、隣接する頂点はハッシュマップの値の配列リストとして保存されるため、たとえば

テスト ケースが次の場合:

ここで、最初の列はキーであり、それらに隣接する数字はその値 (arraylist) です。

私のアルゴリズムは

1. 2 つ以上の隣接する頂点 (この場合は 2 つ) を持つ "i" と呼ばれる最初に発生する頂点を選択します。
2. 「i」のリストに2つ以上の数字がある間
3. 「U」と呼ばれる隣接する頂点をランダムに選択します
4. 「U」と「i」を合体（「V」という別の頂点と合体させても正解にはなりません）
5. 新しい「i」のリストが「i」自体で構成されているかどうかを確認し、それを削除します。(セルフループ)
6. 新しい「i」のリストを他の頂点に相互参照する

7. 「U」(キー) を削除します。たとえば、「U」が 6 の場合、更新された頂点は次のようになります。

   /li>

8. したがって、「i」が一意の番号を持つ場合、アルゴリズムは終了します (「i」のリストを Set に追加することによって行われます)。例：

   /li>

したがって、これは、特定のグラフの 2 つの最小カットです。

コード：

上記の Java アルゴリズムのコードは次のとおりです。

問題：

私が直面している問題は、このアルゴリズムが、200 個の頂点からなる 1 つの非常に大きなテスト ケースを除いて、私が遭遇したほぼすべてのテスト ケースで完全に機能することです。正解は 17 のはずですが、「20」と答え続けます。選択したすべての「U」を追跡しました。どうやらそれらはすべて重複せずに一意であり、「20」という答えが得られ続けています。アドバイスをお願いします。もう一度ありがとう。テストケースへのリンクは次のとおりです。

http://spark-public.s3.amazonaws.com/algo1/programming_prob/kargerMinCut.txt

注意:

これは宿題ではなく、coursera のオンライン コース (アルゴリズムの設計と分析) で見た練習問題です。これでコースは終了です。事前にどうもありがとうございました。最初に答えを得ることができなかったので、この質問をもう一度します。私はかなり長い間それに取り組んできたので、この質問が私に負担をかけていると言ったので、提供された助けに感謝します.

Karger のアルゴリズムを実装しています。私が理解していることから、最後の 2 つのノード間のエッジの数は必ずしも最小カットではありません。私が理解に苦しんでいるのは、このアルゴリズムから実際に最小カットを取得する方法です。私は確率に関する多くのことを見つけ続けていますが、それはすべて意味不明なように見えます...

私が読んだことから、グラフで Karger のアルゴリズムを複数回実行する必要があると思います。これにより、最小カットを達成する高い確率が得られます。おもう？...

誰かがこれをもっと簡単に説明できますか？このアルゴリズムを実行する回数を見つけるにはどうすればよいですか? 私が上で言ったことは正しいですか？

私はこれを行う方法を理解するために多くの苦労をしてきました. グラフのカットセットをすばやく見つけることに興味があります。BGL は、edmonds_karp_max_flow などでサポートされている colorMap 引数の反復によるカット セットの検索をサポートしていることを知っています。Gomory Hu アルゴリズムは、最小カット アルゴリズムに対して複数の呼び出しを行う必要があります。

私が望んでいた結果は、(色、頂点) を含むマルチマップを持つことでした。

次のコードは、ブースト グラフ ライブラリの例を書き直して、associative_property_map にマルチマップを使用する試みです。コードをコンパイルするには、clang -lboost_graph -o edmonds_karp edmonds_karp.cpp または clang の代わりに g++ を使用します。出てくるエラーはわかりません。

ヒントをいただければ幸いです。ありがとうございました。

グラフに基づく方法は、医用画像のセグメンテーションの問題に使用されてきました。画像内の各ピクセル (3D のボクセル) はグラフ内のノードで表され、エッジは隣接するノードを接続します。さらに、ソースとシンクという 2 つのノードが追加されます。コストは、ノード (ソースとシンクを除く) ごとに定義され、これに基づいて最小コストの閉集合が計算されます。このセットは、ソースに属するノードとシンクに属するノードを分離する境界 (3D のサーフェス) に対応します。通常、この境界は必要なセグメンテーションを提供します。詳細はこのペーパーにあります。

私はこのアプローチを使ったかなりの数の研究を見てきましたが、彼らのメソッドをグラフ検索 ( Garvin et al. ) と呼ぶ人もいれば、グラフカット ( Kaba et al.) と呼ぶ人もいます。読むと、これらの作品は非常に似ているように見えます。

グラフサーチとグラフカットの違いを暗示する作品が他にあるが、この作品を読んでも違いが分からない。

もしあれば、誰かが違いを明確にしてもらえますか？

この問題は次のように与えられます: DAG と number が与えられた場合、ソースからシンクへのパスの0 < p ≤ 1少なくとも一部を切断する (つまり、入ってくるアークがない) (つまり、出るアークがない) 頂点のカーディナリティが最小のセットを返します。 p）。の場合p = 1、問題は最小カットに相当します。ただし、の他の値についてはp、答えがどうなるかわかりません。

私が考えているアルゴリズムは、最初に DAG の最小カット セットを計算し、次に基準を満たすように刈り込むことです。これ自体、見つけたサブセットが実際にp与えられた特定の最小カットセットであるかどうかを確認するのは興味深いことです。このアルゴリズムの問​​題は、最終的な答えで必要のない多くのノードを計算し、実際には最初に「より大きな」問題を解決しているため、無駄が多いことです。

この問題の解決策へのポインタはありますか? min-cut の一部のアルゴリズムでは、この追加の制約を早期停止基準として設定することは可能ではないでしょうか?

削除されたパスの数を確認するために、削除によって切断されたパスの数がわかるように、各頂点にインデックスを付けて (必要に応じて更新し続ける) とします。更新中のインデックスの複雑さについて心配しないでください。最後にもう 1 つ、サイズなどに関して、結果のコンポーネントに制約はありません。