最大流問題

問題設定

水道管のような、リンクを通じて何かが流れるネットワークを想像する

  • 有向グラフ$G$がある
  • ノード$s$から$t$に、水を流す
  • 各リンクには容量capがあり、そのリンクを通じてはcapまでの量しか流せない
  • $s, t$ 以外のノードでは流入量と流出量は一致する
  • 最大流せる流量を求めよ
       ① -9→ ②
  10↗    \6    \8
  /        ↘     ↘    ※リンク上の数値はcap
s-4→ ③ -3→ ④ -4→t

この場合、たとえば以下のように配分することで、12を流すことができる。

       ① -8→ ②
  10↗    \2    \8
  /        ↘     ↘    ※リンク上の数値は流量
s-2→ ③ -2→ ④ -4→t

わかりやすい図とかは上記リンク先参照

解き方

「逆辺」という概念を利用する。逆辺とは、Gの各辺を逆向きに繋ぐリンク。

  1. 最終的な答え$f=0$で初期化する
  2. $G$に「逆辺」を追加する
  3. 各リンクに「残容量」を設定する
    • オリジナルリンクの残容量の初期値は、そのリンクの容量
    • 逆辺の残容量の初期値は0
  4. $s$から$t$まで流せる任意の経路を探す
    • 残容量が0より大きい辺のみを辿る
    • 経路が見つからなければ終了。その時点の$f$が答え
    • 見つかったら、その経路で流せる流量$d$を求める
      • $d=$経路中のリンク残容量の最小値
  5. $G$を更新する
    • 経路の各リンクの残容量を$d$ずつ減らす
    • 経路の逆方向の各リンクの残容量を$d$ずつ増やす
  6. $f$に$d$を足し、4.に戻る

なぜ逆辺が必要なのか

いきなり逆辺なんて出てきて「何じゃこりゃ」と思うが、これを使うと貪欲法(見つかった経路に最大限流す、を繰り返す)が上手くいく。

逆辺の無い貪欲法で解くと、経路を発見する順番によっては最大を達成できなくなる場合がある。

逆辺の無いネットワーク
       ① -9→ ②        s→tの経路をどれか1つ見つける際、
  10↗    \6    \8     s-①-④-tの経路を最初に見つけてしまうと……
  /        ↘     ↘    流量4を流した結果、④-tのリンクがそれ以上使えなくなる
s-4→ ③ -3→ ④ -4→t
                         (下図:s-①-④-tに流量4を流した後の残容量)
       ① -9→ ②           
   6↗    \2    \8     最適解は、経路s-①-②-tに多めに流すことで
  /        ↘     ↘    経路s-①-④-tに流す容量を少なくし、
s-4→ ③ -3→ ④ -0→t リンク④-tを経路s-③-④-tのために開けておくのが良い
逆辺を張ったネットワーク(正方向残容量/逆方向残容量)
          9/0 
      ①ーー-→②        経路s-①-④-tを最初に見つけて流した後の状態
 6/4↗  \2/4    \8/0   
  /      ↘   0/4 ↘    同じく④-tのリンクは使えなくなっているが、
sー→③ー→④ーー-→t  代わりにs③④①②tという経路が使えるようになっている
  4/0   3/0              リンク①-④の逆辺を利用し、流しすぎた容量を「押し戻す」感覚。

                         これにより、経路の発見順にかかわらず、全経路が網羅される

高速化

Ford-Fulkerson

  • $s$から探索して$t$までの経路を発見
  • $G$を更新(経路の残容量を$d$減らし、逆を増やす)

という流れを繰り返す素朴な方法は、フォード・ファルカーソンのアルゴリズムという。

計算量は$O(Ef)$、ただしE:リンク数、f:最大フロー

Dinic法

1つの経路$R$が見つかって$G$を更新した後、次の経路を求める際に、影響があるのは$R$と辺を共有する経路だけである。他の経路は、途中までの探索結果を利用できるはずだ。

それをアルゴリズムとして確立したのが、Dinic法となる。

  1. $s$からBFSを行い、各頂点の$s$からの距離を記憶しておく(リンク距離=1)
  2. $s$からDFSを行い、$t$までの経路を1つ見つける
    • BFSで求めた$s$からの距離が、増加する方向にのみ移動する
    • 各ノードにつき、「探索した結果、$t$にたどり着けなかった辺」を覚えておく
    • 経路が見つかったら、$G$を更新する
  3. 改めて$s$からDFSを行う
    • やり方は同様
    • 前のDFSで、$t$にたどり着けないとわかった辺は使わない
    • 見つかったら、$G$を更新し、3.に戻る
    • 見つからなくなったら、探索した辺をリセットし、1.に戻る

※BFSもDFSも、残容量が残っているリンクのみを探索する。

BFSの時点で$t$までの経路が見つからない状態になれば、それが最大流。

And more.

もっと高速化は進んでいるらしいのだが、理解が追いつかないため、無視。

事前処理に時間をかけることで、クエリの時間を短縮しているアルゴリズムもある。

実装

Dinic法 - tkw’s diaryを参考に。

from collections import deque


class Dinic:
    def __init__(self, n):
        self.n = n
        self.links = [[] for _ in range(n)]
        self.depth = None
        self.progress = None

    def add_link(self, _from, to, cap):
        self.links[_from].append([cap, to, len(self.links[to])])
        self.links[to].append([0, _from, len(self.links[_from]) - 1])

    def bfs(self, s):
        depth = [-1] * self.n
        depth[s] = 0
        q = deque([s])
        while q:
            v = q.popleft()
            for cap, to, rev in self.links[v]:
                if cap > 0 and depth[to] < 0:
                    depth[to] = depth[v] + 1
                    q.append(to)
        self.depth = depth

    def dfs(self, v, t, flow):
        if v == t:
            return flow
        links_v = self.links[v]
        for i in range(self.progress[v], len(links_v)):
            self.progress[v] = i
            cap, to, rev = link = links_v[i]
            if cap == 0 or self.depth[v] >= self.depth[to]:
                continue
            d = self.dfs(to, t, min(flow, cap))
            if d == 0:
                continue
            link[0] -= d
            self.links[to][rev][0] += d
            return d
        return 0

    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.depth[t] < 0:
                return flow
            self.progress = [0] * self.n
            current_flow = self.dfs(s, t, float('inf'))
            while current_flow > 0:
                flow += current_flow
                current_flow = self.dfs(s, t, float('inf'))

# 使い方
mf = Dinic(6)
mf.add_link(0, 1, 10)
mf.add_link(0, 3, 4)
mf.add_link(1, 2, 9)
mf.add_link(1, 4, 6)
mf.add_link(2, 5, 8)
mf.add_link(3, 4, 3)
mf.add_link(4, 5, 4)
print(mf.max_flow(0, 5))

最小カット問題

最大流問題の答えは、最小カット問題の答えと一致する。

問題設定

  • 有向グラフGがある
  • 各リンクには非負のコストが与えられている
  • ある2点s, tがある
  • s→tまで行けなくなるように、リンクを取り除く
  • 取り除くリンクのコストをできるだけ少なくしたい場合、いくつになる?

最大フロー最小カット定理

programming_algorithm/graph_theory/maximum_flow.txt · 最終更新: 2017/12/03 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0