|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ カー ： [かー] 【名詞】 1. car 2. (n) car ・ ー ： [ちょうおん] (n) long vowel mark (usually only used in katakana)
エドモンズ・カープのアルゴリズム（英: Edmonds-Karp algorithm）は、フローネットワークの最大フロー問題を解くフォード・ファルカーソンのアルゴリズムの実装の一種であり、 の計算量である。 のrelabel-to-front アルゴリズムに比べると漸近的に遅いが、（辺の少ない）疎なグラフでは速い。このアルゴリズムは1970年にロシア人科学者 Dinic が発表し、それとは独立に1972年にジャック・エドモンズとリチャード・カープが発表した（発見はこちらの方が早かった）。Dinic のアルゴリズムには追加の技法が含まれており、計算量は となっている。 == アルゴリズム == このアルゴリズムはフォード・ファルカーソンのアルゴリズムとほぼ同じだが、増加道を探索するときの順序が定義されている点だけが異なる。それは、各辺が単位長としたときの幅優先探索である。 の実行時間は、各増加道の探索に の時間がかかり、 個の辺のうち毎回少なくとも1つが飽和し、飽和した辺と始点を結ぶ増加道が前回より短くなることはなく、増加道の長さの上限は である。もう1つのこのアルゴリズムの特性として、最短増加道の長さは単調に増大する。アルゴリズムの妥当性の証明は書籍『アルゴリズムイントロダクション』（ISBN 476490408X） にある。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「エドモンズ・カープのアルゴリズム」の詳細全文を読む スポンサード リンク
|