Hatena::Grouptopcoder

れんしゅうちょう。 このページをアンテナに追加 RSSフィード

 | 

2014-03-20最大流問題について その3

前々回, 前回 に引き続き, 最大流問題についてです.

Dinic 法でのボトルネックは, 各ステップで, dfs によりブロッキングフローを求める部分でした.

前回は, O(nm) だったこの部分を O(n^2) に落としたアルゴリズムを二つ紹介しました.

今回は, ここを O(m \log n), 従って, 全体では O(mn \log n) にするアルゴリズムを紹介します.


前回の二つは, ある意味でまとめて流そうという感じのアルゴリズムでした.

今回のは, どちらかと言えば, Dinic 法の dfs を単純に速くする感じです.


Link/Cut Tree

突然ですが, Link/Cut Tree と呼ばれるデータ構造があります.

Link/Cut Tree は, 有向森(根付き木がいくつかあるもの) に関して, 色々なクエリを処理させられる, 割と強力なデータ構造です.

まず, 森の形状を変えるための基本的クエリとして次の 4 つが挙げられます.

  1. \mathrm{link}(u, v) : ある木の根 u の親を v にする.
  2. \mathrm{cut}(u) : 頂点 u を根とする部分木を切り離す.
  3. \mathrm{find}(u) : 頂点 u を含む木の根を探す.
  4. \mathrm{evert}(u) : u を含む木に含まれる辺の向きを変え, u が根になるようにする.

他に, 例えば次のようなクエリを処理出来ます.

  1. \mathrm{set}(u, x) : 頂点 u に値 x をセットする.
  2. \mathrm{getMinInPath}(u) : 頂点 u から, u を含む木の根までのパスのうち, セットされた値が最小のものを返す.
  3. \mathrm{addToPath}(u, x) : 頂点 u から, u を含む木の根までのパスに含まれる各頂点に対し, セットされた値に x を足しこむ.
  4. \mathrm{size}(u) : 頂点 u を根とする部分木のサイズを取得する.

これらのようなクエリを, (償却計算量の意味で)対数オーダーで処理出来るデータ構造です.

誤解を恐れずに言えば, 切れる Union-Find Tree で, 木構造っぽいクエリの他に, 頂点を端点とする path に Segment Tree と同じような操作をサポートさせられるような感じです.


Link/Cut Tree の実装について.

次の 3 つを読むとよいです.

  1. no title
  2. no title
  3. IJPC 2012 #3: 解説: animals2

自分が実装した時の印象は, 次のような感じでした.

  1. 基本的クエリはそこまで難しくはない. (\mathrm{evert} はちょっと面倒かも.)
  2. 頂点, パスに含まれる頂点へのクエリもそこまで難しくはない.
  3. (上では挙げなかった)辺に対するクエリは, 直接実装するのは難しい. (諦めた)
    • 各辺の間に頂点を追加して, 頂点に対する操作に書き直すと楽.
  4. 木に対する操作は, パスに対する操作よりちょっと面倒くさい. (多分アーベル群程度あれば可能ではある)
    • u を頂点とする部分木のサイズを取得するとか.

Link/Cut Tree を用いた Dinic 法

参考文献1 の 26 ページ下部のあたりから読むのが手っ取り早いです.

Dinic 法の dfs の途中の状態を見てみましょう.

各頂点に対し, 今見ている辺を, \mathrm{iter} なる変数に格納していましたが, これに対応する辺に注目します.

例えば, 次の図のようになっています.

f:id:Mi_Sawa:20140325170631j:image:w360

\mathrm{iter} に対応する辺だけ見ると, 次の図のように, (T に近い側を根として持つ, 内側向きな有向)森になっています.

f:id:Mi_Sawa:20140325170630j:image:w180

dfs を進めるのあたって, 森の上では次のような操作が行われています.

  1. \mathrm{iter}(u) を進める <=> u の親を入れ替える.
  2. dfs を一段階深くする <=> 注目している頂点を, 今の頂点の親にする.
  3. S から T へのパスが見つかる <=> S を含む木の根が T.
  4. 見つかったパスに流れるフロー量 <=> S から根に向けたパスのうち, 容量が最も少ないヤツ.
  5. 見つかったパスにフローを流す <=> S から根に向けたパスにフローを流す.

ちょっと考えると, 次の操作をサポートする Link/Cut Tree を用意すれば, 対応する操作を Link/Cut Tree 上で実現出来る事が解ります. (容量は, 辺ではなく, 辺の下側の頂点に持たせます)

  1. \mathrm{link}(u, v) : ある木の根 u の親を v にする.
  2. \mathrm{cut}(u) : 頂点 u を根とする部分木を切り離す.
  3. \mathrm{find}(u) : 頂点 u を含む木の根を探す.
  4. \mathrm{set}(u, x) : 頂点 u に値 x をセットする.
  5. \mathrm{get}(u) : 頂点 u にセットされた値を見る.
  6. \mathrm{getMinInPath}(u) : 頂点 u から, u を含む木の根までのパスに含まれる頂点のうち, セットされた値が最小のものを返す.
  7. \mathrm{addToPath}(u, x) : 頂点 u から, u を含む木の根までのパスに含まれる各頂点に対し, セットされた値に x を足しこむ.

