コンピュータソフトウェア

コンピュータアルゴリズム2
4. 分割統治法
田浦
http://www.logos.ic.i.u-tokyo.ac.jp
/~tau/lecture/software/
内容



分割統治法(divide-and-conquer)の考え方
 再帰呼び出しを有効利用したアルゴリズムの簡潔な記述
適用例
 クイックソート，マージソート，FFT, 行列積，etc
 その他の再帰呼び出し利用例
再帰呼び出しを含むプログラムの計算量
 漸化式
 分割統治の計算量の一般論
分割統治法のテンプレート

solve(X) {
if (trivial(X)) {
trivial_solve(X);
} else {
X1, X2, ..., Xp = divide(X);
A1 = solve(X1);
A2 = solve(X2);
...
Ap = solve(Xp);
return combine(A1, A2, ..., Ap);
}
}
X
X1
X2
X3
X4
分割統治法のマスター  再帰呼び出しの有効利用法のマスター
再帰呼び出しのマスターが重要な
理由


プログラムの「記述法」として
 さもなければ非常にややこしくなるプログラムの記述が非
常に簡潔になる
解法の「発想法」として
 「あたかも，より小さな問題の解はわかっている」と仮定し
て，解答を書けばいい
 数学での類似物：漸化式による解法
 最初から closed form での解を求めるのが難しい問題
を，いったん漸化式を書いてそれを解く，という方法
(用語の注)
再帰呼び出し=分割統治?

NO: ニュアンスとしては，「分割統治法」は，再帰呼び出しを
する際に問題のサイズが当初の問題より十分(定数倍)小さく
なっている場合をいうようである
 たとえば普通以下を「分割統治」とは呼ばない
 int fib(n) { if (n < 2) return 1; else fib(n – 1) + fib(n – 2); }

しかしそうであろうとなかろうと，「再帰呼び出し」が「記述法・
発想法として有効」なことには違いない
再帰呼び出しの練習(1)

例題： n (整数)が与えられた際に，可能なすべての n 個の{0,
1}列(2n個ある)を列挙せよ
 0000...00
 0000...01
 0000...10
 ...
 1111...11
再帰呼び出しの練習(2)

n要素の整数の配列(a[0], ..., a[n–1])と目標値Tが与えられる．
n個から値を選び出してその和がTとなるようにできるか?
 例: a = { 2, 4, 3, 9 }, T = 5 解: 2 + 3 = 5
 例: a = { 2, 4, 3, 9 }, T = 8 解: なし
再帰呼び出しの練習(3)

例題： n 円盤のハノイの塔を解く(手順を表示する)プログラ
ムを書け
move 1 a  b
move 2 a  c
move 1 b  c
move 3 a  b
move 1 c  a
move 2 c  b
move 1 a  b
1
2
3
a
b
c
再帰呼び出しの練習(4)

1...nまでのすべての並び替えを列挙せよ
 123
 132
 213
 231
 312
 321

注：これらはどれも n に対して指数関数の計算時間を要する
アルゴリズムで，通常「分割統治法」とは呼ばない
「分割統治法」の例(1)
行列積
A00
A01
A
A10
A11

B00
B01
B
B10
C00
C
=
B11
A00  B00 +
A01  B10 =
C00
A00  B01 +
A01  B11 =
C01
A10  B00 +
A11  B10 =
C10
A10  B01 +
A11  B11 =
C11
C01
C10
C11
1辺 N の問題
 1辺N / 2の問題  8
「分割統治法」の例(2)
FFT (高速フーリエ変換)

フーリエ変換(連続関数)
1
g ( y) 
2




f ( x)e ixydx
離散フーリエ変換(サンプル数N)
  は1のN乗根の逆数 = e– i (2  / N)
N 1
g[k ]   f [ j ]
j 0
jk
N
(k = 0, 1, ..., N – 1)
FFTはこの計算を高速に行う方法
離散フーリエ変換の行列表示
N 1
g k   f j
j 0
jk
N
1
1
 g 0  1

 
1
2

 g1  1 
4
 g   1  2

2

 


   
g  
N 1
( N 1) 2

 N 1  1 







N 1


2 ( N 1) 




( N 1)( N 1) 


1
f0 

f1 
f2 

 

f N 1 


通常の方法では明らかに N2 回の掛け算が必要
どのように「分割統治」(小さな問題へ分割)できるか
 簡単のため N は偶数(後でわかるように2のべき)とする
N = 8の場合の行列
1
1 = 1
1
1
1 1

1
2
3
4
5
6
=
–




1  
1  2  4  6 =  8  10  12

3
6
9 = – 12
15
18
 


1  
1  4  8  12  16  20  24
=

1  5  10  15 = –  20  25  30

6
12
18
24
30
36
 =


1  
1  7  14  21= –  28  35  42

1 

7
 
14 


21
 
28 
 
35
 
42 
 
49 
 
