れんしゅうちょう。

2014-03-11最大流問題について.

■ いんとろ 02:05

最大流問題を解くアルゴリズムについて, ちょろっと書いておきます.

要約すると, 言いたいことは

Dinic のライブラリ持ってたら, 間違っていないかチェックしましょう. (注意1のやつ)
Dinic ちょっぱやな気がするけど, ワーストケースは遅いよ. (当然)

の二つです. 半分自分用のメモみたいなもんです.

Dinic についてちゃんと知っている人が読むメリットは多分無いです.

ツッコミなどあれば, ぜひお願いします.

蟻本のページ番号が書いてある時は, 第二版のものです.

最大流問題を知らない人は, 蟻本(p. 188から少し)を読んで下さい.

今回は, グラフ $G=(V, E)$ 上で, $S$ から $T$ への最大流を求めたいとします.

また, $n = |V|$ , $m = |E|$ とします. (こんな準備要るのかな)

■ Dinic 法と, その注意点 02:05

最大流を解くアルゴリズムの一つに, Dinic 法というヤツがあります.

Dinic 法については, とりあえず, 蟻本のコラム(p. 194)に書いてある事を把握しましょう.

ここでは, "1ステップ" というのは, 一度 bfs をしてから, もう一度 bfs をするまでを指す事にします.

計算量について.

各ステップの dfs が $O(nm)$ で終わる事は, そんなに自明ではないです.

実際,

dfs が呼ばれる回数は $O(m)$ になり得る. ( $S$ -完全二部グラフ- $T$ で二部グラフの所だけ容量 $1$ , 他容量 $\infty$ とか考えればよい.)
一回の dfs にかかる時間も $O(m)$ になり得る. (増加パスが一つしか無くて, それが最後に見つかる的なのとか考えればよい.)

なので, 単純に掛け算すると $O(m^2)$ になります.

参考文献1を眺めると, $O(nm)$ になる事を見るには, 辺が使われなくなるタイミングに注目すればよいようです.

注意2までを読んでからの方が解りやすい気がしますが, 大雑把言うと, 多分こういう感じです.

dfs の再帰深さは, 0から深くなり, 浅くなり, 深くなり, ..., 浅くなり, 0になる.
浅くなり始めるのは, $T$ に到達した時か, 今の頂点から $T$ へ到達不可能だった時.
$T$ へ到達した時は, 出来たパスに含まれる辺のうち, 容量最小の辺が削除される.
$T$ へ到達不可能だと解った時は, 今来た辺 $e$ を戻り, $e$ は削除される.
浅くなり始めてから, 次に浅くなり始めるのは, $d(S, T) \le n$ から, 高々 $2n$ 回以内.
よって, dfs は $O(nm)$ .

元々の Dinic 法

元々は, $S$ と $T$ 両方から bfs をして, 真に関係ある頂点と辺だけを取り出します.

フローを流すときも, それによって使えなくなった辺や頂点はその場で取り除くようにしています.

普段よく使っているのは, どうやら Cherkassky version に近いようです.(参考文献1)

実装上の注意点とか, ちょっとした高速化.

bfs では, $S$ からの距離で, 各頂点をラベリングしています.

dfs で見るのは, 始点のラベルが終点のラベルより小さい辺のみです.

この辺のみを見ると, 例えば次のようなグラフになります.

いくつかの注意を, このグラフ上で, $S$ から $T$ に $2$ だけ流れ, このステップが終わるまでに, dfs がどう動くかと共に見ていきます.

注意1(ありがちで割と重大なミス)

蟻本(p. 194) に書いてある

無駄な辺を何度も調べない

というのは, dfs内のループが iter[v] をインデックスとして回っている事に対応しています.

これはかなり重要で, これがないと, 入力によってはかなり遅くなります.

Dinic 法のライブラリを持っている人は, ちゃんとそうなっているか確かめましょう. (そうしていない人もそれなりに多いようです.)

これを怠った場合, dfs は次の順序で頂点を見る事になります.

一回目の dfs では,

により,

$S \rightarrow c \rightarrow g \rightarrow T$

なる増加パスを見つけ, これに沿ってに 1 流します.

二回目の dfs では,

$S \rightarrow a \rightarrow d \rightarrow a \rightarrow e \rightarrow a \rightarrow S \rightarrow b \rightarrow e \rightarrow b \rightarrow f \rightarrow b \rightarrow S \rightarrow c \rightarrow g \rightarrow c \rightarrow h \rightarrow T$

により,

$S \rightarrow c \rightarrow h \rightarrow T$

なる増加パスを見つけ, これに沿ってに 1 流します.

次の dfs は失敗し, これ以上 $S$ から $T$ へは流れない事が解り, このステップは終了します.

一方, ちゃんと実装した場合, 一回目の dfs は同じですが, 二回目の dfs では,

$S \rightarrow c \rightarrow g \rightarrow c \rightarrow h \rightarrow T$

により,

$S \rightarrow c \rightarrow h \rightarrow T$

なる増加パスを見つけます.

前回の dfs の続きから始めるというイメージです.

これをしないと, オーダーレベルで遅くなるはず.

注意2(dfs を一回で済ませる)

一回目の dfs で

$S \rightarrow c \rightarrow g \rightarrow T$

なる増加パスを見つけた時, 使えなくなる辺は $g \rightarrow T$ のみです.

従って, 次の dfs でも, $g$ まで探索される事がわかり, ここから継続して dfs を行うようにすればよい事が解ります.

少し工夫すれば, 各ステップの dfs が一回で済むように実装する事が出来, この時の探索順序は

のようになります.

