最大フロー問題

最大フローのあるフローネットワークの例。始点

s

{\displaystyle s} と終点

t

{\displaystyle t} があり、各枝の数値はフローと容量を示す。

最大フロー問題(さいだいフローもんだい、英: Maximum flow problem)または最大流問題とは、単一の始点から単一の終点へのフローネットワークで最大となるフローを求める問題である^[1]。単にフローの最大値を求める問題と定義されることもある。最大フロー問題は、より複雑なネットワークフロー問題である最小費用流問題の特殊ケースと見ることもできる。

最小カット問題(英: Minimum cut problem)とは、辺の重みが非負値の有向グラフにおいて、始点から終点までのパスが存在しなくなるように辺を除去した時に、除去した辺の重みの総和を最小にする問題。始点から終点への最大フローは始点から終点への最小カットと等しい。これを最大フロー最小カット定理と呼ぶ。

2部グラフの最大マッチング問題(英: Maximum bipartite matching)とは、2部グラフの最大マッチングを求める問題で、これも最大フロー問題のアルゴリズムを使用して解ける^[1]。

解法

[編集 ]

有向グラフ $G(V,E)$ {\displaystyle G(V,E)} において、各枝 $u,v$ {\displaystyle u,v} の容量を $c(u,v)$ {\displaystyle c(u,v)} としたとき、始点 $s$ {\displaystyle s} から終点 $t$ {\displaystyle t} への最大フロー $f$ {\displaystyle f} を求める。この問題の解法アルゴリズムは多数存在する。

発表年	名称	計算量	説明
線形計画法	正規フローの定義から制約条件が与えられる。 $\sum _{v\in V}f(s,v)$ {\displaystyle \sum _{v\in V}f(s,v)} を最大化。
1956年	フォード・ファルカーソンのアルゴリズム	$O(E\cdot {\text{maxflow}})$ {\displaystyle O(E\cdot {\text{maxflow}})}	残余グラフに余裕がある限り、その経路の残余容量の最小ぶんだけ送る。この計算量を達成するには、容量の整数性が必要である。容量が無理数を含む場合、終了しない可能性がある。
1970年	エドモンズ・カープのアルゴリズム	$O(VE^{2})$ {\displaystyle O(VE^{2})}	フォード・ファルカーソンの特殊ケースであり、幅優先探索で増加道を探す。
1970年	Dinic法	$O(V^{2}E)$ {\displaystyle O(V^{2}E)}	ステップ毎に残余グラフについて幅優先探索で層別グラフを構築し、この上でブロッキングフローと呼ばれるフローを求め、これを追加する。層別グラフでのブロッキングフローは $O(VE)$ {\displaystyle O(VE)} で求められ、ステップの反復は最大 $n-1$ {\displaystyle n-1} 回である。
1978年	MPM法^[2]	$O(V^{3})$ {\displaystyle O(V^{3})}	Malhotra, Pramodh-Kumar, Maheshwari が発表。
1981年	動的木を使ったDinic法^[3]	$O(VE\log V)$ {\displaystyle O(VE\log V)}	層別グラフのブロッキングフロー計算を動的木を使うことで $O(E\log V)$ {\displaystyle O(E\log V)} で行う。
1986年	汎用プッシュ再ラベル法^[4]	$O(V^{2}E)$ {\displaystyle O(V^{2}E)}	プリフロー(頂点群で超過する可能性のあるフロー関数)を使うアルゴリズム。正の超過のある頂点(グラフ内のアクティブな頂点)がある限り、アルゴリズムを繰り返す。プッシュ操作によって残余枝でのフローを増加させ、頂点における高さ関数でどの残余枝にプッシュを行うかを制御する。高さ関数は再ラベル操作で変更される。これらを正しく定義することで、最終的なフロー関数が最大フローを導き出す。
1986年	FIFO式頂点選択規則付きプッシュ再ラベル法^[4]	$O(V^{3})$ {\displaystyle O(V^{3})}	最も以前に活性化された頂点を常に選択するプッシュ再ラベル法。
1986年	動的木を使ったプッシュ再ラベル法^[4]	$O(VE\log(V^{2}/E))$ {\displaystyle O(VE\log(V^{2}/E))}	height 関数について残余グラフの限定的な木構造を構築し、多層的プッシュ操作を行う。
1994年	KRT (King, Rao, Tarjan) 法^[5]	$O(EV\log _{E/V\log V}V)$ {\displaystyle O(EV\log _{E/V\log V}V)}
1998年	バイナリブロッキングフロー法^[6]	$O(E\min(V^{2/3},{\sqrt {E}})\log(V^{2}/E)\log {U})$ {\displaystyle O(E\min(V^{2/3},{\sqrt {E}})\log(V^{2}/E)\log {U})}	計算量のUはネットワークの最大容量。
2013年	Jim Orlin法 + KRT (King, Rao, Tarjan) 法^[7]	$O(VE)$ {\displaystyle O(VE)}	Jim Orlin法自体は $O(VE+E^{31/16}\log ^{2}V)$ {\displaystyle O(VE+E^{31/16}\log ^{2}V)}だが、KRT法を組み合わせることで $O(VE)$ {\displaystyle O(VE)}になる。

