December 2016
Intermediate to advanced
440 pages
9h 44m
Japanese
Content preview from アルゴリズムクイックリファレンス 第2版
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
Start your free trial
260
■
8
章 ネットワークフローアルゴリズム
8.2.3
分析
フォード
-
ファルカーソン法
が必ず停止するのは、流れているユニットの数が非負
整数であるからだ（
Ford-Fulkerson, 1962
）。
深さ優先探索
を用いた
フォード
-
ファ
ルカーソン法
の性能は、
O(E*mf)
となり、これは最大フローの最終値
mf
に基づく。
一見したところ、
1
回の反復ごとに、
1
つのユニットだけが増加道に加えられ、超巨
大容量のネットワークでは、とてつもない回数の反復が必要に見える。しかし、驚
くべきことに、実行時間は問題のサイズ（すなわち、節点または辺の個数）ではなく
て、辺の容量に依存する。
（
エドモンズ
-
カープ法
という名で知られる）
幅優先探索
を用いると性能は
O(V*E
2
)
となる。
幅優先探索
は、最短増加道を
O(V
＋
E)
で見つけるが、これは、連結フロー
ネットワークグラフにおいては節点の個数が辺の個数よりも少ないことから、実際
には
O(E)
となる。コルメンらは、フローの増加回数が
O(V*E)
のオーダーであり、
エドモンズ
-
カープ法
が
O(V*E
2
)
性能を持つという最終結果を証明した（
Cormen
et al., 2009
）。
エドモンズ
-
カープ法
は
幅優先探索
を用い、すべての可能な経路を長
さ順に調べるので、深さ優先のようにシンクへの「競争」による無駄な作業をしない
分だけ、
フォード
-
ファルカーソン法
を上回ることがままある。
8.2.4
最適化
フローネットワーク問題の典型的な実装では情報を配列に貯える。本章では、そ
うせずに、 ...