注意3(dfs を逆から)

上の探索順を見ていると, 明らかに $T$ に辿りつけない $a, b, d, e, f$ を探索するのは無駄だなぁという感じがします.

これを解消するには, dfs を $T$ から, 逆グラフに沿ってするように変更すればよいです.

この時の探索順序は,

$T \rightarrow g \rightarrow c \rightarrow S \rightarrow c \rightarrow g \rightarrow T \rightarrow h \rightarrow c \rightarrow S \rightarrow c \rightarrow h \rightarrow T$

となります.

bfs と dfs を逆から探索するようにすればよいので, $T$ からの距離でラベリングし, $S$ から dfs を行なってもよいです.

bfs を順グラフ, dfs を逆グラフで行うほうが, 実測でよい結果が出ましたが, これは, グラフの持ち方の問題で, 逆グラフでの bfs で辺をイテレートする際のキャッシュヒット率が低い事によるものと思われます. (dfs の方はどっちにしろ低くなる.)

■ Dinic 法の速さ 02:05

Dinic 法は, 上で書いたように, (ちゃんと実装すれば) $O(mn^2)$ です.

しかし, 経験的にはもっと速く感じます.

ランダムケースとか

速い. 体感計算量などという言葉を作りたくなるくらい. 体感計算量, 定数倍が重めな $O(n+m)$ . (個人の感想です)

グラフの構築にかかる時間が無視できない感じ.

頻出の特殊なグラフ

参考文献1 によれば,

二部グラフの最大マッチング系の場合は, $O(\sqrt{n}m)$ ,
辺容量が全て同じ場合は, $O(\min \{ m^{1/2}, n^{2/3} \} E)$

で, こういうグラフなら速い保証があってよいです.

悪いケース

当然なんだけれども, 普段の Dinic からは信じられない遅さ.

最悪ケースについては, 次の二つ(参考文献の2と3)が参考になります.

一つ目は, その名の通りの論文で, $O(n)$ ステップかかる素疎グラフ(割と自明なケース)を挙げています.

素疎なので, ワーストケースってほどワーストじゃない気もしますが, ステップ数が $O(n)$ 回かかるケースです. (平均的なケースではもっと滅茶苦茶少ない)

二つ目は, TopCoder の Tutorial ですが, 真ん中あたりにある密グラフがヤバいケースです.

■ ソースと実測 02:05

ソース

ここに置いておきます.

実験用の部分が多いです.

蟻本と Spaghetti Source にかなり影響をうけています.

割とどうしてくれても良いですが, WAやTLE喰らっても知りません.

理解してから, (他の人のソース見ながらでも)自分で実装する事をおすすめします.

実測

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

参考として, 自分の環境で, 自分が書いたコードが $2$ 秒程度かかるものを挙げます.

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

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

ケース	頂点数	辺数
ランダムを80ケース(合計)	5000	1000000
ランダムを40ケース(合計)	50000	1000000
ランダムを13ケース(合計)	500000	1000000
密なランダムを5ケース(合計)	5000	約 $n(n-1)/2$
完全グラフを15ケース(合計)	2000	$n(n-1)$
ワーストケース1つ目	7000	13997
ワーストケース2つ目	628	33491

■ 結論 02:05

ワーストケースはマジ死ぬ.

Dinic 法は使い所を間違えると辛い事になる.

例えば, 次のような条件が揃うとヤバめ.

問題の入力をうまくすれば, 最大流を求めなきゃいけないグラフを, 割と自由に決められる.
頂点数が $500$ 以下みたいな, Dinic 法とかを過信した制約.

こういう時は, Goldberg-Tarjan とか, Push/Relabel 系のアルゴリズムを使った方がよさげ.

逆に,

問題の入力から, 特殊な形のグラフを作って, その上で最大流を求める.

の場合は, 割と制約大きくても, Dinic のワーストケースを突くのが難しく, 大丈夫そう.

特に, 前に言った, 辺容量が全て同じ場合や, 二部グラフの場合など.

■ 言い訳 and 次回予告 02:05

ゆるふわな感じに書いているのは, $\TeX$ 記法が貧弱だからです, 許して下さい.

暇とやる気があれば, 次は $O(n^3)$ のアルゴリズムについて書きます. 多分.

■ 参考文献 02:05

1. は no title の一番上から読めます.

2. は Worst case behavior of the Dinic algorithm から読めます.

3. は Topcoder.

Yefim Dinitz (2006), Dinitz' algorithm: the original version and even's version, In Theoretical Computer Science, Oded Goldreich, Arnold L. Rosenberg, and Alan L. Selman (Eds.), Springer-Verlag, pp.218-240.
Gary R. Waissi (1991), Worst case behavior of the Dinic algorithm, Applied Mathematics Letters, vol.4, no.5, pp.57-60
Zealint, Maximum Flow: Augmenting Path Algorithms Comparison, Algorithm Tutorials, TopCoder
秋葉拓哉, 岩田陽一, 北川宜稔 (2012), プログラミングコンテストチャレンジブック-第2版-～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～, マイナビ

コメントを書く

774 2015/10/15 23:28 「Dinic 法と, その注意点」の注意2の部分について
探索順序は
S, a, b, a, e, a, S, b, e, b, f, b, S, c, g, T, g, c, h, T, h, c, S
ではないですか？最初に g に来たときに c に戻るのはなぜでしょうか．
私が理解していない/勘違いしていたら済みません．

Mi_Sawa 2015/10/15 23:39 (最初の b が d ですが)そのとおりですね. ご指摘ありがとうございます, 修正します.

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/Mi_Sawa/20140311

リンク元