問題タブ [max-flow]

Ford-fulkerson アルゴリズムは、わずかな変更を加えるだけで双方向エッジで機能しますが、dinic のアルゴリズムについては混乱しています。このアルゴリズムは双方向エッジでもうまく機能しますか?

私は現在、学生をコースにマッピングするプログラムを書いています。現在、私はSATソルバーを使用していますが、次のサブ問題を解決する多項式時間/貪欲でないアルゴリズムを実装しようとしています:

• 学生あり（50～150人）
• 「数学」、「生物学」、「芸術」などの科目 (10 ～ 20) があります。
• 科目ごとにコースがあります (少なくとも 1 つ)。たとえば、「数学 1」、「数学 2」、「生物学 1」、「芸術 1」、「芸術 2」、「芸術 3」などです。
• 学生はいくつかの (固定された) 科目 (10 ～ 12) を選択し、各科目について、既存のコースの 1 つに学生を割り当てる必要があります (可能な場合)。「数学1」「数学2」どちらの科目を選択しても問題ありません。
• コースには許可された最大数の学生（20-34）があります
• 各コースは固定ブロック（＝タイムスロット1～13）
• 学生は、同じブロックにあるコースに割り当てられない場合があります

今までやってきたことを紹介しています。

(1) 受講者制限の無視

ハンガリーのアルゴリズム/二部マッチングでこれを解決できました。各生徒は、次のようにモデル化することで個別に計算できます。

• 左のノードは、科目「数学」、「生物学」、「芸術」 (生徒の) を表します
• 右側のノードは、ブロック '1'、'2'、.... '13' を表します
• 「科目」から「ブロック」までのコースごとにエッジが挿入されます

このようにして、学生は同じブロックにあるコースに参加していなくても、コースのすべての科目に割り当てられます。ただし、コース制限は無視されます。

(2) 学生の選択科目無視

max-flow-algorithm でこれを解決できました。各学生について、以下がモデル化されます。

• レイヤー 1: 13 の流れでソースから各生徒へ
• レイヤー 2: 各生徒から個人ブロックまで、フロー 1
• レイヤー 3: 各学生ブロックからそのブロック内の各コースへのフロー 1
• レイヤ 4: 各コースから「max-student-limit」を使用してシンクまで

このようにして、学生は任意のコースを選択し、コース制限が満たされます。しかし、運が悪く、科目「生物学」と「芸術」を無視して「数学 1」「数学 2」「数学 3」に割り当てられるかもしれません。

(3)貪欲なハンガリー人

私が持っていた別のアイデアは、一度に 1 人の学生をハンガリーのアルゴリズムと一致させ、「より空のコース」が優先されるように重みを調整することでした。たとえば、次のモデルを作成できます。

• 左のノードは生徒の科目です
• 右のノードはブロック
• コースごとに、重み = 自由席の数で、コースのブロックにサブジェクトからエッジを挿入します

次に、Maximum-Weight-Matching を計算します。

提案/ヘルプをいただければ幸いです。

ありがとうございました！

研究論文で説明されているように、エネルギー最小化の概念を使用して、特定の画像から髪を抽出しようとしていました。エネルギー関数は、事前確率と YCrCb 色尤度ヒストグラムの両方に依存します。エネルギー関数は次のように定義されます。

data (x)=−∑(log(I(x)|x)+logsel (x)) [事前確率モデル]

Smooth (x) = ∑ (x ≠x )exp(-||(x)−(x)||^2/) [以前の YcrCb カラー モデル]

指定されたグラフにラベルを付ける方法に混乱しています(画像のピクセルはグラフのノードとして扱われます)。次のアプローチを使用してグラフにラベルを付けようとしましたが、結果は期待どおりではありません。

そして、グラフのノード間に重みを追加しながら、次を使用します。

値をより低い整数に変更すると比較的良い結果が得られるため、問題はにあると思いmax_val_weight-sourceますが、それは正しい方法ではありません。

また、eSmooth の値を 0 に変更しても、出力には影響しませんか?

誰かがこの文脈に光を当てることができれば、非常に感謝しています。

グラフの一部のエッジがフロー = 3n (n は非負の整数) でなければならないという最大フローの問題をどのように解決しますか? つまり、特定のエッジが 3 で割り切れるフローを持たなければならないという制約をどのように課すのでしょうか? たとえば、これらのエッジにはフロー 0、3、6、9... があるかもしれませんが、フロー 1、2、4、5 はないかもしれません... 理想的には、このようなグラフで最大フローを計算する方法が欲しいです。また、最大フロー構成の各エッジのフロー。

私は、有向で強く接続されたグラフであるグラフ G を持っています。グラフ内の S と T のすべてのペアを意味する、頂点のすべてのペアの最小カットを見つけるように求められます。これは、O(m ² × n ² ) 時間で実行する必要があります。

私が思いついた最善の方法は、すべての頂点を S と見なし、各 S について他のすべての頂点を T と見なし、それらのそれぞれについてフォード-フルカーソン アルゴリズムを実行し、最小カットを見つけることでした。しかし、私が間違っていなければ、このアルゴリズムは O(m ² × n ² × C) の複雑さを持ちます。

^{このタスクを O(m 2} × n ² ) 時間で行うにはどうすればよいでしょうか? それは可能ですか？

加重有向グラフが与えられた場合、グローバルに最小のカット、つまり、削除された場合にグラフを 2 つの半分に分離し、他のそのようなカットと比較して総加重が最小になるエッジのセットを見つけたいと考えています。

さて、以下は機能しているように見えますが、その推論は間違っていると言われました。しかし、率直に言って、私にはその方法がわかりませんし、彼がどれほど確信を持っていたかもわかりません。

U,Vグローバルな最小カット (つまり、st-cut、 where ) によって分離されたノードのセットを考えてみましょうs in U, t in V。V注: からへ戻るエッジは気にしませんU。

任意u in U, v in Vの m について、uv-cut を よりも小さくすることはできません。それ以外のs-t-cut場合、st-cut は (グローバルに) 最小ではありません。同じ理由で、2 つの頂点間uまたは 2 つの頂点間のカットをV小さくすることはできません。

一方、UV カットを大きくすることはできません。それ以外の場合U->Vは、st カットの一部ではないエッジを含める必要があります。つまり、st カットはまったくカットされません。

したがって、s任意に修正して他のすべての頂点を反復するだけで十分ですx。sが inUの場合、sx-cut が大域的最小値に対応するのxは is inVの場合であり、xs-cut はsis inVおよびxis in の場合ですU。それらが両方とも同じセットの一部である場合、カットは少なくともグローバル最小値と同じくらい大きくなります (ただし、より大きくなる可能性もあります)。

したがって、両方を計算し、これまでに遭遇した最小カットを追跡することで、最終的にグローバル最小値を見つけます。

それは私には理にかなっているように思えました。私が間違っている？もしそうなら、なぜですか？

サイズが Ai の N 個のピース​​があります。サイズ x のピースとサイズ y のピースを結合するコストは abs(xy) です。すべてのピースを結合する最適な方法は何ですか? 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' を最後に移動して、後で結合容量を強制的に小さくすることはできません。