4

制御フローグラフでいくつかのデータを維持する必要があるプログラムを作成する必要があります。実行時に最大フローを計算する必要があります。

グラフを処理するためのライブラリがいくつかあり、ほとんどすべての古典的なアルゴリズムを実装していることは知っていますが、私の問題は、グラフが動的であるということです。つまり、実行時に進化します。すべての進化の後、新しい最大フローを再計算する必要があります。

進化は次のいずれかです。

  • エッジを追加する
  • エッジの容量を増やす

再計算する必要があるのは、ソースSからそのステップで変更されたエッジの宛先ノードへの最大フローです。例えば：

                     S                            S  
                     |                            |
                     5                            5
                     |                            |
                     V                            V
                     A---3--->B                   A---5--->B
    adding edge      |        |     increasing    |        |
      B-->D          2        1      A-->B of     2        1
                     |        |     two units     |        |
                     V        V                   V        V
                     C---3--->D                   C---3--->D

                      OUTPUT: 3                    OUTPUT: 5  
                    (maxflow S-D)                (maxflow S-B)

私のグラフの進化の非常に具体的な性質を考慮すると、どのアルゴリズム/ライブラリがより時間のパフォーマンスが高いでしょうか？つまり、各ステップでグラフが前のステップ（1つのエッジを除く）とほぼ同じであるという事実を考慮すると、前の計算の中間結果を効率的に再利用できるアルゴリズムはありますか？

目的地が毎回違うという事実が問題を少し難しくしていることを私は知っています....各ステップでO（VE ^ 2）よりも優れている方法について何か考えはありますか？

そして、私がこの可能な進化も考慮した場合はどうなりますか？

  • ノード（およびそのノードとの間のすべての着信/発信エッジ）の削除

私はすべての標準的なアルゴリズムを理解し、それらをどのように変更できるかを考えようとしましたが、グラフ理論が私の分野ではないため、悲惨なことに失敗しました...

どんな助けでもありがたいです。ありがとう。

4

2 に答える 2

3

この問題の一般的なケースについて私が見つけることができる唯一の記事は、KumarとGuptaによる最大フロー問題のインクリメンタルアルゴリズムです。ペイウォールの背後にありますが、主なアイデアは非常に単純です。アークuvの容量を増やすときは、グラフを2回トラバースして、グラフのsからtへのパス上にあるすべての頂点wを見つけ、正の残留容量とuvを持つアークを使用します。（uから後方にトラバースし、 vから前方にトラバースします。）以前に計算されたフローから始めて、これらの頂点でGoldberg–Tarjanを実行します。

アークを追加するには、最初に容量がゼロのアークを追加してから、容量を増やします。Kumar–Guptaは、容量の削減/アークの除去も検討しました。これはもっと複雑です。フローをtからvにプッシュバックし、次にvを削除してから、フローを再び前方にプッシュします。

于 2011-07-19T23:13:57.950 に答える
0

すでに使用しているライブラリはありますか？もし私があなたなら、少なくともネットワークシンプレックスを実装しているものを探します。

于 2011-07-19T17:46:38.423 に答える