にゃあさんの戯言日記

2007-11-09

最大フローのアルゴリズム

  • Edmonds-Karp
  • Dinic
  • Goldberg-Tarjan
  • Goldberg-Tarjan with gap heuristics

あたりを実装してベンチマークしてみた。

Edmonds-Karpはやっぱり他のアルゴリズムに比べると圧倒的に遅い(naiveなGoldberg-Tarjan除く)。N=1000くらいになると比べるべくもない。ymatsuさんに聞いていた通り、Goldberg-Tarjanはheuristicsが無いとあまり意味が無い。逆に、ちゃんと実装すると劇的に改善した。

しかし、意外と速いスピードを出していたのがDinicだったりしてちょっと驚いた。Goldberg-Tarjan with gap heuristicsとは大体同じくらいの速度。コンパクトに書けるならこれを選択するのもありかもしれないなあ。


(追記)

...という論文を今井先生が書いていた件。

(追記)

せっかくなので測定結果をはってみる。Edmonds-KarpとGoldbarg-Tarjan without heuristicsは問題外なので計測していない(たぶん1分以上かかる)。

ネットワークはランダムに0〜1000の整数値をキャパシティとする4000x4000の密行列を生成している。


// g++ -O0の場合
Benchmarking with N=4000
=== Case 1
Dinic: 0.641 secs. result=2009359.
Goldberg-Tarjan (gap): 1.140 secs. result=2009359.
Goldberg-Tarjan (gap + lift-to-front): 0.844 secs. result=2009359.
=== Case 2
Dinic: 0.828 secs. result=1966746.
Goldberg-Tarjan (gap): 1.188 secs. result=1966746.
Goldberg-Tarjan (gap + lift-to-front): 1.250 secs. result=1966746.
=== Case 3
Dinic: 0.735 secs. result=1977706.
Goldberg-Tarjan (gap): 1.141 secs. result=1977706.
Goldberg-Tarjan (gap + lift-to-front): 0.719 secs. result=1977706.
=== Case 4
Dinic: 0.828 secs. result=1987877.
Goldberg-Tarjan (gap): 1.156 secs. result=1987877.
Goldberg-Tarjan (gap + lift-to-front): 1.234 secs. result=1987877.
=== Case 5
Dinic: 0.812 secs. result=1970366.
Goldberg-Tarjan (gap): 1.156 secs. result=1970366.
Goldberg-Tarjan (gap + lift-to-front): 1.235 secs. result=1970366.

// g++ -O1の場合
Benchmarking with N=4000
=== Case 1
Dinic: 0.422 secs. result=2009359.
Goldberg-Tarjan (gap): 0.687 secs. result=2009359.
Goldberg-Tarjan (gap + lift-to-front): 0.468 secs. result=2009359.
=== Case 2
Dinic: 0.547 secs. result=1966746.
Goldberg-Tarjan (gap): 0.703 secs. result=1966746.
Goldberg-Tarjan (gap + lift-to-front): 0.718 secs. result=1966746.
=== Case 3
Dinic: 0.500 secs. result=1977706.
Goldberg-Tarjan (gap): 0.703 secs. result=1977706.
Goldberg-Tarjan (gap + lift-to-front): 0.406 secs. result=1977706.
=== Case 4
Dinic: 0.563 secs. result=1987877.
Goldberg-Tarjan (gap): 0.703 secs. result=1987877.
Goldberg-Tarjan (gap + lift-to-front): 0.718 secs. result=1987877.
=== Case 5
Dinic: 0.547 secs. result=1970366.
Goldberg-Tarjan (gap): 0.687 secs. result=1970366.
Goldberg-Tarjan (gap + lift-to-front): 0.703 secs. result=1970366.

桜庭桜庭 2007/11/10 01:41 これは面白いですね。ICPCだと最悪ケースが入ってくることもあるのでその辺は気になるところですが。

nyaasannyaasan 2007/11/10 02:02 追記しました。N=4000の密行列でこんなかんじです。

ymatsuymatsu 2007/11/10 15:57 Dinic が速いということは,二部グラフの最大マッチングで
同様のテクニックに基づいている Hopcroft-Karp のアルゴリズムも
速いのかな?もしよければ検証してください(ぉ

nyaasannyaasan 2007/11/10 20:41 試してみたところ、Hopcroft-Karpは密でもN=10000に対して1秒くらいです。
これに対する意図的な最悪ケースってどうやって作ればいいんでしょうか...

nyaasannyaasan 2007/11/12 02:29 前原さんに教えてもらった資料をメモ
http://www.mpi-inf.mpg.de/~mehlhorn/AlgEng/AlgEng.html

トラックバック - http://d.hatena.ne.jp/nyaasan/20071109/p1