問題タブ [max-flow]

いくつかのエッジとノードを持つフローネットワークがあります。そのソースノードを離れるエッジに、最小フローを配置して、そのエッジに少なくともxフローが存在するようにします（それが不可能な場合は、それを知りたいと思います）。最大フローを見つけるためにFord-Fulkersonアルゴリズムを実装しましたが、これを行うためにアルゴリズムを調整する方法がわかりません。ソースノードを離れるエッジの容量を減らすことを考えましたが、それはうまくいきませんでした。

誰かがこの問題について正しい方向に私を導いてくれませんか？

前もって感謝します！

最大フロー問題については、いくつかの非常に洗練されたアルゴリズムがあるようで、少なくとも 1 つが昨年開発されました。Orlin の最大フローは O(mn) 時間またはそれ以上で、O(VE) で実行されるアルゴリズムを提供します。

一方、私が最も一般的に実装しているアルゴリズムは次のとおりです (徹底的な検索を行ったとは言いません。これは、何気なく観察しただけです)。

• エドモンズ・カープ、O(VE^2)
• FIFO 頂点選択を使用したプッシュ リラベル、O(V^2 E)、または O(V^3)
• Dinic のアルゴリズム、O(V^2 E)

より良い漸近実行時間を持つアルゴリズムは、現実世界の問題サイズに対して実用的ではないのでしょうか? また、「動的ツリー」がかなりの数のアルゴリズムに関与していることがわかります。これらは実際に使用されていますか？

Ford-Fulkerson アルゴリズムの私の分析は正しく出ていません。たとえば、次のグラフを見てください。

ノード 0 はソース、ノード 6 はターミナル ノードであり、すべてのエッジの制限は 1 です。ただし、ノード 0 から 1 へのエッジの制限は 2 です。フローが 0->1->3->6 および 0- >1->4->6 および 0->2->5->6 の場合、グラフのフローは 3 です。ただし、フローが 0->1 から開始する場合は、0->1->3 を選択します。 ->6 と 0->1->5->6 では、5->6 は既に占有されているため、0->2->5->6 からはもう移動できません。0->1 の制限は 2 であるため、0->1 から開始できるのは 2 回だけです。したがって、グラフのフローは 2 です。明らかに、グラフの可能な最大フローは 2 ではなく 3 である必要があります。アルゴリズムはこの問題を処理し、常に答えとして 3 を返しますか?

ウィキペディアで最大フローの問題について読んでいました。私は、問題の説明で s が t と等しくなる (ソースがシンクと等しくなる) ことを許可しているのかに興味がありました。s =t の場合、答えは 0 でなければならないことはわかっています。しかし、この問題を解決するコードを書いているとします。私のコードでこの特殊なケースを処理する必要がありますか、それとも問題の説明でこれが禁止されていますか?

こんにちは素晴らしいコミュニティです！

私は現在、暇なときに小さなゲームを書いています。それは、プレイヤーがいくつかの星を制御できる大きな銀河で行われます。これらの星では、それぞれいくつかの (0..*) の入力を持つ建物を構築し、いくつかの出力を生成できます。これらの建物には最大容量/スループットがあり、その入力を縮小すると出力も同じ量だけ縮小されます。すべての建物のスループットを最適化 (または概算) する予算編成アルゴリズムを見つけたいと考えています。ある種の最大フローの問題のように思えますが、私が読んだフロー最適化アルゴリズムのどれも、異なるタイプの入力または依存する出力を持っていません。

私が遊んでいるおもちゃ「テック ツリー」は次のとおりです。

私は準最適なアルゴリズムを喜んで受け入れ、入力/出力にサイクルがないことを保証します (それらは構築から構築への DAG を形成します)。アイデアは、プレイヤーの介入なしに、合理的なスループットと技術ツリーの複雑さを許可することです。数百または数千の星のスケールでは、プレイヤーが予算戦略を手動で定義できるようにすることは楽しくなく、それを生きていないプレイヤーに明確な違いを与えるためです。アドバンテージ。

私の現在の戦略は、DAG を構築し、リソースに全体的な順序を与えることです (船は金属よりも優れています。鉱石はエネルギーよりも優れています)。次に、各リソースをループして、最も「子孫」の建物を見つけます。そのリソースを生成し、その入力から再帰的に貪欲に取得できるようにします (造船所は 2 つのエネルギーと 1 つの金属を取得し、次に製油所は 1 つのエネルギーと 1 つの鉱石を取得するなど)、グラフ内の「嘘つき」を見つけます (ソーラー プラントは 4 エネルギーを提供します。最大値が 2 の場合)、生産を縮小し、変化を前方に伝播します。DAG のすべてが解決されたら、ターミナル要素 (造船所) をグラフから削除し、建物の最大スループットから各エッジの「現在のスループット」を差し引きます。次に、次のタイプのリソースに対してプロセスを繰り返します。もっと良い方法がないか、私よりもはるかに賢い人たちに聞いてみようと思いました。:)

G = (V, E) を s と t をソースとシンクとするネットワークとします。f を G の最大フローとします。G に一意の最小カットが存在するかどうかを判断するアルゴリズムを見つけます。

このサイトで同様の質問を見つけることができました：

最小カットの一意性の決定

そこに与えられた答えの要約：

残差グラフで s から到達可能なすべての頂点を見つけると、G の最小カット (S,T) が見つかりました。

t から始まる同じ残差グラフを見てください。矢印の逆方向に t から到達可能な頂点のグループ (つまり、t に到達できるすべての頂点) を見てください。

このグループもミニカットです。

そのカットが元のカットと同一である場合は、1 つしかありません。それ以外の場合は、2 つのカットが見つかっただけなので、元のカットが一意である可能性はありません。

カットが元のカットと同一である場合、そのカットがユニークである理由がわかりません。他に最小カットがないことを誰が約束できますか?

前もって感謝します

グラフ G = (V,E) で Ford-Fulkerson アルゴリズムを実行し、その結果が最小カット Xmin に関連付けられた最大フロー f _{maxであるとします。}グラフ内のいずれかのエッジの容量を増やすことで、フローを可能な限り増やすことに興味があります。このエッジを特定するにはどうすればよいですか?

最初の頂点sと最後の頂点tが与えられた場合、 sからtまでのすべてのパスを考慮し、容量が小さいエッジを検証します。たとえば、1/1 のエッジがある場合、これは容量を増やす必要がある頂点です。

この問題を解決するための一般的なアルゴリズムはありますか?