Document

最適２分探索木
図書の検索と図書の格納
遠くの場所
近くの場所
貸出頻度
が高い本
貸出頻度
が低い本
A
B
書庫
書庫に無い本 C
J
データの検索とデータの格納
根から遠い場所
根に近い場所
検索頻度が
高いデータ
検索頻度が
低いデータ
A
B
格納されている
データ
格納されていない
C
データ
J
図書の検索と図書の格納
J
データ
データ
根
今までの話では・・・
J
データ問合せの頻度（確率）は同じ
データ問合せの頻度（確率）は同じ
最適２分探索木とは？
• 格納されているデータ集合の中に、探索キーと同じ
キーを持つデータがあるか否かをチェックする
データ
2
5
7
10
12
• 探索キーが現れる確率が与えられる
確率(1/20)
1
3
20
2
20
1
2
20
2
1
3
2
1
７
1
20
データ
確率(1/20)
2
５
２
1
20
3
2
1
20
5
1
2
3
2
2
7
1
2
20
2
１２
１０
3
20
1
2
20
1
20
10
12
3 2 2 1 2
2
20
最適２分探索木とは？
• 探索キーの現れる確率が与えられる
データ
2
5
7
10
12
探索木をどう作れば平均
1 3 2 1 2 1 3 2 2 1 2
探索時間が短かくなるか
• 平均比較回数が最小となる２分探索木を作る
確率(1/20)
７
５
２
５
１０
１０
２
１２
７
１２
２分探索木の平均コストの計算方法
J
0
データ
1
2
取りに行く
頻度（確率）
3
取りに行く
手間（コスト）
データ
根
２分探索木の平均コストの計算方法
1×1/20
確率：1/20
比較：1
0
1
2
3
2×1/20
確率：1/20
比較：2
3×3/20
確率：3/20
比較：3
3×3/20
確率：3/20
比較：3
２
５
７
１０
内点：比較回数＝深さ＋１
外点：比較回数＝深さ
１２
２分探索木のコストの比較（その１）
平均比較回数＝55/20
1/20
1/20
0
2/20
1/20
1
2
9/20
3/20
５
７
１０
２
１２
2/20
4/20
3
1/20 3/20
3/20 9/20
4/20
2/20
3/20
1/20
3/20
6/20
2/20 2/20
6/20 6/20
２分探索木のコストの比較（その２）
平均比較回数＝53/20
1/20
2/20
0
1
探索木の作り方次第で
6/20
平均探索時間が変化する
3/20
１０
２
3/20
1/20
2
3
５
4/20
2/20
3/20
1/20
７
１２
2/20 3/20
6/20 9/20
2/20 2/20
6/20 6/20
1/20 3/20
2/20 6/20
記号pi，qj ，c(T) の説明
• 探索キーの現れる確率が与えられる
データ
確率(1/20)
2
1
3
5
1
2
2
7
1
10
12
3 2 2 1 2
• 与えられる確率の一般的表記
データ
a1
a2
p2
確率(1/全体) q0 p1 q1
確率×比較回数
c(T ) 
・・・
・・・
an-1
an
pn-1 qn-1 pn qn
内点
n
p
i 1
i
外点
n
 (depth(vi )  1)   qi  depth(ui )
i 0
2分探索木Tのコストc(T) の計算方法
確率×比較回数
c(T ) 
内点
n
p
i 1
i
外点
n
 (depth(vi )  1)   qi  depth(ui )
