|
|
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:エポニム]]
| |