Help us understand the problem. What is going on with this article?

Preflow Push-Relabel (プリフロープッシュリラベル) アルゴリズム 改良

More than 1 year has passed since last update.

[ 読者の想定 ]

  1. ネットワーク/最大フロー問題が分かっている
  2. preflow-push (preflow push-relabel) アルゴリズムを知っている
  3. preflow-push アルゴリズムを改良したい!

なお, Python3.7で実装したプログラムをGit hubで公開していますので, ぜひ.

概要

preflow-push algorithm [1][2] はネットワーク$G=(V, E)$上の最大フローを求めるアルゴリズムです. 以下では, 始点(source)を$s$, 終点(sink, target)を$t$を書くことにします.

preflowとはフロー保存則を無視したフローのことで, ノードから出るフロー量 - ノードに入るフロー量(=: excess value(超過量))が大きいことを許したものです. このアルゴリズムでは, まずsから流せるだけpreflowを流し, 距離ラベルdを適切に管理しながら, 流しすぎた分を始点に返すことで最終的に, フロー保存則を満たした maxフローを取得します.

超過量が正の点をactive node(活動点)と呼び, active nodeがグラフからなくなるまで, あるactive nodeに対し, もしその点を始点とするadmissible arc(可能辺)があれば, push操作を, そうでなければ relabel操作を繰り返します. 擬似コードを書くとこんな感じ.

preprocess # set distance label and flow each arc (s, j) in E
while the network contains an active node:
    select an active node i
    if the network contains an admissible arc (i, j):
        push(i, j)
    else:
        relabel(i)

push操作とrelabel操作, その他用語については[3]もしくは[2]を参考にしてください. これをGeneric prelow-push algorithmと呼ぶことにします.

擬似コードを見てわかるように, このアルゴリズムは非常にシンプルなので, 次のような任意性を含みます[4]

  • 活動点選択の任意性
    • 一度選ばれたactive node $i$について, iがnon active nodeになるか, $i$からの可能辺がなくなるまでiを選択し続ける
    • active nodeをどの順番に選ぶか
  • 流量の可能性
    • push操作においてどれほどの流量を流すか
  • データ構造の選択の任意性
  • 他の技術との併用の任意性

任意性があるということは, 改良の余地があるということでもあります.

この記事では, 計算量を削減する改良として, FIFO Preflow-Push AlgorithmHighest-Label Preflow-Push Algorithmを, 最悪計算量は変わらないheuristicsな改善手法として, Global labeling, Gap-relabeling, Freeze operation[5]を紹介したいと思います.

計算量のまとめ

$n := |V|, m := |E|$

手法 計算量
Generic preflow-push algorithm $O(n^2m)$
FIFO preflow-push algorithm $O(n^3)$
Highest-label preflow-push algorithm $O(n^2\sqrt{m})$
Excess scaling algorithm (今回紹介なし) $O(nm+n^2logU)$

計算量改善

FIFO preflow-push algorithm

FIFO preflow-push algorithmは Generic preflow-push alogirthmに次のような工夫を行ったものです.

  • active nodeはqueueで管理する. 新たにactive nodeが生まれる or relabelされるたびにqueueの末尾に追加する
  • push/relabel対象のactive node $i$はqueueの先頭から取り出す
  • active node $i$がnon active または relabel されるまで $i$を選択し続ける
preprocess # set distance label and flow each arc (s, j) in E
LIST = queue({j: (s, j) in E})
while the network contains an active node:
    select an active node i
    if the network contains an admissible arc (i, j):
        push(i)
    else:
        relabel(i)

Highest preflow-push algorithm

Highest preflow-push algorithmは Generic preflow-push alogirthmに次のような工夫を行ったものです

  • 距離ラベルが最大のactive nodeを push/relabel対象とする.
  • 距離ラベルが取りうる値は$0 から 2n-1$までの整数値[2]なので, バケツソートの要領で最大active nodeを取り出すことができる.
preprocess # set distance label and flow each arc (s, j) in E
LIST(0) = {j: (s, j) in E}
hstar = 0 # hstar is the max label of active nodes
while LIST is not empty:
    while LIST(hstar) is empty:
        hstar = hstar - 1
    pop active node i from LIST(hstar)
    while excess value of i > 0 or admissible arc (i, j):
        push(i, j)
        if j not in LIST:
            add j to LIST(d(j))
    if excess value of i > 0:
        relabel(i)
        add i to LIST(d(i))
        if d(i) > hstar:
            hstar = d(i)

実験 その1

このネットワークで実験. $s$を青色, $t$を緑色, active nodeを赤色, excess valueをその濃さ, non active nodeを水色で, アルゴリズム実行中のノードについている番号は距離ラベルを表しています. また, アルゴリズムの良さを, push/relabel operationの回数で測ることにします.

Genetic preflow-push algorithm

operation 回数
push 19回
relabel 20回

FIFO preflow-push algorithm

operation 回数
push 16回
relabel 14回

Highest preflow-push algorithm

operation 回数
push 16回
relabel 11回