i 0
方針
• 目的：最適2分探索木を作りたい
• （天下り的だが）そのためにcijを計算したい
– cijを説明するためをTij等を説明する
• 動的計画法によりcijを計算する
– そのためにはcijに関する再帰式が必要
• そのためにTijを（根の値で）分類する
方針
• 目的：最適2分探索木を作りたい
• （天下り的だが）そのためにcijを計算したい
– cijを説明するためをTij等を説明する
• 動的計画法によりcijを計算する
– そのためにはcijに関する再帰式が必要
• そのためにTijを（根の値で）分類する
（全体ではなく部分を表す）Tij の説明
Ti , j : データ ai 1から a jで
a1
a2
a3
a4
q0 p1 q1 p2 q2 p3 q3 p4 q4
T14
Ti,j : Ti,j 全体からなる集合
T1,4
a2
a2
p2
q1
q1
p2
a3
a3
q2
p3
q3
q2
q4
a4
p4
a４
a2
p4
p2
a3
q4
p3
a４
p4
構成されるある部分木
q3
p3
a2
q1
p2
q2
q1
a４
q3
p4
q4
q4
a3
a3
p3
q2
a４
a2
q3
q1
p2
p3
q2
p4
q4
q3
（全体ではなく部分を表す）Tij の説明
Tki,j ： Ti,jで根がakのある木
a1
a2
a3
a4
q0 p1 q1 p2 q2 p3 q3 p4 q4 T ki,j : Tki,j全体からなる集合
T1,4
T
2
1,4
q1
q1
p2
a４
a3
p3
a４
q3
p4
∪T
i+2
i,j
∪・・・∪ T
T1,4
a3
q2
i+1
i,j
i,j = T
a2
a2
p2
T
p4
q4
q3
p3
a2
p2
q1
p2
q2
q1
a４
q3
p4
a3
a3
q3
q1
a2
p2
4
1,4
a４
q4
p3
q2
q4
T
p4
a2
3
1,4
a3
q4
p3
q2
T
a4
j
i,j
p3
q2
p4
q4
q3
方針
• 目的：最適2分探索木を作りたい
• （天下り的だが）そのためにcijを計算したい
– cijを説明するためをTij等を説明する
• 動的計画法によりcijを計算する
– そのためにはcijに関する再帰式が必要
• そのためにTijを（根の値で）分類する
（ Ti,jの最適コスト）ci,j の説明
a1
a2
a3
a4
q0 p1 q1 p2 q2 p3 q3 p4 q4
ci,j = min c(Ti,j)
Ti,j ∈Ti,,j
Cijを計算したい。
しらみ潰し的に
調べるしかない？
T1,4
c(Ti,j)で最小の値
（それはp*, q*のみで決まる）
a2
a2
p2
q1
q1
p2
a3
a3
q2
p3
q3
p4
a2
p4
p2
p3
a４
q2
q4
p4
a４
a3
q4
q3
p3
a2
q1
p2
q2
q1
a４
q3
p4
a４
q4
a3
a3
p3
q2
q4
a4
a2
q3
q1
p2
p3
q2
p4
q4
q3
（ T=T0,nの最適コスト）c0,n とは?
a1
a2
a3
a4
q0 p1 q1 p2 q2 p3 q3 p4 q4
つまりc(T)
T0,4
c(T0,n)で最小の値
a１
（それはp*, q*のみで決まる）
P１ a
2
q0
p2
・・・
a3
q1
p3
q2 a４
p4
q3 q4
a４
a3
p3
a1
p1
q1
a2
q3
・・・
a４
q3
p2
q2
a3
p4
q4
a2
a2
p2
P1
q0 q1
p3
q2
p4
q4
q3
方針
• 目的：最適2分探索木を作りたい
• （天下り的だが）そのためにcijを計算したい
– cijを説明するためをTij等を説明する
• 動的計画法によりcijを計算する
– そのためにはcijに関する再帰式が必要
• そのためにTijを（根の値で）分類する
根にキーakがあるときのコスト
ak


p
i 1
n
i 0
n
  pi  depth(vi )
i
  qi
 depth(Tの左右部分木, vi )
k 1
n
c(T )
depth(T , vi )  1
k 1
i 0
n


  pi   qi   c(T0,k 1 )  c(Tk ,n )
i 0
 i 1

確率×比較回数
c(Ts ,t ) 
p

i 1
  qi  (depth(ui )  1)
n
i  k 1
p
i  s 1
i
 depth(vi )
n
  qi  (depth(ui )  1)
i k
内点
t
i
外点
t
 (depth(vi )  1)   qi  depth(ui )
is
根にキーakがあるときのc(T) に関する再帰式
a2
p2
depth 0
depth 1
a1
depth 2
p1
a3
p3
q1
q0
depth 3
q2
a4
a1
p4
p1
q4
q3
q0
a2
p2
a4
T01
c(T )


p
i 1
n
i
  qi
i 0
n
q4
p3
q2
depth 1
depth 2
q3
T04
n
p4
a3
q1
depth 0
T24
k 1
  pi  depth(vi )
k 1
i 0

i 1
  qi  (depth(ui )  1)
n


  pi   qi   c(T0,k 1 )  c(Tk ,n )
i 0
 i 1

n
p
i  k 1
n
i
 depth(vi )
  qi  (depth(ui )  1)
