Hatena::Grouptopcoder

れんしゅうちょう。 このページをアンテナに追加 RSSフィード

 | 

2014-03-19最大流問題について その2

前回 に引き続き, 最大流問題についてです.

Dinic 法でのボトルネックは, 各ステップで, dfs によりブロッキングフローを求める部分でした.

Dinic 法では O(nm) だったこの部分を O(n^2) に落としたアルゴリズムを二つ紹介します.


両方共, ある意味でまとめて流そうという感じですが, どうまとめるかの方向性が違うという感じです.

今回は, 前回のように横着せず, "元々の Dinic 法" と言っていたのと同じく, ST 両方から bfs を行い, S から T への最短路に現れうる頂点と辺のみを取り出しておきます.

この層別ネットワークにおける最大流を求める, O(n^2)アルゴリズムを与えようというのが今回の話でした.


MKM algorithm

Malhotra, Kumar, Maheshwari によるアルゴリズムです.

参考文献1 に書いてあるヤツです.

たった2ページなので, 興味のある人は読んでみるとよいかも.


アイディアは非常に簡単です.


層別ネットワークにおいて, ある層で一つの頂点 v しか通らないようなフロー f_v を考えましょう.


v \in V に対し, v に入る辺の残余容量の和と, v から出る辺の残余容量の和の小さい方を \rho(v) とおきます.

但し, S に対しては, 出る辺の方, T に対しては, 入る辺の方を取るものとします.

今は, "S から T への最短路に現れうる頂点と辺のみ" としていたので, \rho(v) > 0 です.

\rho(v) が最小となる v を取ってきます.

すると, 流量が \rho(v) であるようなフロー f_v が, 効率的に計算出来るというのがポイントです.

このフローを, 現在のフローに追加すれば, v を通るフローはもう流せません.

従って, 今のグラフから v を取り除く事ができ, O(n) 回この操作を繰り返す事で, 層別ネットワークにおける最大流が求まる事になります.


MKM algorithm の計算量

f_v の計算法については, v から S と, v から T幅優先探索とおなじ順序で探索を行い, 貪欲に流せばよいという事が, \rho(v) の最小性から解ります.

一回の f_v の計算は O(n+m) かかりますが, f_v で使った辺は O(n) 本を除いてすべて層別ネットワークから取り除かれるので, 合計では O(n^2+m) = O(n^2) で済むようになっています.


MKM algorithm の実装について

S から T への最短路に現れうる頂点と辺のみを取るように管理しなければならないので, 実装は割と面倒です.

Dinic 法のようにてきとーな事はあまり出来ません.

初期状態をそう取るだけならまぁ bfs を2回すればよいだけなのでまだいいですが, そこに更新も加わるとなると, やる気が失せる感じですね.


S から T への最短路に現れうる頂点と辺のみを考えているので, イメージ的には, 下の図の左ようなグラフになります.

v から貪欲に取ったフロー f_v は, 下の図の右のようなフローになります.

f:id:Mi_Sawa:20140320010916j:image:w360

一方, Dinic 法の時のように, S からの dfs のみでやると, 下の図の左のようなグラフになります.

v から S に向けて貪欲に取るのは大丈夫ですが, T に向けて貪欲にとると, T にたどり着く事が出来ないフローが出てきてしまうわけです.

f:id:Mi_Sawa:20140320010915j:image:w360


wave algorithm

こっちは, Tarjan によるアルゴリズムで, 参考文献2 に載っています.

「Karzanov によるアルゴリズムをシンプルにした」 というヤツらしいです.

元の Karzanov のアルゴリズムは, 僕は知りません.


いくつか, 言葉の定義をしておきます.

「フロー整合性が取れていなくても, 入る量が多いぶんには構わない」

と, フローの条件を緩和したヤツを, プリフロー(preflow)と呼びます.

つまり, 各頂点で, フローが余っていてもよいが, 足りないのはダメという事です.