偶数行(0, 2, 4, 6)の計算方法
+
しかもこの計算が良く見るとN/2 点 FFTそのもの
奇数行(1, 3, 5, 7)の計算方法
–
残念ながらここはFFTそのものではなく一工夫必要
奇数行の工夫
1

1
1

1

1
1  f 0 
 1  2  3  f 0  1 1







2
4
6
   f1 
 3  6  9  f1  1  

4
8
12  2
5
10
15 

 
  f 2  1      f 2 
6
12
18  3



7
14
21 
f

f
 
 
  3  1  
3
N / 2点FFT
N 1
g 2 k   f j
j 0
2 jk
N
導出(偶数行)
N 1
  f j
j 0

N / 2 1
f
j 0

j
jk
N /2
N / 2 1
f
j 0

jk
N /2
j
N / 2 1
( f
j 0
j
jk
N /2

N 1
f
jN / 2

j
N / 2 1
f
j 0
 f j  N / 2 )
jk
N /2

jN / 2
jk
N /2
jk
N /2
N 1
g 2 k 1   f j
j 0
2 jk  j
N
N 1
  f j
j 0

N / 2 1
f
j 0

j
N / 2 1
f
j 0


jk
N /2
j
N / 2 1
( f
j 0
j
導出(奇数行)
j
N
 
jk
N /2
j
N
 
jk
N /2
j
N
N 1
f
jN / 2
j
N / 2 1
f
j 0
 f j  N / 2 ) 
j
N

jk
N /2

jN / 2
jk
N /2
j
N
jk
N /2
( )
j
N
FFTの計算量は?


O(N log N)
ただし分割統治が続けられるよう, N が2のべきである必要が
ある
分割統治法の計算量に関する一般
論
問題設定(1)


以下のような分割統治法を考える
solve (X) {
if (size(X) = 1) return trivial_solve(X);
else {
X1, X2, ..., Xp = divide(X);
A1 = solve(X1);
...
Ap = solve(Xp);
return merge(A1, ..., Ap);
}
}
問題設定(2)

以下を仮定する．Xiの大きさを inとするとき，
 分割と解の併合(divideとmerge)にかかる計算量はあわせ
てO(nk)
 定数 c < 1 が存在し，各 i  c
 定数 d が存在し， 1k + 2k + ... + pk  d
 大きさ 1のデータに対する(trivial_solve(X)の)計算量は
高々定数(1とする)
定理

このとき大きさnのデータに対するこのアルゴリズムの計算量
T(n)は
 O(n )
d  1 のとき

k
T (n)   O(n log n) d  1 のとき
O(n k  log1 / c d ) d  1 のとき

k
いくつかの例


マージソート
 n が n/2 二つに分かれる
 分割・併合は O(n)
  k = 1, c = 1/2, d = 1  O(n log n)
クイックソート
 ただし，定理中の定数 c < 1 の存在を仮定する(実際には
成り立たない)
 分割・併合は O(n)
  k = 1, d = 1  O(n log n)
行列積



n が n/2 八つに分かれる
分割・併合は O(n2)
k = 2, c = 1/2, d = (1/2)2  8 = 2  O(n2 + log2) = O(n3)
アルゴリズム体操
チャレンジ問題：授業期間を通じて「できた」という人の報告を待つ
アルゴリズム体操(1)

2  2 行列の積は通常 8つの掛け算が必要である
a00
a10


a01
a11

b00
b01
c00
c01
c10
c11
=
b10
b11
[難] これを7つの掛け算(その代わり足し算引き算の数は増え
る)で行う方法がある．それを考えよ
それが見つかるとn  nの行列の掛け算をO(n2.81)で行う方法
が導かれる(nは2の冪としてよい)
アルゴリズム体操(2)

n個の要素からなる配列がある．これらの中でn/2個より多く
現れている要素があればそれを見つけ，そのような要素が
なければないと答えるアルゴリズムを作りたい
 [易] 計算量 O(n log n)のアルゴリズムを考えよ
 [難] 計算量 O(n)のアルゴリズムを考えよ
 hint: 分割統治法でk = 1, d < 1となるようなものを見出
せ
アルゴリズム体操(3)



時間計算量O(n log n)が保証されたクイックソートアルゴリズ
ムは，以下の意味で「安全な」pivot pをO(n)で見つけることが
できれば実現可能である(※)
 ある定数c < 1 が存在し
 a[i]  pであるiの個数  c n
 a[i]  pであるiの個数  c n
[易] (※) を証明せよ
[難] そのようなアルゴリズムFを見つけよ
 hint: 分割統治法でk = 1, d < 1であるようなものを見出せ
アルゴリズム体操(4)

n個の相異なる数からなる配列がある．中央値(nの偶奇に応
じn/2番目または (n+1)/2番目の値)を見つけたい
 [易] O(n log n)のアルゴリズムを見つけよ
 [難] O(n)のアルゴリズムを見つけよ
 hint : 前問で求めたアルゴリズムFを用いる．そして，こ
れを利用して分割統治法を使う(k = 1, d < 1)

Download Report