Dinic 法の速さ - れんしゅうちょう。

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

■ 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 ですが, 真ん中あたりにある密グラフがヤバいケースです.

コメントを書く

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 ですが)そのとおりですね. ご指摘ありがとうございます, 修正します.