Union-Find data structure
次の2つの操作を高速で実行することのできるデータ構造にUnion-Findと呼ばれるものがある.
- Find: どの集合に属しているかを決定する.
- Union: 2つの集合を1つにする.
聞いたことはあってもきちんと理解していないので少し勉強してみる.
実装
とりあえずjavaで書いてみた.
import static java.util.Arrays.*; class UnionFind { private int[] data; public UnionFind(int size) { data = new int[size]; fill(data,-1); } int find(int x){ return (data[x]<0)? x : (data[x] = find(data[x])); } boolean union(int x, int y){ x = find(x); y = find(y); if(x!=y){ if(data[y]<data[x])data[x]=y; else if(data[y]>data[x])data[y]=x; else data[data[y]=x]--; } return x!=y; } int rank(int x){ return -data[find(x)]-1; } }
かなりシンプルなデータ構造である.
ポイントをまとめると
- 子が親のノードへのリンクを持つ有向森
- 根は葉からの高さ(ランク)のマイナスを持つ
- union/findを行うときに木の高さを低くする
アッカーマン関数の逆関数ってなんぞや
アッカーマン関数の定義式は
とてつもなく大きな数を返す関数として有名である.
分割統治法
Union-Findの解析の準備として分割倒置法について考える.
典型的な分割倒置法は次のような形である.
- サイズが1ならば結果は自明
- サイズが1より大きいとき
- サイズがf(n)未満の部分問題に分割
- n/f(n)個の部分問題をそれぞれ再帰的に解く
- 解を統合する
計算量をX(n)とすると,
これの解の一つとして
を考える.
ただし,
である.
具体的なに対するは次のようになる.
Union-Findの解析
結局,分割統治を行って解析する.
戦略としてはまずUnionだけについて考えて,次にFindを一般化したものを考え解析する.
定義 ランク
ノードxについてランクr(x)を葉からの高さ(の最大値)として定義する.
定義 rank forest
任意のノードxと任意のi ([tex:0\le i
補題
を最大のランクがrであるrank forestとし,Xをそのノードの集合とする.
また,
- (top)
- (bottom)
とする.
このとき,はrank forestであり,
である.
証明は,rank forestになるのは自明.
になるのは1段づつしたから削ることを考えればよい.
定義
f(m,n,r)をノード数がnの最大ランクがrのrank forestにおいて,findがm回来るときの最大コストと定義する.
自明な上界として
定義
関数についてと定義する.
まとめ
アルゴリズムは簡単だが解析がやたら難しい.
まだ,完全には理解していないし,間違った記述をしているところがありそうなので,気づいた方はご指摘ください.
(かなり端折った証明をしているからこれだけでは理解できないだろうけど...)