3

複数のソースと特定の容量の複数のシンクを持つパイプのネットワークをシミュレートするアルゴリズムを考案しようとしています。

これまでのところ、古典的な Ford-Fulkerson アルゴリズムを使用してみましたが、次のグラフを考えると、私が遭遇する問題はこれです。

    S
    |
    a
   / \
  B   C

ソース容量が 1 のSと、シンク容量が 1 のB と Cの両方を考えると、フローは S - a - B となり、B は 1 に飽和し、C はフロー 0 のままになります。

B と Cの両方が 0.5 を受け取るように、ネットワーク全体にフローを均一に分散しようとしています。何か案は？

ありがとう！

4

2 に答える 2

1

ソース容量c iとmシンクt 1 , ..., t mを持つn 個のソースs 1 , ..., s nがあるとします。f = sum i c i とする。すべてのソースiの正味フローが-c iで、すべてのシンクの正味フローがf / mであるネットワークで実行可能なフローを見つけたいとします。

これを解決するには、スーパー ソースSとスーパー シンクTを導入し、各ソースiを容量c iのエッジ ( s i , S) を介してSに接続します。容量f / mのエッジを介して各t iを T に接続します。次に、ソース S とシンク T で max-flow を実行します。

各シンクに正確にf / m単位のフローをプッシュできない場合、何を最適化したいのか明確ではありませんが、次の 2 つのアプローチが役立つ場合があります。

  • eを選択し、容量f / m + e のエッジを介してシンクを T に接続します。二分探索を使用して、総フローがfになる最小のeを見つけます。これにより、max i inflow(t i )が最小化されます。
  • eを選択し、下限 eのエッジを介してシンクを T に追加します。二分探索を使用して、実行可能なフローを可能にする最大eを見つけます。これにより、min i inflow(t i )が最大化されます。下限のある実行可能なフローの問題は、max-flow に減らすことができます: http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/2009/notes/18-maxflowext.pdfこの場合、構築は実際にはシンプル: 追加のスーパーソース S' を追加し、容量m * eのエッジを介して S' を S に接続するだけです。容量eのエッジを介してすべてのシンクを T に接続します。S' と T の間の最大フローがm * eであるかどうかを確認します
于 2014-03-21T21:47:16.943 に答える