Dinic 法と, その注意点 - れんしゅうちょう。

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

■ 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 の方はどっちにしろ低くなる.)

コメントを書く

7742015/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_Sawa2015/10/15 23:39(最初の b が d ですが)そのとおりですね. ご指摘ありがとうございます, 修正します.