問題タブ [max-flow]

与えられた 2 つのノード 's' と 't' が undiredted グラフで、グラフを 2 つの A と B に分割する最小カット エッジを見つけるアルゴリズムを探しています。's' は A と 't になります。 ' は B になります。

ほとんどの人が Ford-Fulkerson アルゴリズムをそのタスクに使用することを提案しています。Dinic のアルゴリズムを使用することは可能でしょうか。Dinic のアルゴリズムは動的ツリーで高速化できるためです。可能な限り最速の方法で最小カットエッジを見つけたいからです。

巨大な無向グラフで最小カット エッジを見つけるには、どのアルゴリズムがより高速ですか?

これらのアルゴリズムの詳細を検討している間に、アドバイスを聞きたいと思います。

前もって感謝します

私は医療画像のセグメンテーションに取り組んでおり、ファジー接続性アルゴリズムとグラフカットを組み合わせたいと考えています.背景と前景がファジー接続性で画像をセグメント化し、グラフカットアルゴリズムのシンクとソースとして使用されます.グラフカットセグメンテーションのシード座標を取得するための私のコードです

グラフ カットには、File Exchangeのアルゴリズムを使用しました。

たとえば、次のように定義できます

しかし問題は、コード ソースのこの部分のように、コスト関数からの情報をどのように組み合わせるかです。

行列のサイズを超えます

3 つのエッジがノードに入り、3 つのエッジが出てくるようなグラフがありますが、特定の入力エッジに容量がある場合にのみ、出力エッジをアクティブにする必要があります。たとえば、次の場合:

A -> N

B -> N

C -> N

N -> N'

N' -> A'

N' -> B'

N' -> C'

Aにフローがある場合はA'を通過するフローのみが必要であり、Bにフローがある場合はB'を通過するフローなどが必要です。

基本的に、エッジ A、B、C の容量リミッターであり、最初は容量を制限できませんでした。

この制約を最大フローに追加し、このシナリオが複数回発生すると仮定して、特定のグラフの最大フロー グラフの問題を解決するにはどうすればよいですか?

編集: A'、B'、および C' はグラフの後半で使用されるため、最終的にそれらの容量を制限することもできません。そのため、N と N' を最後に移動して、後で結合容量を強制的に小さくすることはできません。

と の 2 つのクラスがMaxFlowありMinMaxFlowます。

MaxFlowブースト グラフを使用して、ネットワーク トポロジからグラフを作成します。

MaxFlowg_ここですべての作業を行うために必要なインスタンスは 1 つだけなので 、ローカル変数を維持します。失敗した場合(容量を 0 に設定) MinMaxFlow、最小最大フローを見つけるためにグラフのすべてのエッジを繰り返します。edge

問題は、クラスmaxFlowAlgoのローカル変数に基づいていることです。 で新しいオブジェクトを作成すると、呼び出しで独自のデータが使用されるため、結果が予測できなくなります。だから私の質問は:メソッドがでローカル変数を使用する場合、2番目のクラスに属するメソッド(のような)をどのように使用できますか?g_MaxFlowmaxFlowObjMinMaxFlowmaxFlowObj.maxFlowAlgo()maxFlowAlgoMaxFlowMinMaxFlowMaxFlow

更新: 問題が からのものであることがわかりました。boost::boykov_kolmogorov_max_flowバンドル プロパティを使用して容量プロパティ マップをそれに渡しますが、このアルゴリズムは容量プロパティ マップだけでなく、元のエッジ容量変数も変更します! ここでの回避策は、アルゴリズムを実行する前に容量値を保存し、その後に復元する必要があることです。元のメンバーを変更することは想定されていませんよね?

N頂点に 1 から N の番号が付けられた無向木があるとします。各エッジ ツリーにはある程度の容量があります。考えられるすべての頂点のペア間の最大フローの合計を見つけます。任意の 2 つの頂点間を移動する方法は 1 つしかありません。
考えられるすべての頂点のペア間の最大フローの合計を見つけます。

例: 3 つのエッジを持つ特定のツリーでは
1 2 5
2 3 6
、ノード 1 とノード 2 の間のエッジは容量 5、ノード 2 とノード 3 の間は容量 6 です。
Output - 32

(1,2) = (2,1) = 5
(1,3) = (3,1) = 5
(2,3) = (3,2) = 6
したがって、出力は(5+5+6)*2 = 32

私のアプローチ-