v \in V におけるこの余剰量を, \mathrm{excess}(v) とおきます.

また, \mathrm{excess}(v)0 であるか否かに従って, v が balanced である, または unbalanced であると呼びます.

更に, blocking flow と同様に, preflow であって, 任意の S から T へのパスが飽和辺を含むとき, blocking preflow と呼びます.


e = (u, v) \in E に対し,  \min\{ \mathrm{cap}(e)-\mathrm{flow}(e), \mathrm{excess}(u)\}e に沿って流す操作を,  \mathrm{push}(e) と呼びます.

これは, preflow を保つ操作です. すなわち,  \mathrm{push} 前がプリフローなら,  \mathrm{push} 後もプリフローです.


wave algorithm は, 大雑把に言うと, 次を繰り返すアルゴリズムです.

  1. T の方へ, \mathrm{push} しまくる.
  2. T に行けない余剰分を, S の方へ \mathrm{push} する.

この, 寄せて引いてという感じが波っぽいので, wave algorithm と呼ぶのでしょう. 多分.

1. の方を Forward phase, 2. の方を Backward phase と呼ぶ事にしましょう.


さて, v \in V に対し, blocked であるか, unblocked であるか というステータスを考えます.

これは, v から T にフローを流せる見込みの有無です.

すなわち, 「"blocked ならば流せない" は真だが, 逆は真でなくてよい」です.

また, アルゴリズム中で, 一度 blocked となった頂点は, unblocked にはならない事に注意しておきましょう.


この blocked なるステータスと, blocking preflow を保ちながら, blocking flow にしていくというのが, wave algorithm です.


wave algorithm の詳細

まず, 初期の blocking preflow として, (S, v) \in E を全て最大使ったものを取り, S は blocked, それ以外は unblocked とします.


forward phase では, S からの bfs 順に, v \in V \setminus \{S, T\} を調べます.

v が unblocked かつ unbalanced である時, v から T 方面へ出る辺 v, w のうち, w が unblocked なものに push しまくります.

すると, \mathrm{excess}(v) = 0 (すなわち balanced) になるか, v から T 方面へ出る辺のうち, T に辿り着く見込みのある所が全て最大容量まで使われている状態になります.

後者の時, v を blocked にします.

実際, v から T へは, これ以上行けないのは明らかです.


backward phase では, T からの bfs 順に, v \in V \setminus \{S, T\} を調べます.

v が unblocked かつ unbalanced である時, v から S 方面へ出る辺に push しまくります.

すると, 今度は必ず \mathrm{excess}(v) = 0 (すなわち balanced) になります.

実際, \mathrm{excess}(v)v への流入量以下なので, v から S 方面へ出る枝の逆辺のフロー合計以下, すなわち, v から S 方面へ出る枝の容量合計以下になります.


forward phase と backward phase が何もしなくなったら, アルゴリズムを終了し, これが blocking flow になっています.

このアルゴリズムの正当性を見て行きましょう.


まず, S, T 以外の blocked な頂点は, backward phase の終了後は必ず balanced になります.

各頂点 v に対する操作が終わった時 balanced になるのは既に述べましたが, backward phase 全体の終了後もこれが保たれるのは, T からの bfs 順で頂点を見ていることによります.


次に, S, T 以外の unblocked な頂点は, forward phase の終了後は必ず unblocked balanced 又は blocked になるので,

backward phase 終了後は balanced です.


従って, アルゴリズムが終了した時, S, T 以外の全ての頂点は balanced であり, フローになっています.

特に, アルゴリズム中のプリフローはブロッキングプリフローであるので, ブロッキングフローが見つかった事になります.


wave algorithm の計算量

計算量についてみて行きます.

殆ど全ての forward phase で, 少なくとも一つ blocked な頂点が増える事が示せるので, O(n) 回, これらを行えばよい事がわかります.

従って, push 操作は O(n^2) 回です.