これら以外にも解法アルゴリズムは多数存在し、参考文献(特に Goldberg and Tarjan 1988)を参照されたい。

脚注・出典

[編集 ]

^ ^a ^b T. コルメン、R. リベスト、C. シュタイン、C. ライザーソン『アルゴリズムイントロダクション』(第3版)近代科学社、2013年12月17日(原著2009年7月31日)。ISBN 476490408X。
^ Malhotra, V.M.; Kumar, M.Pramodh; Maheshwari, S.N. (1978). "An O(". Information Processing Letters 7 (6): 277–278. doi:10.1016/0020-0190(78)90016-9. ISSN 00200190.
^ Daniel Dominic Kaplan Sleator. An o(nm log n) algorithm for maximum network flow.
^ ^a ^b ^c Goldberg, A V; Tarjan, R E (1986). A new approach to the maximum flow problem. pp. 136–146. doi:10.1145/12130.12144.
^ King, V.; Rao, S.; Tarjan, R. (1994). "A Faster Deterministic Maximum Flow Algorithm". Journal of Algorithms 17 (3): 447–474. doi:10.1006/jagm.1994.1044. ISSN 01966774.
^ Goldberg, Andrew V.; Rao, Satish (1998). "Beyond the flow decomposition barrier". Journal of the ACM 45 (5): 783–797. doi:10.1145/290179.290181. ISSN 00045411.
^ Orlin, James B. (2013). Max flows in O(nm) time, or better. pp. 765. doi:10.1145/2488608.2488705.

参考文献

[編集 ]

Daniel D. Sleator and Robert E. Tarjan (1983). "A data structure for dynamic trees". Journal of Computer and System Sciences 26 (3): 362–391. doi:10.1016/0022-0000(83)90006-5. ISSN 0022-0000 . http://www.cs.cmu.edu/~sleator/papers/dynamic-trees.pdf .
Daniel D. Sleator and Robert E. Tarjan (1985). "Self-adjusting binary search trees". Journal of the ACM (New York, NY, USA: ACM Press) 32 (3): 652–686. doi:10.1145/3828.3835. ISSN 0004-5411 . http://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf .
Andrew V. Goldberg and Robert E. Tarjan (1988). "A new approach to the maximum-flow problem". Journal of the ACM (New York, NY, USA: ACM Press) 35 (4): 921–940. doi:10.1145/48014.61051. ISSN 0004-5411 . http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.91.1599 .
Joseph Cheriyan and Kurt Mehlhorn (1999). "An analysis of the highest-level selection rule in the preflow-push max-flow algorithm". Information Processing Letters 69 (5): 239–242. doi:10.1016/S0020-0190(99)00019-8 . http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.8563 .

数理最適化 • 最適化問題 : メソッド • ヒューリスティック

非線形(無制約)

... 関数

勾配法

収束性	信頼領域ウルフ条件
準ニュートン法	BFGS法ブロイデン法 L-BFGS (英語版) DFP法対称ランク1法 (英語版)
その他の求解法	ガウス・ニュートン法最急降下法レーベンバーグ・マルカート法共役勾配法(非線形共役勾配法) 切り捨てニュートン法 (英語版) ドッグレッグ法

... ヘッセ行列

最適化におけるニュートン法 (英語版)

The graph of a strictly concave quadratic function is shown in blue, with its unique maximum shown as a red dot. Below the graph appears the contours of the function: The level sets are nested ellipses.

Optimization computes maxima and minima.

非線形(制約付き)

一般	バリア関数ペナルティ関数法 (英語版)
微分可能	ラグランジュの未定乗数法逐次二次計画法連続線形計画 (英語版)

凸最適化

凸縮小化

線型および
二次

内点法	カチヤンの楕円体法カーマーカーの投影アルゴリズム
ベイズ- 交換	単体法改訂単体法 (英語版) 十文字法 (英語版) レムケの主ピボット操作法 (英語版)

組合せ最適化

系列範例
(Paradigms)

グラフ理論

最小全域木	ベルマン–フォード法ブルーフカ法ダイクストラ法ワーシャル–フロイド法ジョンソン法 (英語版) クラスカル法
最大フロー問題	Dinic法 (英語版) エドモンズ・カープフォード・ファルカーソンプッシュリラベル最大流アルゴリズム (英語版)

メタヒューリスティクス

カテゴリ(最適化 • アルゴリズム) • ソフトウェア (英語版)

アルゴリズム

ソート

比較ソート	バブルソート選択ソート挿入ソートシェルソートクイックソートマージソートヒープソートシェーカーソートコムソートノームソート図書館ソートイントロソート奇偶転置ソート
線形時間ソート	鳩の巣ソート基数ソートバケットソート
並行ソート	ソーティングネットワークバッチャー奇偶マージソートシェアソート
非効率的	ボゴソートストゥージソート
グラフ	トポロジカルソート

探索

リスト	線形探索二分探索
木・グラフ	幅優先探索最良優先探索均一コスト探索 A* 深さ優先探索反復深化深さ優先探索深さ制限探索双方向探索分枝限定法ビームサーチ
文字列	クヌース–モリス–プラット法ボイヤー-ムーア法エイホ–コラシック法ラビン-カープ法 Bitap法