夢追い人

"It takes a dreamer to make a dream come true."―Vincent Willem van Gogh

Ford-Fulkerson分析およびまとめ

あり本写経フェーズしているのですがとてもわかりにくいので自分なりにわかりやすくまとめてみようと思います。
このまとめが僕個人にとってわかりやすいものであって他の人にとっては実はあり本のほうがわかりやすいことがあるかもしれないことをご承知ください。

最大流問題概要

簡単のため、今回は四頂点五辺のグラフを考えてみます。下の図を見てください。
f:id:touyou1121:20120317114105p:plain
最大流問題とは単純にいうとある有向グラフにおいて始点Sから終点Tまでに一気に流すことができる最大のデータ量を求める問題です。
上の図で見てみると、水色の円が有向グラフの頂点、矢印が辺となっており、それぞれの辺の脇に書かれてるのがC:その辺に流すことのできる最大のデータ量とF:今その辺に流れているデータ量となっており、このときSからTまで最大でいくらのデータ量を一気に流せるかを考えます。
これだけ見ていると最短路問題を最長路にしただけじゃんかとか早とちりしてしまう僕みたいな人がいるので、もう少し詳しく説明しましょう。その上で、何か例えてみると・・・じゃああまりにも抽象概念を出しても仕方ないのでSをダム、Tを海、その他の二点を常に放流しているダム(なにそれw)とし、それぞれの矢印を川に例えてみましょう。
それぞれの川には容量があり、それを超える水量を流してしまうと洪水が起こります。しかし、Sには大雨ですでに水があふれてしまいそうになっているのでできるだけ水量を減らしたいです。となった時にまず最短路と違うのは、Sから次の二頂点のどちらにも水が流せるという点です。つまり、C=1000の辺とC=200の辺に同時に片方には500、片方には200といったように流すことができます。また一番図の上に位置するダムではSから入ってきた水を2つの川に分けて放水できます。そして下のダムでは2つの川からはいってきた水と同じ分量を川に流します。
なんかいらない例えだった気がしますが、つまり「最大になる流れ方」を調べるのではなく、「できるだけ合計を大きくしたときの流量」を調べる問題というわけです。

アルゴリズム解説

では、この問題をとくアルゴリズムを考えてみましょう。
ひとまず単純に貪欲を考えると、一つ流れをみつけて、次に流れを見つけてといったように次々と流れをみつけながら求めていく方法が考えられます。
しかしこれだと、たとえばSから一番上、下、Tという流れを確定した時、上の図だと例が悪かったですが、たとえば下からTまでの辺のCが10とか小さかったとすると、そこに予め10流れてしまうので、本当ならSから下とSから上で10を分担してそのかわりSから上からよりおおく上からTまでの流量が流せるはずのケースを見逃してしまうということになってしまいます。あ〜ごちゃごちゃした。
もう一度図作り直しますね(^_^;)
次のように値を変化させたものを考えましょう。
f:id:touyou1121:20120317120423p:plain
-100ではなく100ですよ。でまず最初にいった貪欲はつまりこうなります。
f:id:touyou1121:20120317120501p:plain
赤が一番最初にみつけた流れです。2からTまですでに100流れてしまったのでSから2には流すことが出来ず、またSから1までに1000ながしているのですが、下に100とられて1からTに900しか流れません。しかし、このケースでの最大流は・・・
f:id:touyou1121:20120317120629p:plain
のように下から100、上から1000ながすことで2からTまでの流量はかわらず1からTまでの流量をふやすことができます。
このように貪欲でやってしまうとどうしても最大流を見逃してしまうことになります。
Ford-Fulkersonはこの問題をうまく解決したこの貪欲の改造とも言えるアルゴリズムです。
とりあえずWiki引用で歴史とか

