問題タブ [max-flow]

ネットワークには複数の最小カットが存在する場合があります。例えば：

には 4 つの最小カットがあり、Ford-Fulkerson は s (ソース) に「近い」ものを見つけます。すべてのネットワークについて同じことが言えますか? つまり、Ford-Fulkerson はソースに最も近いカットを見つけますか? もしそうなら、フローネットワークで「ソースに最も近い」という概念をどのように形式化しますか?

私は与えられた質問に対する答えを探していました。提供されるその他の詳細は次のとおりです。容量が 0 より大きいグラフ内の各リンクは p であり、容量が 0 未満のリンクの確率は 1-p です。{1,2,3,4} のようなデータ ベクトルがノード 1 からノード 5 に正常に送信される確率はどのくらいですか。

この種の問題には max-flow の概念があることは知っていますが、そのようなネットワークを介した送信が成功する確率はまだわかりません。

2 番目の質問: max-flow の概念を探す前に。開始ノードと宛先ノードを考えると、単純に BFS を実行して、ソース ノードから宛先ノードまでの多くの可能なパスを見つけ、それらをタップし続けることができると考え始めました (パスが無限にある場合、それは指数関数的な時間になることに気付きました)。巨大なスペースの複雑さを持つアルゴリズムですが、それはかなり有限のネットワークだと言います)。次に、P（成功した送信）を計算するために、次の方法でアプローチできますか？

ノード 1 からノード 5 へのパスの数が 4 の場合、P(ノード 1 とノード 5 の間の成功した伝送は)= P(パス 1)+p(パス 2)+p(パス 3)+p(パス 4)-p(パスの交差点） どこ、

P(交差) は、次のような 2 つ以上のパスがエッジを共有する可能性がある確率です。 4.

また、そのパス内のエッジの p(path#)=p^no。私のアプローチは正しいですか？また、このように考えてよろしい場合、これを無限パスの可能性に拡張するにはどうすればよいですか?

どんな助けや指針も大歓迎です!! ありがとうございました。

Boost-graph ライブラリのアルゴリズムで、バンドルされたプロパティで名前付きパラメータを使用しようとしています。edmonds_karp_max_flow

私の問題を示すために、既存のedmonds-karp の例を取り上げ、Internal プロパティを Bundled プロパティ (私は my properties edge_tand と呼びますnode_t) に変更し、Named パラメータを Non-named パラメータに変更しました。

正常にコンパイルされる名前のないパラメーターのバージョンは次のとおりです。

これは、コンパイルされず、多くのテンプレート エラーをトリガーする名前付きパラメーター バージョンです。

完全なedmonds-karp-eg_modified.cppソース:

返されるエラーは次のとおりです: http://pastebin.com/Vra8ZWHG。

名前のないパラメーターでは正常に機能します...しかし、名前付きパラメーターでは機能しません。

更新:誰かがまったく同じ問題を抱えているようです: svn.boost.org/trac/boost/ticket/8791。Boost 1.50彼は代わりにを使用して修正しました1.55。

• ブーストグラフのバージョン: 1.58.0
• コンパイラ: g++ 5.0

私は有向グラフを持っています

まず、Ford-Fulkerson のアルゴリズムを使用して、ネットワークの流れを増やしました。頂点をマークすると、path: のフローがs->a->b->d->t1 つ増えることがわかったので、グラフは次のように変更されました。

最大フローを検索するときは、グラフの最小カットと外側部分を接続するエッジのすべての容量を合計する必要があることを知っています。私の最小限のカットには vertices: が含まれs, a, cているため、取得したすべてのエッジを合計すると、これは 5 であるc(G, !G) = 3 + 2 +2 + 1フローよりもはるかに大きくなります。t

私は何を間違っていますか、FFまたは最小限のカットを台無しにしましたか?

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 を計算します。

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

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