[ 読者の想定 ]
- ネットワーク/最大フロー問題が分かっている
- preflow-push (preflow push-relabel) アルゴリズムを知っている
- preflow-push アルゴリズムを改良したい!
なおPython3.7で実装したプログラムをGitHubで公開していますので, ぜひ.
概要
preflow-push algorithm [1][2] はネットワーク$G=(V, E)$上の最大フローを求めるアルゴリズムです. 以下では始点(source)を$s$, 終点(sink, target)を$t$と書くことにします.
preflowとはフロー保存則を無視したフローのことで ノードから出るフロー量 - ノードに入るフロー量(=: excess value(超過量) )が0よりも大きいことを許したものです. このアルゴリズムではまず始点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 network contains 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 AlgorithmとHighest-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によって距離ラベルをいつかは最低終点までの最短ホップ数は増やすことになるので, それならば最初から増やしておこうというものです
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上で公開しています。