1. Sortedge_capacity に基づくエッジ

2. While edge_listis not empty: 最小限の容量でエッジを削除

   • このエッジ上leftのノードの数を数えます。rightノード数の DFS を実行する
   • 答えに ( left_count* right_count* ) を追加します。edge_capacity

3. 戻りanswer*2ます。
   

時間計算量は O(n ² ) です。このソリューションは TLE を提供します。
時間の複雑さをさらに軽減するにはどうすればよいでしょうか?

私のコード-

元の問題へのリンク - Spoj-Flow on Tree

アップデート

制約-

1. テストケース数 - 10
2. 1 <= N <= 10 ⁵ (各テスト ケースの頂点の数)
3. ^{各エッジの容量は負ではなく、10 6}を超えません。
4. すべてのテスト ケースの頂点の総数は 5*10 ⁵未満になります。

G = (V,E) の 2 つの頂点 u と v と正の整数 k を与えて、u から v への ak 辺の互いに素な経路が存在するかどうかを決定するアルゴリズムを説明してください。決定問題の答えが「はい」の場合、その方法を説明してくださいk 個の辺が素な経路のセットを計算します。

解決策 : u から v への最大フローを実行し (グラフ G のすべてのエッジに 1 の重みを与えて、1 つのエッジが u から v への 1 つのパスのみの一部になるようにします)、フローの値を取得します。フローの値が k の場合、決定問題の答えは「はい」になります。

このようなすべてのパスを見つけるために、u から BFS を実行して最小カットを見つけます。したがって、最小カットの両側に 1 つずつ、頂点を 2 つのセットに分割する頂点のパーティションがあります。

次に、最小カットから取得した 2 つのパーティション セットにあるこれらの頂点のみを持つすべてのパスを探して、u から v への DFS を再度実行する必要がありますか。

または、他のよりクリーンな方法はありますか？すべての k エッジの素なパスを取得します。

したがって、最大フローが 10 であることがわかりました。つまり、最小カットも 10 であることを意味しますが、この画像に最小カット 10 を描画するにはどうすればよいですか?

mincut の誤解があるかどうかはわかりませんが、edmond-karps とそれに続くフロー ネットワーク上の BFS を使用して mincut アルゴリズムを作成しました。

A から B への最小カットを実行するように指示すると、残差フロー A->B = 0 であるため機能し、A->B (1) のカットでセット {A} が生成されます。

ただし、B から A への最小カットを実行するように指示した場合、(C からのエッジがないため) エッジを拡張することはできません。そのため、結果のセットは {C} であり、B-> のカットがあります。 C (2)。

私の見方では、これを 2 つのうちの 1 つの方法で誤解している可能性があります。まず、B から A への最小カットは正しい可能性があります。これは、B のセットからのエッジのみがカウントされ、エッジへのエッジはカウントされないためです (つまり、最小カットは、「B が A に接続できないようにするための最小値は何か」ではなく、"グラフを 2 つのパーティションに分割するための最小値は何ですか)。

または、フロー ネットワークで最小カットを見つけるように求められた場合 (一般的な最小カット。現在、「任意のソースを選択し、他のすべてのノードを試す」方法を使用しています)、両方向に等しいフローが必要である必要があります。任意のエッジ。

この記事で説明した Push-Relabel Graph Cut アルゴリズムを前提として、バイナリ イメージ セグメンテーションを実行したいと考えています。私の質問は、グラフの初期化に関するものです。

画像を格子構造 (MRF) を持つグラフとして表す場合、通常は、この論文のセクション 3 の式 1 に従って、標準の単項項およびペアワイズ項のエネルギー関数に従って問題を定式化します。ここで、単項項はデータです。エネルギーとペアワイズ項は、ある近傍の滑らかさをモデル化します。

この MRF 最適化定式化と、リンクされた記事の max-flow アルゴリズムの定式化とを結び付けるのに苦労しています。私の理解では、隣接するノード間の容量は、このペーパーのセクション 2、方程式 7 など、(空間距離と強度の値に基づく) 距離関数で表すことができます。ただし、シード ポイントの初期分布など、事前の知識をグラフの初期化に組み込む方法は明確ではありません。

より高いレベルでは、背景またはオブジェクト クラスに関連するいくつかのラベル付きシード ポイントを含む画像が与えられた場合、max-flow を使用してバイナリ セグメンテーションを実行できるようにフロー グラフを初期化するにはどうすればよいでしょうか?