一方, e = (u, v) \in ES から T へ向かう辺とすると,

  • e の流量を増やすのは, v が unblocked な時のみ.
  • e の流量を減らすのは, v が blocked な時のみ.

の二つが成立し, blocked から unblocked にはならないので,

e の流量は, 単調に増え, その後単調に減る事がわかります.

あとは, Dinic 法の時と同じく, \mathrm{iter}(u) を用意して, push 先をコントロールしてやれば, 全体で O(m+n^2) = O(n^2) が達成出来ます.


wave algorithm の実装について

MKM algorithm とちがって, こっちは, backward phase の目的地の方からのみ bfs を行うようにできます.

forward phase で, T に辿りつけない所は順に blocked になるので, まぁ適当にやってくれる感じです.


また, 前の説明は, DAG ならよいハズで, 今回の場合は特に層別ネットワークになっているので,

各 phase で見なければならない頂点を, 結構簡単に管理してやる事ができます.

これをすると, (最悪計算量はともかくとして)実用上は速くなります.


ただし, Dinic 法では層別ネットワークをあまり意識せずに適当にやっていましたが,

今回はちゃんと持たなければなりません.(陽に持つ必要はないですが)

どういう事かは, 例えば次のようなグラフを考えるとわかります.

f:id:Mi_Sawa:20140320010914j:image:w360

まず, forward phase で, 次のようにプリフローが流れます.

f:id:Mi_Sawa:20140320010913j:image:w360

\mathrm{excess} が正である b, c が blocked になります.

次に, backward phase で c から S 方面へ押し戻す訳ですが,

この時に辺cb を選んでしまうと, 次の図のようになります.

f:id:Mi_Sawa:20140320010911j:image:w360

\mathrm{excess}(b) = 2 ですが, b から S へは 1 しか流れず, 詰んでしまうわけです.

今回の場合は辺cb を消しておかなければなりません.


ソース

前述の通り, MKM は面倒くさいので, 実装していません.

興味のある人は頑張って実装して下さい.

wave algorithm の方は, ここ に置いておきます.

競技で wave algorithm 使う気あんまりないので, 割と適当です.


実測

どういうデータが欲しいかに従って, 自分で計測して下さい.

前回と同じデータで, Dinic 法と比較してみると, 次のようになっていました.

前と同様, グラフの構築にかかる時間は無視しています.

特にランダムは, ケース数少ないし, 信用できるようなデータではないと考えた方がよいです.

ケース 頂点数 辺数 Dinic (sec) Wave (sec)
ランダムを80ケース(合計) 5000 1000000 1.9 5.3
ランダムを40ケース(合計) 50000 1000000 2.0 9.9
ランダムを13ケース(合計) 500000 1000000 2.0 10.0
密なランダムを5ケース(合計) 5000 n(n-1)/2 2.2 3.3
完全グラフを15ケース(合計) 2000 n(n-1) 2.1 3.8
ワーストケース1つ目 7000 13997 2.1 4.7
ワーストケース2つ目 628 33491 2.1 0.1

結論

普通に使うぶんには Dinic 法で十分だけど, 最悪の場合を考慮するなら wave algorithm の方がいい. (もっといいのあるだろうけど.)

しかしワーストケース2つ目, 速すぎ...


次回予告

暇とやる気があれば, 次は Dinic 法の高速化についてか, その準備か, または push/relabel 法について書きます.


参考文献

1. は An O(|V|3) algorithm for finding maximum flows in networks - Library Open Repository から読めます.

2. は no title にあります. (学生とかならタダで読めそう).

  1. V.M. Malhotra, M.P. Kumar and S.N. Maheshwari (1978) An O(|V|^3) algorithm for finding maximum flows in networks, Information Processing Letters, vol.7, no.6, pp. 277-278.
  2. Robert Endre Tarjan (1984), A simple version of Karzanov's blocking flow algorithm, Operations Research Letters, vol.2, no.6, pp.265 - 268.

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/Mi_Sawa/20140319
 |