PowerPoint プレゼンテーション

1
最下位共通先祖問題と MF 木
＊＊ここで理解すべき内容＊＊
 抽象データ型
 Merge-Find 集合（Union-Find 集合）
 データ構造
 Merge-Find 木（Merge-Find tree）
 計算量評価方法
 均し計算量（amortized complexity）
2
例として考える問題
オフライン
最下位共通先祖
問題
3
オフライン最下位共通先祖問題
 Off-line Lowest Common Ancestors Problem
 入力：
 根付き木 T = (V,E)
 点対の集合 P = { p=(v,w) | v, w は T の点 }
 出力：
 各点対 p=(v,w)∈P に対する
（木 T 上での）最下位共通先祖 anc(p)
4
最下位共通先祖
 木 T 上の質問点対 p=(v,w) に対する
最下位共通先祖 anc(p) = a
木 T の点 a で，以下の性質を持つもの
 v と w の共通の先祖であり，
 a の真の子孫には
v と w の共通の先祖が無い
5
オフライン最下位共通先祖問題
 質問点対の集合 P
P = { (c,h), (e,f),
(f,g), (g,h) }
木T
b
d
a
g
c
h
e
f
最下位共通先祖
 anc( (c,h) ) = b
 anc( (e,f) ) = e
 anc( (f,g) ) = b
 anc( (g,h) ) = d
6
オフライン（off-line）問題
 オフライン（off-line）問題
 全ての質問を予め知った上で
各質問に対する答えを求めるもの
 オンライン（on-line）問題
 全質問を予め知ることができず，
質問毎に答えを出すもの
7
オフライン最下位共通先祖問題
に対するアルゴリズム
8
アルゴリズム
 木 T を深さ優先探索（DFS）して求める．
 void DFS( v, T ) {

行きがけの処理 ;

c := lm_child(v) ;
/* c を v の長男に */

while ( 子 c が存在する ) {

DFS( c, T ) ;

子 c の情報を利用する処理 ;

c := r_sibling( c ) ; /* c を次弟に */

}

帰りがけの処理 ;
 } /* end DFS */
 帰りがけに，最下位共通先祖が求められる ?
r
v
c
c'
9
点 v からの帰りがけ時の検査
 (v,w)∈P なる質問点対が存在し
w は既に探索済みか？
b
d

もし，そうならば，
 w の先祖で探索中の点の内，
最下位にある点 a は，
v と w の最下位共通先祖
anc( (v,w) )
a
w
e
v
10
必要な操作
1. 点 v を含む質問点対 (v,w)
∈P が存在するか否かの検査
b
d
2. もう一方の点 w は既に探索
済みか否かの検査
3. w の探索中の先祖で，最下
位の点の探索
 これらを効率良く実行したい
a
w
e
v
11
必要な操作 1
 点 v を含む質問点対 (v,w)∈P
が存在するか否かの検査に対しては，
 木 T の各点 v に対して，
v を含む質問点対 p=(v,w) ∈ P の集合
P(v) = { p | p=(v,w)∈ P }
を覚えておく
w
v
w'
12
必要な操作 2
b
 点 v を含む質問点対 (v,w)∈P
のもう一方の点 w が，
既に探索済みか否かの検査は
d
a
 点に

未探索

探索中

探索済み
の印を付けておけば良い
w
e
v
13
必要な操作 3
b
 点 w の探索中の先祖で，
最下位のもの a を求めるには，
d
 “探索中” の各点 a に対して，
集合 U(a) = { a }
 { w, ・・・
a
}
 w は a の子孫で探策済み，
 w の先祖で a より下に探索中の点は無い
を覚える
 w ∈U(a) と現在探索中の点 v との
最下位共通先祖は a = anc( (v,w) )
 U(a) の初期値は， U(a) = { a } とする