フォード・ファルカーソンのアルゴリズム(英: Ford-Fulkerson algorithm)とは、フローネットワークにおける最大フローを求めるアルゴリズムである。L. R. Ford, Jr. と D. R. Fulkerson にちなんで命名されたもので、1956年に発表された。フォード・ファルカーソンのアルゴリズムの特殊版であるエドモンズ-カープアルゴリズムも「フォード・ファルカーソン」と呼ばれることがある。

・・・とまぁこれはさておき、ポイントとなるのは逆辺を考えることです。
つまり有向グラフですがそれを逆さまにたどることも考えることによってうまくいきます。
f:id:touyou1121:20120317121622p:plain
図を書いて見ました。きたないwとりあえずこれで説明できるので。
まず貪欲に赤の流れを見つけます。このときそれぞれの辺に赤の数字の流量が流れていることがわかります。
次の青の流れ、これがポイントです。逆にたどるということはつまり「逆向きに流した辺をある水量使わなくても、その辺の終点の頂点まではその水量を別ルートで流すことができ、その分節約できた水量をその辺の始点から別の辺にながすことができる」ということを暗に示しているわけです。ですから、ここで注意しなければならないのは逆向きにたどった辺の水量がマイナスになるような流れは考えられないことで、つまりFをCに置き換えて考えるとうまくいきます。
まぁ最後の緑はダメ押しですね。上二辺ののこりの容量はC-Fになっているのでその上で考えます。

実装

とりあえず蟻本実装を示してみましょう。

#include <cstdio>
#include <cstring>
#include <climits>
#include <vector>
#include <algorithm>
using namespace std;
#define max_v 1000000
#define inf INT_MAX/2
struct edge { int to, cap, rev; };
vector<edge> G[max_v];
bool used[max_v];
// fromからtoへ向かう容量capの辺をグラフに追加する
void add_edge(int from, int to, int cap) {
    G[from].push_back((edge){to,cap,G[to].size()});
    G[to].push_back((edge){to,0,G[from].size()-1});
}
// 増加パスをDFSで探す
int dfs(int v, int t, int f) {
    if (v==t) return f;
    used[v]=true;
    for (int i=0; i<G[v].size(); i++) {
        edge &e=G[v][i];
        if (!used[e.to]&&e.cap>0) {
            int d=dfs(e.to,t,min(f,e.cap));
            if (d>0) {
                e.cap-=d;
                G[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
    return 0;
}
// sからtまでの最大流
int max_flow(int s, int t) {
    int flow=0;
    for (;;) {
        memset(used,0,sizeof(used)); // 0=false
        int f=dfs(s,t,inf);
        if (f==0) return flow;
        flow+=f;
    }
}

え〜と、一言で言うと謎(笑)
逆辺がなんでサイズなんでしょうか?
よくわかりませんね。いや、ここからはみなさんと足をそろえて分析していこうと思います(なんてったって一番参考にしやすいものなのだからね)
とりあえず増加パスというのを説明していませんでした。蟻本の説明だと記号がいりみだれて難しいのですがWikiによればようするに経路上に容量の空きがあるパスのことを指すようです。また増加パスだけで構成されるグラフを残余グラフというそうです。はい。
dfs関数から見てみるとこれは順に行き先をたどっていってその流れ方での最小の辺の容量、つまりその流れで流せる水量を探しているようですね。
そして問題の逆辺ですが、これはこのdfs関数をみているとどうやら辺に対応する逆辺のアドレスを持っているようです。vectorを使っているのでsizeを取ればその辺の情報がどこに入っているかわかるというわけですね。
if文の中身でdの流れを流せた時、流す辺の容量をd減らし、逆辺の容量をd増やしてますね。これはこの実装でC、Fと独立に考えず流す時の容量は一意に決まるので直接Cを変化させているからだそうです。
どの辺にも流せなくなったとき0を返します。その時初めてmax_flowが定まるようですね。

完結

ふぇ〜、やっぱりまとめると違うもんだな(笑)
皆さんは理解していただけたでしょうか?
なんかここおかしいとかあったら教えてください。
おしまい