i k
方針
• 目的：最適2分探索木を作りたい
• （天下り的だが）そのためにcijを計算したい
– cijを説明するためをTij等を説明する
• 動的計画法によりcijを計算する
– そのためにはcijに関する再帰式が必要
• そのためにTijを（根の値で）分類する
根がakのc(T) に関する再帰式の考察
これを小さくしたい
c(Ti ,kj )


j
 j

  ps   qs   c(Ti , k 1 )  c(Tk , j )
s i
 s i 1

これらを小さくすればよい
wi , j  c(Ti , k 1 )  c(Tk , j )
赤線部が最小になるようなTi,k-1 とTk,jを選ぶと、
つまりｃ(Ti,k-1)= ci,k-1, ｃ(Tk,j)= ck,jを満たすものを
選ぶとｃ(T ki,j)を最小にできる
T
k )=w +ｃ
min
ｃ
(T
i,j
i,j
i,k-1 + ｃk,j
k
k
i,j ∈T
i,j
つまり、これを考えればよい
ci,j を求めるための再帰式
T
k )=w +ｃ
min
ｃ
(T
+
ｃ
i,j
i,j
i,k-1
k,j
k
k
T
i,j = T
i,j ∈T
i,j
i+1
i,j
∪T
i+2
i,j
∪・・・∪ T
j
i,j
ｃi,j = min ｃ(T i,j)
T i,j ∈T
i,j
{
= min{w
= min
}
,・・・, w +ｃ +ｃ }
,・・・, ｃ +ｃ
}
min ｃ(T i+1i,j) ,・・・, min ｃ(T ji,j)
T i+1i,j ∈T
i+1
i,j
i,j +ｃi,i+ｃi+1,j
{
= wi,j+ min ｃi,i+ｃi+1,j
= wi,j+ min { ｃi,k-1+ｃk,j }
i<k≦j
T ji,j ∈T
j
i,j
i,j
i,j-1
i,j-1
j,j
j,j
動的計画法の例
• 動的計画法のイメージ
• 動的計画法の計算過程
動的計画法のイメージ
3
5
38
1
1
18
21
2
2
0
4
2
1
1
2
1
3
2
2
0
4
C02
9
0
4
C00
1
3
C11
1
6 2
10 3
8 4
2
1
5
2
0 1
4 3
C01
1 2
3 2
C12
2 3
2 3
C23
3 4
3 3
C34
2
2
C22
3
3
C33
4
3
C44
・・・
2
2
2
1
3
C02
3
3
2
0
4
2
1
1 2
3 2
C03
小さい部品から
大きい部品を作る
・・・
動的計画法の計算過程
ci , j  wi , j  min ci ,k 1  ck , j 
i k  j
c0,1  w0,1  min c0, 0  c1,1
0 k 1
4+2+3=9
9
cij c000 c01
を
C先ずC
iiから
00とC11
C0にセット
01を計算
c011
00
0 0
4
C00
1
2
0 1
4 3
C00 C11
0 1
3
C11
c022
00
c033
00
c044
00
動的計画法の計算過程
ci , j  wi , j  min ci ,k 1  ck , j 
i k  j
cij c00 c01
c11
00 c12
c1, 2  w1, 2  min c1,1  c2, 2 
1 k  2
c22
00 c23
c2,3  w2,3  min c2, 2  c3,3 
2 k 3
c33
00 c34
c44
00
c3, 4  w3, 4  min c3,3  c4, 4 
3 k  4
動的計画法の計算過程
ci , j  wi , j  min ci ,k 1  ck , j 
minを選ぶ
i k  j
c0, 2  w0, 2  min c0, 0  c1, 2 , c0,1  c2, 2 
0 k  2
9
0
4
C00
cij c00 c01 c02
c11
00 c12
1
2
0 1
4 3
C01
18 1
2
0
2
4
1
C00 1 2
3 2
C12
6 2
1
1 2
3 2
C12
c22
00 c23
c33
00 c34
c44
00
2
2
C22
21 2
１
1
2
0 1
4 3
C01
2
2
C22
動的計画法の計算過程
ci , j  wi , j  min ci ,k 1  ck , j 
i k  j
cij c00 c01 c02
c11
00 c12 c13
c1,3  w1,3  min c1,1  c2,3 , c1, 2  c3,3 
1 k 3
c22
00 c23 c24
c33
00 c34
c44
00
c2, 4  w2, 4  min c2, 2  c3, 4 , c2,3  c4, 4 
2 k  4
動的計画法の計算過程
ci , j  wi , j  min ci ,k 1  ck , j 
kが0<k≦3の
範囲で動く
i k  j
c0,3  w0,3  min c0, 0  c1,3 , c0,1  c2,3 , c0, 2  c3,3 
0 k 3
1
cij c00 c01 c02 c03
c11
00 c12 c13
0 20
4
C00
2
5
2
3
3
1
c22
00 c23 c24
c33
00 c34
c44
00
1
3
9
3
2
2
C13
3
1
10 3
2
5
0 1
4 3
C01
2 3
2 3
C23
18
1
3
3
C33
2
0
4
2
1
1
3
C02
2
2
動的計画法の計算過程
ci , j  wi , j  min ci ,k 1  ck , j 
i k  j
c1, 4  w1, 4  min c1,1  c2, 4 , c1, 2  c3, 4 , c1,3  c4, 4 
1 k  4
cij c00 c01 c02 c03
c11
00 c12 c13 c14
c22
00 c23 c24
c33
00 c34
c44
00
動的計画法の計算過程
ci , j  wi , j  min ci ,k 1  ck , j 
i k  j
c0, 4  w0, 4  min c0, 0  c1, 4 , c0,1  c2, 4 , c0, 2  c3, 4 , c0,3  c4, 4 
0 k  4
cij c00 c01 c02 c03 c04
c11
00 c12 c13 c14
c22
00 c23 c24
c33
00 c34
c44
00
c04
min
c00
c14
c01
c24
c02
c34
c03
c14
w03
w14
min
c00
c13
w02
c01
c23
c02
min
c02
c33
w13
c01
c22
c01
c11
c23
c24
min
c22
c34
c23
c44
c34
c23
w23
c11
c22
c11
c13
c44
w24
c12
c33
w12
c00
c11
c12
c34
c13
c12
w01
c00
c11
c24
min
min
c00
c12
c03
c44
w34
c22
c33
c22
c33
c44
c33
c44
ここからは部品
動的計画法の考え方
1
1
2
3
3
2
2
1
5
5
0 24 2
4
1
C00 1
3
3
5
2 3
2 3
C13
0 20
4
C00
5
2
3
3
1
1
3
9
3
2
2
C13
1
10 3
2
5
0 1
4 3
C01
2 3
2 3
C23
18
1
3
3
C33
2
0
4
2
1
1
1
1
3
C02
2
21
2
2
2
2
2
0
4
1
3
C02
3
3
C33
動的計画法の考え方
1
2
0
1
1
1
3
2
1
4
3
2
4
3
0
4
2
4
3
4
3
0
2
0
1
1
2
3
4
3
4
2
1
4
3
2
動的計画法の説明
確率×比較回数
c(Ts ,t ) 
内点
t
p
i  s 1
i
外点
t
 (depth(vi )  1)   qi  depth(ui )
is
ｋをｓからｔまで動かし
minを取る
aaｔ kｓ
Tｓ,k-1
Tｓ,ｔ-1
Tk,ｔ
Tｓ+１ｔ
最適２分探索木を求めるために
何を考えればよいか？
•
常套手段を使う
1. 求めたいものを記号化し
2. その記号を使って式を組み立て
3. 組み立てた式を解く
根にキーakがあるときのコスト
ak
n
c(T ) 
p
i 1
n
i
q
i 0
n
i
k 1
  pi  depth(vi )
k 1
n

i 1
 p  depth(v )
i  k 1
n
i
i
  qi  (depth(ui )  1)   qi  (depth(ui )  1)
i 0
n
i k


   pi   qi   c(T0,k 1 )  c(Tk ,n )
i 0
 i 1

wi ,i  qi wi , j  qi  pi 1  qi 1    p j  q j
ci ,i  0 ci , j  wi , j  min ci ,k 1 , ck , j 
ik  j
wij w00 w01 w02 w03 w04
cij c00 c00 c00 c00 c00
w11 w12 w13 w14
c00 c00 c00 c00
w22 w23 w24
c00 c00 c00
w33 w34
c00 c00
w44
c00
wi ,i  qi wi , j  qi  pi 1  qi 1    p j  q j
ci ,i  0 ci , j  wi , j  min ci ,k 1 , ck , j 
ik  j
cij c000
wij wq00
0
c011
wq11
1
wq22
2
c022
wq33
3
c033
wq44
4
c044
ci , j  wi , j  min ci ,k 1 , ck , j 
i k  j
c0,1  w0,1  min c0, 0 , c1,1
0 k 1
cij
c01
c1, 2  w1, 2  min c1,1 , c2, 2 
1 k  2
動的計画法での表の更新
wi ,i  qi wi , j  qi  pi 1  qi 1    p j  q j
ci ,i  0 ci , j  wi , j  min ci ,k 1 , ck , j 
ik  j
wij
cij
動的計画法での表の更新
wi ,i  qi wi , j  qi  pi 1  qi 1    p j  q j
ci ,i  0 ci , j  wi , j  min ci ,k 1 , ck , j 
ik  j
wij w00 w01 w02 w03 w04
cij ｃ00 ｃ01 ｃ02 ｃ03 ｃ04
w11 w12 w13 w14
ｃ11 ｃ12 ｃ13 ｃ14
w22 w23 w24
ｃ22 ｃ23 ｃ24
w33 w34
ｃ33 ｃ34
w44
ｃ44
２分探索木のコストの比較（その１）
i=1, j=4
q0
p1
q1
p2
q2
p3
q3
p4
q4
p5
根にキーakがあるときのコスト
確率×比較回数内点
c(T ) 

外点
n
n
 p  (depth(v )  1)   q  depth(u )
i 1
n
i
i
i 0
k 1
i
i
n
 p   p  depth(v )   p  depth(v ) 
i 1
n
i
i
i 1
k 1
i
i  k 1
i
i
n
 q   q  (depth(u )  1)   q  (depth(u )  1)
i 0
n
i
i 0
i
i
i k
n


   pi   qi   c(T0,k 1 )  c(Tk ,n )
i 0
 i 1

i
i
根にキーakがあるときのコスト
動的計画法を
用いて解く
ak akak
qi
c(T )

qj
n
 n

p

q
  i  i   c(T0,k 1 )  c(Tk ,n )
i 0
 i 1

ci ,：確率
qi , pi 1 , qi 1 ,, p j , q jに対する最適２分探索木のコスト
j
wi , j : qi  pi 1  qi 1    p j  q j
ci , j  wi , j  min ci ,k 1  ck , j 
ik  j
動的計画法の概略
a1
ak
an
…
T1,n
…
T0,k-1
Tk,n
Ti,j を作る
T0,n-1
根にキーakがあるときのコスト
ak akak
動的計画法を
用いて解く
qi
qj
Ti , j : データ ai 1から a jで構成される部分木
ci ,：確率
qi , pi 1 , qi 1 , , p j , q jに対する
j
最適２分探索木のコスト
wi , j : qi  pi 1  qi 1    p j  q j
ci , j  wi , j  min ci ,k 1  ck , j 
ik  j
動的計画法の計算過程
ci , j  wi , j  min ci ,k 1  ck , j 
i k  j
c1, 2  w1, 2  min c1,1  c2, 2 
1 k  2
cij c00 c01
c11
00 c12
c22
00
c33
00
c44
00
動的計画法の計算過程
ci , j  wi , j  min ci ,k 1  ck , j 
i k  j
c2,3  w2,3  min c2, 2  c3,3 
2 k 3
cij c00 c01
c11
00 c12
c22
00 c23
c33
00
c44
00
動的計画法の計算過程
ci , j  wi , j  min ci ,k 1  ck , j 
i k  j
c3, 4  w3, 4  min c3,3  c4, 4 
3 k  4
cij c00 c01
c11
00 c12
c22
00 c23
c33
00 c34
c44
00
（全体ではなく部分を表す）Tij の説明
a1
a2
a3
a4
q0 p1 q1 p2 q2 p3 q3 p4 q4
Ti , j : データ ai 1から a jで構成される
a4
a2 T14
p
p2
4
a
a
2
４
q1
q
4
p
p4
2
a3
a
3
a４
a2
q1
q4
p3
p3
p4
p2
a3
a3 q q
q
q
a
3
2
3
q4
3
2
q1
p3
p
p
3
3
a
a
a
a
2
４
2
４
q3
q2
p2
p4
p2
p4
q3 q4 q1 q2 q3 q 4 q1 q2
• ｃ(T ki,j) = wi,j + ｃ(Ti,k-1) + ｃ(T k,j)

Download Report