w
e
v
14
アルゴリズムの例
集合 U(・) に対する操作
15
木 T と集合 U(・) および P(・)
木T
b
d
a
g
c
h
e
f
A = U(a) = { a }
B = U(b) = { b }
C = U(c) = { c }
D = U(d) = { d }
E = U(e) = { e }
F = U(f) = { f }
G = U(g) = { g }
H = U(h) = { h }
P(c) = { (c,h) }
P(e) = { (e,f) }
P(f) = { (e,f), (f,g) }
P(g) = { (f,g), (g,h) }
P(h) = { (c,h), (g,h) }
16
木 T の深さ優先探索
木T
探索中
b
d
a
g
c
h
e
f
A = U(a) = { a }
B = U(b) = { b }
C = U(c) = { c }
D = U(d) = { d }
E = U(e) = { e }
F = U(f) = { f }
G = U(g) = { g }
H = U(h) = { h }
P(c) = { (c,h) }
P(e) = { (e,f) }
P(f) = { (e,f), (f,g) }
P(g) = { (f,g), (g,h) }
P(h) = { (c,h), (g,h) }
17
木 T の深さ優先探索
探索中
木T
b
d
a
g
c
h
e
f
A = U(a) = { a }
B = U(b) = { b }
C = U(c) = { c }
D = U(d) = { d }
E = U(e) = { e }
F = U(f) = { f }
G = U(g) = { g }
H = U(h) = { h }
P(c) = { (c,h) }
P(e) = { (e,f) }
P(f) = { (e,f), (f,g) }
P(g) = { (f,g), (g,h) }
P(h) = { (c,h), (g,h) }
18
木 T の深さ優先探索
木T
b
d
a
g
c
h
e
f
A = U(a) = { a }
B = U(b) = { b }
C = U(c) = { c }
D = U(d) = { d }
E = U(e) = { e }
F = U(f) = { f }
G = U(g) = { g }
H = U(h) = { h }
P(c) = { (c,h) }
P(e) = { (e,f) }
P(f) = { (e,f), (f,g) }
P(g) = { (f,g), (g,h) }
P(h) = { (c,h), (g,h) }
19
木 T の深さ優先探索
木T
b
d
a
g
c
h
e
f
A = U(a) = { a }
B = U(b) = { b }
C = U(c) = { c }
D = U(d) = { d }
E = U(e) = { e }
F = U(f) = { f }
G = U(g) = { g }
H = U(h) = { h }
P(c) = { (c,h) }
P(e) = { (e,f) }
P(f) = { (e,f), (f,g) }
P(g) = { (f,g), (g,h) }
P(h) = { (c,h), (g,h) }
20
点 g の探索終了： P(g) の検査
木T
b
d
a
c
h
g
探索済
e
f
f, h は未探索
⇒ 何もしない
A = U(a) = { a }
B = U(b) = { b }
C = U(c) = { c }
D = U(d) = { d }
E = U(e) = { e }
F = U(f) = { f }
G = U(g) = { g }
H = U(h) = { h }
P(c) = { (c,h) }
P(e) = { (e,f) }
P(f) = { (e,f), (f,g) }
P(g) = { (f,g), (g,h) }
P(h) = { (c,h), (g,h) }
21
点 g から戻る： A と G の併合
木T
A = U(a) = { a, g }
b
d
a
g
c
h
e
f
A = U(a) = { a }
B = U(b) = { b }
C = U(c) = { c }
D = U(d) = { d }
E = U(e) = { e }
F = U(f) = { f }
G = U(g) = { g }
H = U(h) = { h }
P(c) = { (c,h) }
P(e) = { (e,f) }
P(f) = { (e,f), (f,g) }
P(g) = { (f,g), (g,h) }
P(h) = { (c,h), (g,h) }
22
点 a に戻った
木T
b
d
a
g
c
h
e
f
A = U(a) = { a, g }
B = U(b) = { b }
C = U(c) = { c }
D = U(d) = { d }
E = U(e) = { e }
F = U(f) = { f }
G = U(g) = { g }
H = U(h) = { h }
P(c) = { (c,h) }
P(e) = { (e,f) }
P(f) = { (e,f), (f,g) }
P(g) = { (f,g), (g,h) }
P(h) = { (c,h), (g,h) }
23
点 a の探索終了：
木T
b
d
a
g
c
h
e
f
P(a) は空
A = U(a) = { a, g }
B = U(b) = { b }
C = U(c) = { c }
D = U(d) = { d }
E = U(e) = { e }
F = U(f) = { f }
G = U(g) = { g }
H = U(h) = { h }
P(c) = { (c,h) }
P(e) = { (e,f) }
P(f) = { (e,f), (f,g) }
P(g) = { (f,g), (g,h) }
P(h) = { (c,h), (g,h) }
24
点 a から戻る： A と D を併合
木T
b
d
a
g
c
h
A = U(a) = { a, g }
B = U(b) = { b }
D = U(d) = { a, d, g }
C = U(c) = { c }
D = U(d) = { d }
E = U(e) = { e }
F = U(f) = { f }
e
G = U(g) = { g }
H = U(h) = { h }
f
P(c) = { (c,h) }
P(e) = { (e,f) }
P(f) = { (e,f), (f,g) }
P(g) = { (f,g), (g,h) }
P(h) = { (c,h), (g,h) }
25
点 d に戻った
木T
b
d
a
g
c
h
e
f
A = U(a) = { a, g }
B = U(b) = { b }
C = U(c) = { c }
D = U(d) = { a, d, g }
E = U(e) = { e }
F = U(f) = { f }
G = U(g) = { g }
H = U(h) = { h }
P(c) = { (c,h) }
P(e) = { (e,f) }
P(f) = { (e,f), (f,g) }
P(g) = { (f,g), (g,h) }
P(h) = { (c,h), (g,h) }
26
点 h を深さ優先探索
木T
b
d
a
g
c
h
e
f
A = U(a) = { a, g }
B = U(b) = { b }
C = U(c) = { c }
D = U(d) = { a, d, g }
E = U(e) = { e }
F = U(f) = { f }
G = U(g) = { g }
H = U(h) = { h }
P(c) = { (c,h) }
P(e) = { (e,f) }
P(f) = { (e,f), (f,g) }
P(g) = { (f,g), (g,h) }
P(h) = { (c,h), (g,h) }
27
点 h の探索終了： P(h) の検査
木T
b
d
a
c
h
e
f
g
g は探索済み
⇒ anc((g,h)) は?
A = U(a) = { a, g }
B = U(b) = { b }
C = U(c) = { c }
D = U(d) = { a, d, g }
E = U(e) = { e }
F = U(f) = { f }
G = U(g) = { g }
H = U(h) = { h }
P(c) = { (c,h) }
P(e) = { (e,f) }
P(f) = { (e,f), (f,g) }
P(g) = { (f,g), (g,h) }
P(h) = { (c,h), (g,h) }
28
点 g を含む集合 U(・) の探索
木T
b
d
a
c
h
e
f
g
g ∈ U(d)
⇒ anc((g,h)) = d
A = U(a) = { a, g }
B = U(b) = { b }
C = U(c) = { c }
D = U(d) = { a, d, g }
E = U(e) = { e }
F = U(f) = { f }
G = U(g) = { g }
H = U(h) = { h }
P(c) = { (c,h) }
P(e) = { (e,f) }
P(f) = { (e,f), (f,g) }
P(g) = { (f,g), (g,h) }
P(h) = { (c,h), (g,h) }
29
点 h から戻る： H と D を併合
a
g
A = U(a) = { a, g }
木T
D = U(d) = { a, d, g, h } B = U(b) = { b }
C = U(c) = { c }
b
D = U(d) = { a, d, g }
E = U(e) = { e }
F = U(f) = { f }
d
c
e
G = U(g) = { g }
H = U(h) = { h }
f
h
P(c) = { (c,h) }
P(e) = { (e,f) }
P(f) = { (e,f), (f,g) }
P(g) = { (f,g), (g,h) }
P(h) = { (c,h), (g,h) }
30
点 d に戻った
木T
b
d
a
g
c
h
e
f
A = U(a) = { a, g }
B = U(b) = { b }
C = U(c) = { c }
D = U(d) = { a, d, g, h }
E = U(e) = { e }
F = U(f) = { f }
G = U(g) = { g }
H = U(h) = { h }
P(c) = { (c,h) }
P(e) = { (e,f) }
P(f) = { (e,f), (f,g) }
P(g) = { (f,g), (g,h) }
P(h) = { (c,h), (g,h) }
31
点 d から戻る
木T
b
d
a
c
h
e
f
g
P(d) は空
⇒ B と D を併合
A = U(a) = { a, g }
B = U(b) = { b }
C = U(c) = { c }
D = U(d) = { a, d, g, h }
E = U(e) = { e }
F = U(f) = { f }
G = U(g) = { g }
H = U(h) = { h }
P(c) = { (c,h) }
P(e) = { (e,f) }
P(f) = { (e,f), (f,g) }
P(g) = { (f,g), (g,h) }
P(h) = { (c,h), (g,h) }
32
点 b に戻った
木T
b
d
a
g
c
h
e
f
A = U(a) = { a, g }
B = U(b) = { a, b, d, g, h }
C = U(c) = { c }
D = U(d) = { a, d, g, h }
E = U(e) = { e }
F = U(f) = { f }
G = U(g) = { g }
H = U(h) = { h }
P(c) = { (c,h) }
P(e) = { (e,f) }
P(f) = { (e,f), (f,g) }
P(g) = { (f,g), (g,h) }
P(h) = { (c,h), (g,h) }
33
点 c を深さ優先探索
木T
b
d
a
g
c
h
e
f
A = U(a) = { a, g }
B = U(b) = { a, b, d, g, h }
C = U(c) = { c }
D = U(d) = { a, d, g, h }
E = U(e) = { e }
F = U(f) = { f }
G = U(g) = { g }
H = U(h) = { h }
P(c) = { (c,h) }
P(e) = { (e,f) }
P(f) = { (e,f), (f,g) }
P(g) = { (f,g), (g,h) }
P(h) = { (c,h), (g,h) }
34
点 c の探索終了： P(c) の検査
a
A = U(a) = { a, g }
h
を含む
U(・)
は?
木T
B = U(b) = { a, b, d, g, h }
⇒ anc((c,h)) = b
C = U(c) = { c }
b
D = U(d) = { a, d, g, h }
E = U(e) = { e }
F = U(f) = { f }
d
c
e
G = U(g) = { g }
H = U(h) = { h }
f
h
g
h は探索済み
⇒ anc((c,h)) は?
P(c) = { (c,h) }
P(e) = { (e,f) }
P(f) = { (e,f), (f,g) }
P(g) = { (f,g), (g,h) }
P(h) = { (c,h), (g,h) }
35
点 c から戻る： C と B を併合
木T
b
d
a
g
c
h
e
f
A = U(a) = { a, g }
B = U(b) = { a, b, d, g, h }
C = U(c) = { c }
D = U(d) = { a, d, g, h }
E = U(e) = { e }
F = U(f) = { f }
G = U(g) = { g }
H = U(h) = { h }
P(c) = { (c,h) }
P(e) = { (e,f) }
P(f) = { (e,f), (f,g) }
P(g) = { (f,g), (g,h) }
P(h) = { (c,h), (g,h) }
36
点 b に戻った
木T
b
d
a
g
c
h
e
f
A = U(a) = { a, g }
B = U(b) = { a, b, c, d, g, h }
C = U(c) = { c }
D = U(d) = { a, d, g, h }
E = U(e) = { e }
F = U(f) = { f }
G = U(g) = { g }
H = U(h) = { h }
P(c) = { (c,h) }
P(e) = { (e,f) }
P(f) = { (e,f), (f,g) }
P(g) = { (f,g), (g,h) }
P(h) = { (c,h), (g,h) }
37
点 e, f へ深さ優先探索
木T
b
d
a
g
c
h
e
f
A = U(a) = { a, g }
B = U(b) = { a, b, c, d, g, h }
C = U(c) = { c }
D = U(d) = { a, d, g, h }
E = U(e) = { e }
F = U(f) = { f }
G = U(g) = { g }
H = U(h) = { h }
P(c) = { (c,h) }
P(e) = { (e,f) }
P(f) = { (e,f), (f,g) }
P(g) = { (f,g), (g,h) }
P(h) = { (c,h), (g,h) }
38
点 f の探索終了： P(f) の検査
a
g
A = U(a) = { a, g }
g
を含む
U(・)
は?
木T
B = U(b) = { a, b, c, d, g, h }
⇒ anc((f,g)) = b
C = U(c) = { c }
b
D = U(d) = { a, d, g, h }
E = U(e) = { e }
F = U(f) = { f }
d
c
e
G = U(g) = { g }
H = U(h) = { h }
f
h
P(c) = { (c,h) }
P(e) = { (e,f) }
P(f) = { (e,f), (f,g) }
g は探索済み
P(g) = { (f,g), (g,h) }
⇒ anc((f,g)) は? P(h) = { (c,h), (g,h) }
39
点 f から戻る： F と E の併合
木T
b
d
a
g
c
h
e
f
A = U(a) = { a, g }
B = U(b) = { a, b, c, d, g, h }
C = U(c) = { c }
D = U(d) = { a, d, g, h }
E = U(e) = { e }
F = U(f) = { f }
G = U(g) = { g }
H = U(h) = { h }
P(c) = { (c,h) }
P(e) = { (e,f) }
P(f) = { (e,f), (f,g) }
P(g) = { (f,g), (g,h) }
P(h) = { (c,h), (g,h) }
40
点 e に戻った
木T
b
d
a
g
c
h
e
f
A = U(a) = { a, g }
B = U(b) = { a, b, c, d, g, h }
C = U(c) = { c }
D = U(d) = { a, d, g, h }
E = U(e) = { e, f }
F = U(f) = { f }
G = U(g) = { g }
H = U(h) = { h }
P(c) = { (c,h) }
P(e) = { (e,f) }
P(f) = { (e,f), (f,g) }
P(g) = { (f,g), (g,h) }
P(h) = { (c,h), (g,h) }
41
点 e の探索終了
a
A = U(a) = { a, g }
f
を含む
U(・)
は?
木T
B = U(b) = { a, b, c, d, g, h }
⇒ anc((e,f)) = e
C = U(c) = { c }
b
D = U(d) = { a, d, g, h }
E = U(e) = { e, f }
F = U(f) = { f }
d
c
e
G = U(g) = { g }
H = U(h) = { h }
f
h
g
f は探索済み
⇒ anc((e,f)) は?
P(c) = { (c,h) }
P(e) = { (e,f) }
P(f) = { (e,f), (f,g) }
P(g) = { (f,g), (g,h) }
P(h) = { (c,h), (g,h) }
42
点 e から戻る： E と B の併合
木T
b
d
a
g
c
h
e
f
A = U(a) = { a, g }
B = U(b) = { a, b, c, d, g, h }
C = U(c) = { c }
D = U(d) = { a, d, g, h }
E = U(e) = { e, f }
F = U(f) = { f }
G = U(g) = { g }
H = U(h) = { h }
P(c) = { (c,h) }
P(e) = { (e,f) }
P(f) = { (e,f), (f,g) }
P(g) = { (f,g), (g,h) }
P(h) = { (c,h), (g,h) }
43
根 b に戻り
木T
B = U(b) = { a, b, c, d, e, f, g, h }
b
d
a
g
c
h
e
f
全探索終了
44
アルゴリズムの記述と
計算量
深さ優先探索の再帰的記述
45
アルゴリズムの概要
 void DFS( v, T )