FIFO, Highsetの方がGeneticよりも, より少ないpush/relabelの回数でmaxフローが求められていることがわかります。

Heuristics

次は, heuristicsの方法です. Geneticにそれぞれの手法を適用した場合の擬似コードを載せています.

Global labeling

  • preprocess 直後に, node $i$($s$以外)の距離ラベルを次のように設定する
    • node i から終点までの最短枝数
    • これは残余ネットワーク(residual netowrk)上での$t$からの幅優先探索(計算量($O(m)$)で見つけることができる.
  • 気持ちとしては, 例えば$t$とつながるnodeはtへフローを流すために, relabelによって距離ラベルをいつかは最低1増やすことになるので, それならば最初から増やしておこうというものです


preprocess # set distance label and flow each arc (s, j) in E
global_laveling # set distance from t label by BDS
while the network contains an active node:
    ...

Gap-relabeling

  • アルゴリズム中, 距離ラベルdがちょうど$g (0 < g < n)$ となる点が存在しないとき, $n > d(v) > g$ であるnode $v$のラベルを$n$に変更する

    • ギャップが生じた瞬間に, そのギャップ間を新しくフローが流れることはない
  preprocess # set distance label and flow each arc (s, j) in E
  while the network contains an active node:
    select an active node i
      if the network contains an admissible arc (i, j):
          push(i, j)
      else:
          relabel(i)
          if exists g (0 < g < n) such that there is not node i where d(i) = g:
              for node i where g < d(i) < n:
                  relabel d(i) = n

Freeze operation

  • $d(v) \geq n$ であるようなnode $v$ をFreeze(凍結)し,これ以降activeとは考えず, push操作とrelabel操作は適用しない
  • アルゴリズム終了後に, 超過量が正の点から$s$に超過量分戻していく (計算量$O(nm)$で可能)
    • super souceを用意し, 超過量が正の点へ, 容量が超過量であるような枝を張ると, 始点終点の任意の点で, 常に入ってくる枝の容量の和が, 出ていく枝の容量の和以下であるようなネットワーク上のmaxflow問題として変換できる. この場合, maxflow値はsuper souceから出る枝の容量の和であるので, あとは実際にフローを求めれば良い. 次のようなアルゴリズムを考えました
    • frozen nodeがネットワークからなくなるまで以下を繰り返す.
    • sからの距離が最大のfrozen node uを選択する
    • frozen node uの超過量が0になるまで以下を繰り返す.
      • DFSによりuから深さ優先探索により残余ネットワーク上のパスを探索していく
      • $s$または他のfrozen nodeにたどり着いたら, その点に向かってパス上をmin(超過量, min(パス上の枝の残余ネットワーク容量))分のフローを流す
    • 今回考えたアルゴリズムが最良かどうかは分かりません.
preprocess # set distance label and flow each arc (s, j) in E
while the network contains an active node:
    select an active node i
    if the network contains an admissible arc (i, j):
        push(i, j)
    else:
        relabel(i)
        if d(i) >= n:
            freeze node i and change i to non active

if the network contains a freeze node:
    select a frozen node u with the distance from s being largest
    while excess value of u > 0:
        find (u-v) path on the residual network with v is t or other frozen node by DFS
        delta = min(excess value of u, min(capacity of edge which the path has in the residual network))
        push delta flow u to v

実験 その2

このネットワークで実験. Highest preflow-push algorithmにこれらを適用していきます. 凍結点を灰色で表しています.

Global labeling

operation 回数
push 16
relabel 8

Gap-relabeling

operation 回数
push 16
relabel 13

Freeze operation

operation 回数
push 14
relabel 11

これらのheuristicsは組み合わせることができます.

Global labeling & Gap-relabeling & Freeze operation

operation 回数
push 13
relabel 7

まとめ

Genetic preflow-push algorithmに改良を施すことで, アルゴリズム全体のpush/relabelの回数を減らすことができた. Global labeling と Gap-relabelingは実装が簡単で, 効果が大きい. (Freeze operationは実装が少し大変)

計算量の観点では, 今回紹介していない, Excess scaling algorithmが最小なので, 動的木と合わせて勉強したいです.

参考文献

[1] Goldberg, Andrew V., and Robert E. Tarjan. A new approach to the maximum-flow problem. Journal of the ACM (JACM)* 35.4 (1988): 921-940.
[2] R.K. Ahuja, T.L. Magnanti, and J.B. Orlin. Network Flows Theory, Algorithms, and Applications. (1993) Prentice-Hall.
[3]@a-lilas, 最大流問題をプリフロー・プッシュ (Push-Relabel) 法 で解く
[4] 岩野和生, 最大流アルゴリズムの最近の発展とその背景-II, 情報処理 Vol. 31 No.1 (1990)
[5] J.Kleinberg, E. Tardos(著), 浅野孝夫, 浅野泰仁, 小野孝男, 平田富夫(翻訳) (2009) アルゴリズムデザイン, 共立出版.

今回作成したコード

Git Hub上で公開しています。

https://github.com/nariaki3551/max-flow

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした