フォード・ファルカーソン法
- 提唱者
- Lester R. Ford and Delbert R. Fulkerson
- 年
- 1956
- 種類
- algorithm
- 系統
- Graph Algorithms
この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む
何をする手法か?
1956年にレスター・R・フォードとデルバート・R・ファルカーソンによって開発されたフォード・ファルカーソン法は、フローネットワークにおける最大フローを計算するための基本的な手法である。これは、容量制約のある有向グラフを通じて、ソースからシンクへ送ることができるフローの最大量を求める。
手法の背後にある直感
このアルゴリズムは、残余ネットワークにおいてソースからシンクへの増加パスを繰り返し見つけることによって機能する。残余ネットワークでは、各辺には残りの容量がある。各パスは、そのボトルネック容量(パス上の残りの容量が最小の辺)に等しい追加フローをもたらす。このプロセスは、それ以上増加パスが存在しなくなるまで継続され、その時点で最大フローが達成される。鍵となる洞察は、最大フロー最小カット定理である。すなわち、最大フローはネットワークにおける最小カット容量に等しい。
歴史学
フォードとファルカーソンは1956年に最大フロー問題とその画期的なアルゴリズムを導入した。この研究は、アルゴリズム的手法と有名な最大フロー最小カット定理の両方を確立する上で革命的であった。エドモンズとカープ(1972)は、パス選択に幅優先探索を使用することで最悪ケースの計算量を改善した。ダイニッツ、カルザノフらによるその後の進歩は、さらに高速なアルゴリズムにつながったが、フォード・ファルカーソン法はコンピュータサイエンスにおける古典的で教育的に価値のあるアルゴリズムであり続けている。
使うべき場面
正の整数容量を持つ有向または無向フローネットワークで最大フローを見つけるためにフォード・ファルカーソン法を適用する。これは中小規模のネットワークに有効であり、ネットワークフローの概念を直感的に理解できる。非常に大きなネットワークや、整数フローが必要な場合は、最悪ケースのパフォーマンス向上のためにエドモンズ・カープ法(BFSを使用)またはダイニッツ法を検討する。アルゴリズムの挙動の理解が速度と同じくらい重要な場合にこれを使用する。
限界と注意点
- 時間計算量は容量値に依存する(一般に多項式ではなく、無理数容量では指数関数的になる可能性がある)
- 容量が無理数の場合に終了しない可能性がある(有理数算術による注意深い実装が必要)
- エドモンズ・カープ法やダイニッツ法のような専門的なアルゴリズムよりも、大規模ネットワークでは効率が低い
- 増加パス選択順序に敏感
出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。
強み
- 増加パスに基づくシンプルで直感的なアプローチ
- 容量が有理数または整数である場合に最適な解が保証される
- 小さな整数容量を持つネットワークに対して効率的
- 最大フロー最小カットの二重性を理解するための理論的基盤を形成する
- 有向グラフと無向グラフの両方で機能する
応用
- ネットワークルーティング:通信ネットワークにおけるソースから宛先までのデータスループットの最大化
- 輸送ネットワーク:道路および鉄道の制約を考慮した都市間の最大貨物容量の決定
- 二部マッチング:フローネットワークを構築することによる二部グラフにおける最大マッチングの発見
- 画像セグメンテーション:最大フローアルゴリズムを使用して画像を前景と背景に分割する
- 航空会社スケジューリング:ハブアンドスポークネットワークを通じた旅客フローを最大化するための航空機ルーティングの最適化
- タンパク質解析:相互作用経路を理解するための生物学的ネットワークにおける最大フローの計算
使い方
使い方
残余グラフを、元の辺の容量に等しい容量と、すべての辺にゼロのフローで初期化する。
深さ優先探索または幅優先探索を用いて残余グラフでソースからシンクへの増加パスを見つけ、パスに沿った最小容量を計算し、このフローをパス上のすべての辺に追加しつつ、それらの残余容量を減少させる。
残余グラフで増加パスが存在しなくなるまで増加を繰り返す。累積された総フローが最大フローである。
よくある落とし穴
- 収束が遅い、または誤った結果につながるような不適切な増加パスの選択
- フローを元に戻すための残余容量の更新を怠る、または逆辺の追加を怠る
- 正確な算術が必要な場合に整数除算または浮動小数点算術を使用すること
よくある質問
最大フロー最小カット定理とは何ですか?
この定理は、ソースからシンクへの最大フローが、ソースとシンクを分離する任意のカットの最小容量に等しいと述べている。これは、理論的な洞察とフローアルゴリズムの検証方法の両方を提供する。
なぜアルゴリズムは時々収束が遅くなるのですか?
不運なパス選択により、より大きな増加が可能である場合でも、アルゴリズムは反復ごとに1単位のフローしか増加しない場合がある。幅優先探索(エドモンズ・カープ法)を使用すると、多項式時間での収束が保証される。
アルゴリズムは無向辺をどのように扱いますか?
各無向辺を、同じ容量を持つ2つの逆向きの有向辺に置き換える。アルゴリズムは、その後、有向ネットワーク上でフローを見つける。
辺上のフローと残余容量の違いは何ですか?
辺上のフローは、それに沿って送られた材料の量を示し、残余容量は利用可能な残りの容量を示す。フローが増加すると残余容量は減少し、逆辺はフローを元に戻す能力を追跡する。
関連する手法
参考文献
Ford, L. R., & Fulkerson, D. R. (1956). Maximal flow through a network. Canadian Journal of Mathematics, 8(3), 399-404.
DOI 文献を開くコピーしました。Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
ISBN:978-0-262-03384-8コピーしました。