/* 再帰的関数 */
 木 T の点 v を根とする部分木の深さ優先探索をする関数



入力：
v
T
P(v)

出力：
anc(p) : 各質問点対 p に対する
最下位共通先祖

NODE



各点 v に対して，未探索の印しを付けておき，
集合 U(v) の初期化 U(v) = { v } を行って，
関数 DFS( 木 T の根，T ) を呼ぶ．
c
: NODE（値呼び）
: 木
： v を含む質問点対の集合
/* 局所変数 */
46
アルゴリズムの概要
 void DFS( v, T ) {

v に探索中の印を付ける ;

c := lm_child(v) ;

while ( 子 c が存在する ) {

DFS( c, T ) ;

U(c) を U(v) に併合する ;

c := r_sibling( c ) ;
}

for ( 各 p=(v,w)∈P(v) ) {

if ( 点 w は探索済み ) {

点 w を含む U(a) を求める ;

v に探索済みの印を付ける ;
 } /* end DFS */
実は不要
Merge( )
Find( )
}
}
47
集合 U(・) に対する操作
 指定された点 w を含む集合 U(a) を見出す
Find( w )
計算量を O(TF) と書く
 点 a は点 v と w の最下位共通先祖
 集合 U(v) と U(c) を併合し，U(v) とする
Merge( U(c), U(v), U(v) )
計算量を O(TM) と書く
48
アルゴリズムの計算量
 どの点も高々 1 回しか訪問しない
点 v に関する下記の操作は 1 回しか実行しない
 各点における操作
 Merge の操作
 質問点対があれば，Find の操作
 子を順に探索するための操作
 全 Merge 回数： n-1 回（n ：点の個数）
 全 Find 回数：
m 回（m ：質問点対の個数）
 全計算量
 O( 全 Merge の計算量 + 全 Find の計算量 + その他 )
 = O( (n-1)・TM + m・TF + n )
49
Merge-Find 集合と
Merge-Find 木
Merge, Find に対する
効率的なデータ構造
50
Merge-Find 集合（MF set）
 以下の操作を持った抽象データ型
 Merge( A, B, C )
 互いに素な集合 A および B に対して，
C := A∪B とする手続き．
 A∩B=φなる集合 A, B に対する Union( A, B, C ) と同じ．
 Find( x )
 要素 x を含む集合を返す関数．
 Initialize( A, a )
 要素 a だけから成る集合 A を作る手続き
51
Merge-Find 木
MF 木 U
g
d
B
C
E
F
a
c
e
f
h
b
B = { a, b, d, g, h }
C={c}
E={e}
F={f}
MF 木 U
・各集合を根付き木で表現
・根には集合名を覚える
＊：集合名
・各点は親へのポインタを持つ
＊：要素
52
Merge( C, E, C )
MF 木 U
g
B
C
CE
F
a
c
ee
f
h
b
B = { a, b, d, g, h }
C={c}
E={e}
F={f}
c
d
C = { c, e }
Merge の計算量： TM = O(1)
53
Find( d )
MF 木 U
g
d
B
C
F
a
e
f
h
b
c
B = { a, b, d, g, h }
C = { c, e }
F={f}
MF 木 U の点 d から，
親を辿り，根まで到達すれば，
そこには集合名が書かれている
Find の計算量： TM = O( 木の高さ h(・) )
54
Merge( C, F, F )
C
F
F
e
f
f
?
c
B = { a, b, d, g, h }
C = { c, e }
F={f}
e
c
F
F = { c, e, f }
e
c
f
Find の手間が小さくなるので，
好ましい
55
Merge 操作の改良
木の高さを抑える
Find の効率化になる
56
Merge( A, B, C )
A
a
B
b
C
a
b
|A| > |B|
要素数の少ない木の根を，
もう一方の木の根の子にする
要素数が n の木の
高さは，常に O(logn)
各木の点の個数を覚えていれば，Merge の計算量 TM = O(1)
57
命題
 点の個数の少ない方の木の根を，
個数が大きい方の木の根の子にするように
Merge を行うと，
 どのような順序で Merge が行われても，
木の点の個数を n とすると，
できた木の高さ h(・) は高々
log n 
2
58
数学的帰納法で証明
 n = 1 のとき，木の高さ h(・) は 0 であり，
log2 n   log2 1  0
であるから， n = 1 のとき成立する．
 n < n’ のとき成立を仮定し，n = n’ の時を考える．
 n = n’ の木が，Merge( A, B, C ) でできたとすると，
|A| < n, |B| < n であるから，帰納法の仮定より，
A, B の高さ h(A), h(B) は
h( A)  log2 | A |  log2 n 
，
h( B )  log2 | B |  log2 n 
59
数学的帰納法で証明
 一方，木 C の高さ h(C) は，
C
h(C) = max[ h(A), h(B)+1 ]
a
であるから，
 一般性を失うことなく，
b
h(A)
A
|A|  |B| と仮定できる．
log2 | B |  1 

log2 2 | B | 
 max  log2 n , log2 n    log2 n 
h(B)
B

h (C )  max log2 | A |,
 max log2 | A |,
Q.E.D.
60
Find 操作の改良
木の高さを抑える
後の Find の効率化になる
均し計算量
61
Find の改良
 最下位共通先祖のアルゴリズムの計算量
O( (n-1)・TM + m・TF + n )
= O( (n-1) + m・logn + n ) = O( m・logn + n )
 全 Find の計算量 O( m・logn ) の削減
道の圧縮（path compression）
62
Find の改良（道の圧縮）
 Find の操作において辿った点を
全て木の根の子にする操作
B
B
a
b
g
c
d
e
x
a
c
f
Find(x)
d
x
b
g
e
f
63
Find の改良（道の圧縮）
 Find の最悪計算量 TF のオーダは変化なし
B
B
a
b
g
c
d
e
x
a
c
f
Find(x)
d
x
b
g
e
f
64
Find の改良（道の圧縮）
 しかし，全 Find 操作に要する総計算量
O(m・TF) は

O(m・logn)
O(m・α(n) )
から
になる
 ここで， α(n) はアッカーマン（Ackerman）
関数の逆関数
65
Ackermann’s Function
j
 アッカーマン関数  A1, j   2 :
j2

: i2
 Ai,1  Ai - 1,2 　 Ai, j   Ai - 1, Ai, j - 1 : i, j  2

A2,1  A1,2   22  4
A2,2   A1, A2,1  2
A  2 ,1
A2,3  A1, A2,2   2
A2 , 2 
 2  24  16
22
2
22
2
 216  65,536
A2,4   A1, A2,3  2 A2,3  265,536  1020,000
A3,1  A2,2  16
A4,1  A3,2  A2, A3,1  2 A3,1  216  65,536
66
アッカーマン関数の逆関数
 pseudo-inverse function of Ackermann’s function
 n   min　i  1　| Ai,1  log2 n　   n, n 


 m
 m, n   mini  1 | A i,     log2 n
  n 


n  2 Ai ,1
n  2 A1,1  2  log2 n  A1,1　  n   1
n  2 A2,1  22  log2 n  A2,1　  n   2
n2
A 3,1
 2  log2 n  A3,1　  n   3
16
n  2 A4,1  265536  log2 n  A4,1　  n   4
67
アッカーマン関数の逆関数
 アッカーマン（Ackerman）関数の逆関数
α(n) は
 n < 216 なる n に対して， α(n) ≦ 3
 216 ≦ n < 265,536
なる n に対して，
α(n) = 4 なので
 実用上，定数 O(1) と考えても良い．
68
均し計算量
 均し計算量（amortized time complexity）
 ある操作 A の均し計算量とは，
 A が何回か繰返された時，
 その最悪総計算量を，
繰返し回数で割った
操作 A の 1 回当たりの計算量
69
均し計算量
 MF 木の Find 操作に関しては，
 Merge と Find がどのような順序で行われても，
 m 回の Find に要する総計算量は，高々
O( m・α(n) ) なので，
 Find １回当たりの計算量（均し計算量）は

O(α(n) )
70
均し計算量
 最下位共通先祖を求めるアルゴリズムを
効率化するには，
 Find の最悪計算量を小さくするのではなく
 全 Find に要する総計算量を
小さくしなければならない
 すなわち，Find の均し計算量を小さくす
れば良い
71
均し計算量
 最悪計算量を小さくするデータ構造は，
しばしば，複雑で，実際の計算時間が長い
 均し計算量を小さくするデータ構造は，
単純で，実際の計算時間も小さくなる
ことが多い
 このため，均し計算量は，
データ構造を考える上での重要な概念
72
データ構造の詳細
最下位共通先祖問題に対する
アルゴリズム実現用
73
木 T に必要なデータ構造
 集合 U(・) ： MF 木で実現する
 Merge :
 Find ：
集合名を指定する
要素名を指定する
 木 T = (V,E) の各点 v∈V に対して
 lm_child(v) ： v の長男
 r_sibling(v) ： v の次弟
 mark(v) ：
未探索，探索中，探索済みの印
 集合 P(v) ：
v を含む質問点対の集合
 集合 U(v) ：
集合名 U(v) を持つ MF 木の根
 MF点 MFnode(v) ： v を示す MF 木内の点
74
MF 木のデータ構造
 MF 木の根が持つべきデータ
 set_name : その木が表す集合の名称 U(・)
 size ：
その木に含まれる要素の個数
 MF 木の点が持つべきデータ
 parent : その点の親（根まで辿れるように）
MF 木の点用のセル
parent
set_name size
75
Merge-Find 木
MF 木 U
U(b)
U(c)
U(f)
a
e
f
g
h
b
U(b)
U(c)
U(f)
・
・
・
b 5
c 2
f 5
c
d
根には，集合名 U(v) の
v だけを書いておく
76
木 T のデータ構造
 各点 v∈V に対して
 lm_child(v) ：長男のセルへのポインタ
 r_sibling(v) ：次弟のセルへのポインタ
 mark(v) ：
未探索，探索中，探索済みの印
 集合 P(v) ：連結リストへのポインタ
 集合 U(v) ： MF 木の根のセルへのポインタ
 MF点 MFnode(v) ： MF 木内の点のセルへのポインタ
木 T の点用のセル
mark
lm_child
U(・)
Mfnode(・)
P(・)
r_sibling
77
木 T のデータ構造
mark U P(・)
M U ・
LmC
RSb
Mfn ・ Mfn
木T
c h・
b
d
a
c
M U ・
Mfn
e
h
M U
Mfn ・
e f ・
f
M U ・
Mfn
M U
・ Mfn ・
M U
・ Mfn ・
c h
g
M U
・ Mfn ・
P(・) 用のセル： g h ・
M U
・ Mfn
e f ・
f g
g h・
g h・
78
木 T と MF 木との関連
M U ・
Mfn ・
M U
M U ・
MfnMfn
b
d
a
c
h
M U ・
Mfn
e
f
g
MF 木
M U
・ Mfn
M U
・ Mfn ・
M U
Mfn ・
M U
・ Mfn ・
M U
M U
・ Mfn ・
Mfn
・
g 1
・
a 1
・
d 1
・
f 1
79
木 T と MF 木との関連
M U ・
Mfn ・
点 a に戻った時点
M U ・
Mfn
b
d
a
g
a
c
h
e
f
g
M U ・
Mfn
M U
・ Mfn
M U
・ Mfn ・
M U
Mfn ・
M U
・ Mfn ・
M U
・ Mfn ・
・
a 21
MF 木
g 1
・
d 1
・
f 1
80
木 T と MF 木との関連
M U ・
Mfn ・
点 a に戻った時点
d
b
d
a
g
a
c
h
e
f
g
M U ・
Mfn
M U ・
Mfn
M U
・ Mfn
M U
・ Mfn ・
M U
Mfn ・
M U
・ Mfn ・
M U
・ Mfn ・
・
a 21
MF 木
g 1
・
d 1
・
f 1
81
木 T と MF 木との関連
M U ・
Mfn ・
点 d に戻った時点
d
b
d
a
g
a
c
h
e
f
g
M U ・
Mfn
M U ・
Mfn
M U
・ Mfn
M U
・ Mfn ・
M U
Mfn ・
M U
・ Mfn ・
M U
・ Mfn ・
・
da 32
MF 木
g 1
・
d 1
・
f 1
82
木 T と MF 木との関連
M U ・
Mfn ・
点 d に戻った時点
d
b
d
a
g
a
c
h
e
f
g
M U ・
Mfn
M U ・
Mfn
M U
・ Mfn
M U
・ Mfn ・
M U
Mfn ・
M U
・ Mfn ・
M U
・ Mfn ・
・
da 31
MF 木
g 1
・
d 1
・
f 1
83
木 T と MF 木との関連
M U ・
Mfn ・
点 d に戻った時点
d
b
d
a
g
a
c
h
e
f
g
M U ・
Mfn
M U ・
Mfn
M U
・ Mfn
M U
・ Mfn ・
M U
Mfn ・
M U
・ Mfn ・
M U
・ Mfn ・
・
da 31
MF 木
g 1
・
d 1
・
f 1
84
木 T と MF 木との関連
M U ・
Mfn ・
点 h を深さ優先探索
d
b
d
a
g
a
c
h
e
f
g
M U ・
Mfn
M U ・
Mfn
M U
・ Mfn
M U
・ Mfn ・
M U
Mfn ・
h
M U
・ Mfn ・
M U
・ Mfn ・
・
d 3
MF 木
g 1
・
h 1
・
f 1
85
木 T と MF 木との関連
M U ・
Mfn ・
点 d に戻った時点
d
b
d
a
g
a
c
h
e
f
g
M U ・
Mfn
M U ・
Mfn
M U
・ Mfn
M U
・ Mfn ・
M U
Mfn ・
h
M U
・ Mfn ・
M U
・ Mfn ・
・
d 43
MF 木
g 1
・
h 1
・
f 1
86
木 T と MF 木との関連
M U ・
Mfn ・
点 d に戻った時点
d
b
d
a
g
a
c
h
e
f
g
M U ・
Mfn
M U ・
Mfn
M U
・ Mfn
M U
・ Mfn ・
M U
Mfn ・
h
M U
・ Mfn ・
M U
・ Mfn ・
・
d 4
MF 木
g 1
・
f 1
87
まとめ
 オフライン最下位共通先祖問題を例に，
MF 木と均し計算量の説明をした．
 また，アルゴリズムの解析と実現についても
触れた．
 アルゴリズムが与えられたとき，ここで述べ
たような手順でデータ構造を構築できれば，
単位を修得！！

Download Report