|
|
| 1行目: |
1行目: |
| − | '''エドモンズ・カープのアルゴリズム'''（[[英語|英]]: Edmonds-Karp algorithm）は、[[フローネットワーク]]の[[最大フロー問題]]を解く[[フォード・ファルカーソンのアルゴリズム]]の実装の一種であり、<math>O(VE^2)</math> の計算量である。<math>O(V^3)</math> の[[プッシュ再ラベル法|relabel-to-front アルゴリズム]]に比べると漸近的に遅いが、（辺の少ない）疎なグラフでは速い。このアルゴリズムは1970年にロシア人科学者 Dinic が発表し<ref>{{cite journal | last = E. A. Dinic | title = Algorithm for solution of a problem of maximum flow in a network with power estimation | journal = Soviet Math. Doklady | volume = Vol 11 | issue = | pages = 1277–1280 | publisher = Doklady | date = 1970年 | url = | doi = | id = | accessdate = }}</ref>、それとは独立に1972年に[[ジャック・エドモンズ]]と[[リチャード・カープ]]が発表した<ref>{{cite journal | author = Jack Edmonds and [[リチャード・カープ|Richard M. Karp]] | title = Theoretical improvements in algorithmic efficiency for network flow problems | journal = Journal of the [[Association for Computing Machinery|ACM]] | volume = 19 | issue = 2 | pages = 248–264 | publisher = | date = 1972年 | url = http://www.akira.ruc.dk/~keld/teaching/algoritmedesign_f03/Artikler/08/Edmonds72.pdf | doi = | id = | accessdate = }}</ref>（発見はこちらの方が早かった）。Dinic のアルゴリズムには追加の技法が含まれており、計算量は <math>O(V^2E)</math> となっている。
| + | {{テンプレート:20180815sk}} |
| − | | |
| − | == アルゴリズム ==
| |
| − | このアルゴリズムは[[フォード・ファルカーソンのアルゴリズム]]とほぼ同じだが、[[フローネットワーク|増加道]]を探索するときの順序が定義されている点だけが異なる。それは、各辺が単位長としたときの[[幅優先探索]]である。<math>O(VE^2)</math> の実行時間は、各増加道の探索に <math>O(E)</math> の時間がかかり、<math>E</math> 個の辺のうち毎回少なくとも1つが飽和し、飽和した辺と始点を結ぶ増加道が前回より短くなることはなく、増加道の長さの上限は <math>V</math> である。もう1つのこのアルゴリズムの特性として、最短増加道の長さは単調に増大する。アルゴリズムの妥当性の証明は書籍『アルゴリズムイントロダクション』（ISBN 476490408X） にある<ref>{{cite book |author = Thomas H. Cormen, Charles E. Leiserson, [[ロナルド・リベスト|Ronald L. Rivest]] and Clifford Stein | title = Introduction to Algorithms | publisher = MIT Press and McGraw-Hill | date = 2001年| id = ISBN 0-262-53196-8 | edition = second edition | chapter = 26.2 | pages = 660-663 }}</ref>。
| |
| − | | |
| − | == 擬似コード ==
| |
| − | | |
| − | '''algorithm''' EdmondsKarp
| |
| − | '''input''':
| |
| − | C[1..n, 1..n] ''（容量配列）''
| |
| − | E[1..n, 1..?] ''（隣接リスト）''
| |
| − | s ''（始点）''
| |
| − | t ''（終点）''
| |
| − | '''output''':
| |
| − | f ''（最大フロー値）''
| |
| − | F ''（最大値の正当なフローを与えるマトリクス）''
| |
| − | f := 0 ''（初期フローはゼロ）''
| |
| − | F := '''array'''(1..n, 1..n) ''（u から v への残余容量は C[u,v] - F[u,v]）''
| |
| − | '''forever'''
| |
| − | m, P := BreadthFirstSearch(C, E, s, t)
| |
| − | '''if''' m = 0
| |
| − | '''break'''
| |
| − | f := f + m
| |
| − | ''（バックトラックし、フローを書く）''
| |
| − | v := t
| |
| − | '''while''' v ≠ s
| |
| − | u := P[v]
| |
| − | F[u,v] := F[u,v] + m
| |
| − | F[v,u] := F[v,u] - m
| |
| − | v := u
| |
| − | '''return''' (f, F)
| |
| − |
| |
| − | '''algorithm''' BreadthFirstSearch
| |
| − | '''input''':
| |
| − | C, E, s, t
| |
| − | '''output''':
| |
| − | M[t] ''（見つかった道の容量）''
| |
| − | P ''（親テーブル）''
| |
| − | P := '''array'''(1..n)
| |
| − | '''for''' u '''in''' 1..n
| |
| − | P[u] := -1
| |
| − | P[s] := -2 ''（始点を再発見したのではないことを確認するため）''
| |
| − | M := '''array'''(1..n) ''（見つけた道の容量）''
| |
| − | M[s] := ∞
| |
| − | Q := queue()
| |
| − | Q.push(s)
| |
| − | '''while''' Q.size() > 0
| |
| − | u := Q.pop()
| |
| − | '''for''' v '''in''' E[u]
| |
| − | ''（まだ容量があり、v がまだ探索されていなかった場合）''
| |
| − | '''if''' C[u,v] - F[u,v] > 0 '''and''' P[v] = -1
| |
| − | P[v] := u
| |
| − | M[v] := min(M[u], C[u,v] - F[u,v])
| |
| − | '''if''' v ≠ t
| |
| − | Q.push(v)
| |
| − | '''else'''
| |
| − | '''return''' M[t], P
| |
| − | '''return''' 0, P
| |
| − | | |
| − | == 例 ==
| |
| − | 7ノードからなるネットワーク（A が始点、G が終点）について、以下のように容量が定義されている。
| |
| − | | |
| − | [[画像:Edmonds-Karp flow example 0.svg|300px]]
| |
| − | | |
| − | 各辺にある <math>f/c</math> で、<math>f</math> は現在のフロー、<math>c</math> は容量を表す。<math>u</math> から <math>v</math> の残余容量は <math>c_f(u,v)=c(u,v)-f(u,v)</math> で表される（容量から既に使われている分のフローを差し引いた値）。<math>u</math> から <math>v</math> へのフローが負の場合、残余容量は却って増える。
| |
| − | | |
| − | {| class="wikitable"
| |
| − | |-
| |
| − | !rowspan="2"| 容量
| |
| − | ! 経路（道）
| |
| − | |-
| |
| − | ! ネットワーク
| |
| − | |-
| |
| − | |rowspan="2"| <math>\min(c_f(A,D),c_f(D,E),c_f(E,G)) = </math><br />
| |
| − | <math>\min(3-0,2-0,1-0) = </math><br />
| |
| − | <math>\min(3,2,1) = 1</math><br />
| |
| − | |align="center"| <math>A,D,E,G</math>
| |
| − | |-
| |
| − | | [[画像:Edmonds-Karp flow example 1.svg|300px]]</td>
| |
| − | |-
| |
| − | |rowspan="2"| <math>\min(c_f(A,D),c_f(D,F),c_f(F,G)) = </math><br />
| |
| − | <math>\min(3-1,6-0,9-0) = </math><br />
| |
| − | <math>\min(2,6,9) = 2</math><br />
| |
| − | |align="center"| <math>A,D,F,G</math>
| |
| − | |-
| |
| − | | [[画像:Edmonds-Karp flow example 2.svg|300px]]</td>
| |
| − | |-
| |
| − | |rowspan="2"| <math>\min(c_f(A,B),c_f(B,C),c_f(C,D),c_f(D,F),c_f(F,G)) = </math><br />
| |
| − | <math>\min(3-0,4-0,1-0,6-2,9-2) = </math><br />
| |
| − | <math>\min(3,4,1,4,7) = 1</math><br />
| |
| − | |align="center"| <math>A,B,C,D,F,G</math>
| |
| − | |-
| |
| − | | [[画像:Edmonds-Karp flow example 3.svg|300px]]</td>
| |
| − | |-
| |
| − | |rowspan="2"| <math>\min(c_f(A,B),c_f(B,C),c_f(C,E),c_f(E,D),c_f(D,F),c_f(F,G)) = </math><br />
| |
| − | <math>\min(3-1,4-1,2-0,0--1,6-3,9-3) = </math><br />
| |
| − | <math>\min(2,3,2,1,3,6) = 1</math><br />
| |
| − | |align="center"| <math>A,B,C,E,D,F,G</math>
| |
| − | |-
| |
| − | | [[画像:Edmonds-Karp flow example 4.svg|300px]]</td>
| |
| − | |}
| |
| − | | |
| − | このアルゴリズムで発見する[[フローネットワーク|増加道]]（赤で示されている）の長さが決して減少しない点に注意されたい。発見した道は、その時点の最短である。見つかったフローは、グラフの始点と終点を分離するように横切る[[最大フロー最小カット定理|最小カット]]をまたぐ容量と等価である。このグラフには最小[[カット (グラフ理論)|カット]]は1つしかなく、<math>\{A,B,C,E\}</math> と <math>\{D,F,G\}</math> に分割する分け方であり、その容量は <math>c(A,D)+c(C,D)+c(E,G)=3+1+1=5</math> である。
| |
| − | | |
| − | == Javaでの実装 ==
| |
| − | <source lang="java">
| |
| − | public class FlowGraph {
| |
| − | public static final int WHITE = 0, GRAY = 1, BLACK = 2;
| |
| − | private double[][] flow, capacity, resCapacity;
| |
| − | private int[] parent, color, queue;
| |
| − | private double[] minCapacity;
| |
| − | private int size, source, sink, first, last;
| |
| − | private double maxFlow;
| |
| − | | |
| − | public FlowGraph(String fileName) {
| |
| − | // 入力テキストファイルから
| |
| − | // "size" 値
| |
| − | // "capacity[size][size]" 配列
| |
| − | // "source" および "sink" ノードのインデックス値（0始点）
| |
| − | // を読み込む。
| |
| − | | |
| − | edmondsKarp();
| |
| − | | |
| − | // 出力ファイルに結果を書く（"flow" 配列と "maxFlow" 値）
| |
| − | }
| |
| − | | |
| − | private void edmondsKarp() { // 計算量 O(V³E) のエドモンズ・カープのアルゴリズム
| |
| − | flow = new double[size][size];
| |
| − | resCapacity = new double[size][size];
| |
| − | parent = new int[size];
| |
| − | minCapacity = new double[size];
| |
| − | color = new int[size];
| |
| − | queue = new int[size];
| |
| − | | |
| − | for (int i = 0; i < size; i++)
| |
| − | for (int j = 0; j < size; j++)
| |
| − | resCapacity[i][j] = capacity[i][j];
| |
| − | | |
| − | while (BFS(source)) {
| |
| − | maxFlow += minCapacity[sink];
| |
| − | int v = sink, u;
| |
| − | while (v != source) {
| |
| − | u = parent[v];
| |
| − | flow[u][v] += minCapacity[sink];
| |
| − | flow[v][u] -= minCapacity[sink];
| |
| − | resCapacity[u][v] -= minCapacity[sink];
| |
| − | resCapacity[v][u] += minCapacity[sink];
| |
| − | v = u;
| |
| − | }
| |
| − | }
| |
| − | }
| |
| − | | |
| − | private boolean BFS(int source) { // O(V²) の幅優先探索
| |
| − | for (int i = 0; i < size; i++) {
| |
| − | color[i] = WHITE;
| |
| − | minCapacity[i] = Double.MAX_VALUE;
| |
| − | }
| |
| − | | |
| − | first = last = 0;
| |
| − | queue[last++] = source;
| |
| − | color[source] = GRAY;
| |
| − | | |
| − | while (first != last) { // "queue" が空でないうちはループする
| |
| − | int v = queue[first++];
| |
| − | for (int u = 0; u < size; u++)
| |
| − | if (color[u] == WHITE && resCapacity[v][u] > 0) {
| |
| − | minCapacity[u] = Math.min(minCapacity[v], resCapacity[v][u]);
| |
| − | parent[u] = v;
| |
| − | color[u] = GRAY;
| |
| − | if (u == sink) return true;
| |
| − | queue[last++] = u;
| |
| − | }
| |
| − | }
| |
| − | return false;
| |
| − | }
| |
| − | }
| |
| − | </source>
| |
| − | | |
| − | == 脚注 ==
| |
| − | {{Reflist}}
| |
| − | | |
| − | == 参考文献 ==
| |
| − | * Herbert S. Wilf [http://www.cis.upenn.edu/~wilf/AlgComp3.html Algorithms and Complexity] (see pages 63 - 69).
| |
| − | | |
| − | {{アルゴリズム}}
| |
| − | {{最適化アルゴリズム}}
| |
| − | | |
| − | {{DEFAULTSORT:えともんすかふのあるこりすむ}}
| |
| − | [[Category:グラフ理論]]
| |
| − | [[Category:アルゴリズム]]
| |
| − | [[Category:数学に関する記事]]
| |
| − | [[Category:エポニム]]
| |