具体的には, 次のようにすればよいです.

  1. \mathrm{find}(S) = T であれば, パスが見つかっているので, 流すフェーズへ. そうでなければパスを探すフェーズへ.
    • S から T へのパスを探すフェーズ:
      • u = \mathrm{find}(S) とする.
      • \mathrm{iter}(u) を進め, 使える辺 (容量正かつ T 方面に行く辺) を探す.
      • 使える辺があった時:
        • \mathrm{iter}(u) に対応する辺を e=(u, v) とする.
        • \mathrm{set}(u, e.\mathrm{cap}) し, \mathrm{link}(u, v) する.
        • 1. へ戻る.
      • 使える辺が無かった時: (現状のフローで, u-Tブロッキングされている.)
        • u = S の時, ブロッキングフローになっているので, 今使われている辺 e に対し, \mathrm{unuse}(e) をして停止.
        • u \neq S とする. u を使えない頂点としてマークし, 以後使わない事にする.
        • 今使われている e = (w, u) の形の辺に対し, \mathrm{unuse}(e) を行う.
        • 1. へ戻る.
    • S から T へのパスに流すフェーズ:
      • f = \mathrm{get}(\mathrm{getMinInPath}(S)) とする.
      • \mathrm{addToPath}(S, -f) する.
      • \mathrm{get}(\mathrm{getMinInPath}(S)) == 0 である間, 次を繰り返す.
        • u = \mathrm{getMinInPath}(S) とする.
        • \mathrm{iter}(u) に対応する辺を e に対し, \mathrm{unuse}(e) する.
      • 1. へ戻る.

ここで, e = (u, v) に対する \mathrm{unuse}(e) は, 次のような操作です.

  1. 使われたフロー量 f = e.\mathrm{cap} - \mathrm{get}(u) を, ee の逆辺に適用する.
  2. \mathrm{cut}(u) をし, \mathrm{set}(u, \infty) する.

また, 実装がややこしくなりますが, Dinic 法と同じく, bfs と dfs を逆から行うことが出来ます.


計算量

各辺につき, 高々一回ずつ \mathrm{link}, \mathrm{cut} する.

また, \mathrm{getMinInPath} とか \mathrm{addToPath} は, 高々 \mathrm{cut} と同じくらいしかしない.

従って, ブロッキングフローを求めるのに, O(m \log n), 合計 O(mn \log n).


ソース

ここ に置いておきました.

拡張のしやすさとか, 機能と拡張性を犠牲にして, 速さとかを重視しているので, Link/Cut Tree 部分がごちゃごちゃしています. (つってもそんなに速くないかもしれないですが.)

あと, L/C Tree は, Dinic だとこういうクエリしか来ないからとかいうので, 本来であれば必要なコードを削っていたりもするので, このままライブラリに転用はしないほうが良いです.


実測

例によって, どういうデータが欲しいかに従って, 自分で計測して下さい.

前回と同じデータで, Dinic 法と比較してみると, 次のようになっていました.

前と同様, グラフの構築にかかる時間は無視しています.

ケース 頂点数 辺数 Dinic (sec) L/C Dinic (sec) Wave (sec)
ランダムを80ケース(合計) 5000 1000000 1.9 1.8 5.3
ランダムを40ケース(合計) 50000 1000000 2.0 2.1 10.0
ランダムを13ケース(合計) 500000 1000000 1.9 2.3 10.0
密なランダムを5ケース(合計) 5000 n(n-1)/2 2.1 1.1 3.2
完全グラフを15ケース(合計) 2000 n(n-1) 2.0 1.9 3.6
ワーストケース1つ目 7000 13997 1.9 5.3 5.1
ワーストケース2つ目 628 33491 2.0 0.7 0.1

実測でも, 思ったほど遅くないです.

ワーストケースの一つ目は, dfsO(n) 回必要だけど, 各 dfs では割と自明なフローをひょいと流すだけなので, ブロッキングフローを探すアルゴリズムによる差は出にくく, 逆に定数倍が大きく出てくるので, そんな感じになっています.


結論

まぁ, 使うかどうかは置いておいて, 面白い.


次回予告

やる気と時間があれば, Push/Relabel 法について.

やりたい事が大体終わってきたので, 続かない確率割と高まっている.


参考文献

1. は no title から読めます.

  1. Daniel D. Sleator, Robert Endre Tarjan (1983), A data structure for dynamic trees, Journal of Computer and System Sciences, vol.26, no.3, pp. 362-391
 |