5章再帰呼出しと分割統治

5章再帰呼出しと分割統治
杉原厚吉．（２００１）.「データ構造とアルゴリズム」.
東京：共立出版.
2011/06/21-24
情報知能学科「アルゴリズムとデータ構造」
担当：白井英俊
1
5.1 再帰呼び出し
• 複雑な問題を分割して解くことの代表的なものが
再帰 ― 小問題が大問題の類似形の場合に有
効
• 再帰呼び出し（recursive call) ― 手続き（関数）の
中で自分自身（その関数）を呼び出すこと
• 特長：ある種の手続きを簡潔に表現できる
特に、問題自身が再帰的な場合に有効
木構造、配列、グラフ構造など、構造が「再帰的」になっているとき
など
ただし、どんな問題でも再帰がよい、というわけではない
2
再帰的な構造、効率の悪い問題
• Hanoiの塔：再帰的な構造をしていて、計算量が
大きな問題の典型例
(右図はWikipediaより拝借）
問題：ｎ枚の円盤を3本あるうちの一つの柱から別
な柱に移す手順を求める
入力：円盤の枚数、柱の名称(a,b,c)
出力：円盤を移す手順
3
プログラム Hanoi
def hanoi(n,a,b,c) # n枚の円盤をaからcへ移す
if (n==1) # 円盤が一枚ならば
print ’move the disk from ’,a,’ to ’,c,”\n”
else
hanoi(n－1,a,c,b) # n－1枚の円盤をaからbに移す
print ’move the disk from ’,a,’ to ’,c,”\n”
hanoi(n－1,b,a,c) # n－1枚の円盤をbからcに移す
end # if
end # def
4
ハノイの塔の計算量
• 円盤をn枚移すのにかかる計算量を f(n)
とすると、このアルゴリズムは
f(n) = 2*f(n-1)+α
という計算量が必要である。(円盤を1枚移す手間を定数「 α 」として
いる）
したがって、f(n) は
O(2n)
g(n)=f(n)＋α とおくと
g(n) = 2*g(n-1) となるので
g(n)は２の等比数列
これはアルゴリズムのせいではなく、問題自体が難しい
（指数オーダーの計算量を必要とする）から
＝＞アルゴリズムが簡潔に書けるからといって、そのアル
ゴリズムの効率がよいということにはならない
5
ハノイの塔の計算量
円盤をn枚移すのにかかる計算量を f(n)
とすると、 f(n) は O(2n)
検証: （1枚移す計算量を1とする）
O(2n)
1枚移す:
2枚移す:
3枚移す:
….
n枚移す:
f(1) = 1
f(2) = 2*f(1)+1 = 3
f(3) = 2*f(2)+1 = 7
= 21 -1
= 22 -1
= 23 -1
f(n) = 2*f(n-1)+1
= 2n -1
6
5.2 分割統治法
• 再帰呼び出しによる効率のよいアルゴリズムの例：
マージソート(merge sort)
• 入力： n = 2k (kは正整数）個の数の集合S（配列とす
る）
• 出力： Sの要素を昇順に並べたもの（配列とする）
Sの最小要素
Sの最大要素
• 手続き：
|S|=2ならば、[min(S),max(S)]を返す
さもなくば、Sをn/2個ずつに分け、それぞれをマー
ジソート(mergeSort)する。この二つの結果を、昇順
に並べ(merge）、それを返す。
7
マージソートの実現(0)
アルゴリズムから、mergeSortの全体像は：
def mergeSort(s)
n = s.size
if (n == 2)
# |S|=2の場合の手続きを書く---（１）
else
# それ以外の場合の手続きを書く---(2)
end # if
end # def
8
マージソートの実現(1)
(1) |S|=2のときに[min(S),max(S)]を返す
これは簡単。条件文の使い方さえ分かっていれば…
def mergeSort(s)
n = s.size
return s if n==1 # 一般性を考慮
if (n == 2)
# s[0]とs[1]を比較して、
# [小さい方の要素、大きい方の要素] を返す
else
# 次で考える
end # if
end # def
9
マージソートの実現のために
アルゴリズムを実現するには、以下の作業をするための「アル
ゴリズム」が必要：
2個の要素を持つ配列
(1) |S|=2のときに[min(S),max(S)]を返す
(2) Sをn/2個ずつに分け、それぞれをマージ
ソート(mergeSort)し、二つのマージソートが
返した結果を合わせて、昇順に並べる
(mergeする）
マージソートの実現(２)
def mergeSort(s)
n = s.size
return s if n==1 # 一般性を考慮
if (s.size == 2)
# できているはず…
else
mid = (n－1)/2 # 真中の要素の番号
x = mergeSort(s[0 .. mid])
y = mergeSort(s[(mid+1) .. (n－1)])
return merge(x,y) # xとyを合わせて昇順に
end # if
end # def
注：Rubyでは、配列xのインデックスi番目の要素から
インデックスj番目の要素までを x[i..j]
により配列として取り出せる
11
mergeSortの動き(1)
0
1
2
3
4
5
6
7
mergeSort([20, 10, 5, 15, 3, 7, 13, 18])
def mergeSort(s)
n = s.size
mid = (n－1)/2
x = mergeSort(s[0 .. mid])
y = mergeSort(s[(mid+1) .. (n－1)])
return merge(x,y)
8
3
mergeSortの動き(2)
0
1
2
3
mergeSort([20, 10, 5, 15])
def mergeSort(s)
n = s.size
4
mid = (n－1)/2
x = mergeSort(s[0 .. mid])
y = mergeSort(s[(mid+1) .. (n－1)])
return merge(x,y)
1
mergeSortの動き(3)
0
1
mergeSort([20, 10])
def mergeSort(s)
n = s.size
if (s.size == 2)
2
true
# [最小の要素、最大の要素]を返す
return
else
…
end
[10, 20]
mergeSortの動き(4)
0
1
mergeSort([ 5, 15])
def mergeSort(s)
n = s.size
if (s.size == 2)
2
true
# [最小の要素、最大の要素]を返す
return
else
…
end
[ 5, 15]
mergeSortの動き(2続）
0
1
2
3
mergeSort([20, 10, 5, 15])
def mergeSort(s)
n = s.size
mid = (n－1)/2
[10, 20]
[5,15]
y = mergeSort(s[(mid+1) .. (n－1)])
x = mergeSort(s[0 .. mid])
return merge(x, y)
マージ(merge)とは？
・「再帰法」は、今作ろうとしている手続き
(mergeSort)が小さな問題に対しては「ちゃん
と正しい値を返してくれる」と考えて作る方法。
だから、以下は「ソートされた数の配列が返さ
れると仮定してよい」：
mergeSort(s[0..mid]) # 配列sの前半
mergeSort(s[(mid+1)..(n-1)]) # 配列sの後半
とすると、考えなければならない問題は、返した結果を合わ
せて、昇順に並べる方法
17
マージ(merge)
• 再帰法の仮定から
mergeSort(s[0..mid])
mergeSort(s[(mid+1)..(n－1)])
は、それぞれソートされた配列を返す。ここで
x= mergeSort(s[0..mid])
[1,3,5,9,11,15,18,20]
y= mergeSort(s[(mid+1)..(n－1)]) [2,4,6,8,10,12,14,16]
とすると、
マージmerge(x, y) は、x,yを入力として、
[1,2,3,4,5,6,8,9,10,11,12,14,15,16,18,20]
というような昇順の配列を返す!
18
マージ(merge)関数を作る
def merge(x,y)
result = [ ]
# マージした結果の記録用
xlen = x.size ‐1; ylen = y.size ‐1
# ｘとｙの最後の要素のインデックス
xc = 0; yc = 0 # xとyそれぞれ「比較する」要素の番号
while (xc <= xlen && yc <= ylen ) # 未検査要素あり
# x[xc]とy[yc]を比較し小さい方をresultに入れるなど
# 適切なプログラムを書く
end # while
# xかyに未検査のものがある場合の処理を書く
end # def
19
mergeの動き(1)
merge ( [10, 20] , [5, 15] )
xlen
ylen
0
1 2
5 15
y
ylen = y.size ‐1
def merge(x, y)
0
1
result = [ ]
10 20
x
xlen = x.size ‐1;
xc = 0; yc = 0
(xc <= xlen && yc <= ylen )
xwhile
の残りの要素をすべ
yc
xc 比較(小さい方をresultへ)
# x[xc]とy[yc]を比較しresultに入れる
てresultに入れる
# 適切なプログラムを書く
]
result end #[ while
>
<
mergeSortの動き(２）
0
1
2
3
mergeSort([20, 10, 5, 15])
def mergeSort(s)
n = s.size
mid = (n－1)/2
[10, 20]
[5,15]
y = mergeSort(s[(mid+1) .. (n－1)])
x = mergeSort(s[0 .. mid])
return merge(x, y)
[5, 10, 15, 20]
mergeの動き(2)
merge ([ 3,
7]
,
[13, 18]
)
xlen
ylen
0
x
２
1
3 7
0
1
y
13 18
y の残りの要素をす
xc 比較(小さい方をresultへ)
べてresultに入れる
yc
<
result
[
]
mergeSortの動き(1続)
0
1
2
3
4
5
6
7
mergeSort([20, 10, 5, 15, 3, 7, 13, 18])
def mergeSort(s)
n = s.size
mid = (n－1)/2
x = mergeSort(s[0 .. mid])
y = mergeSort(s[(mid+1) .. (n－1)])
return merge(x,y)
8
3
[5,10,15,20]
[3,7,13,18]
mergeの動き(3)
xlen
0
1
2
3
ylen
0
1
2
3
5 10
20 , [ 3,
3 7
13 18]
18 )
10, 15
15, 20]
7, 13,
merge ( [ 5,
yc
xc
比較(小さい方をresultへ)
<
>
result
4
[
xの残りの要素をすべ
てresultに入れる
]
マージソートの完成
• mergeとmergeSortをちゃんと書くことができれ
ば、次のような結果が得られるだろう：
(mergeSortTemplate.rb参照)ーーー課題
mergeSort([20, 10, 5, 15, 3, 7, 13, 18, 2, 6, 4, 1,
19])
の出力結果：
[1, 2, 3, 4, 5, 6, 7, 10, 13, 15, 18, 19, 20]
25
分割統治法
• 入力データの大きさをnとすると、そのデータ
を大きさ n/b の問題
a
個に分割し、それぞれ
マージソートの計算
を再帰的に解いた結果を利用して、元の問題
量はO(n*log n)
の解を作るという方法(教科書、p.51)で、かつ
計算時間 f(n) が
n=1の時、 f(n) = c (ｃは定数）
n ≧2の時、 f(n)=a*f(n/b) + cn （a,b,cは定数）
となるもの(マージソートでは a=b=2)
26
ハノイの塔とマージソートの比較
ハノイの塔: hanoi(n,a,b,c)
if (n == 1)
1枚円盤をaからcに移動
else
hanoi(n-1,a,c,b)
1枚円盤をaからcに移動
hanoi(n-1,b,a,c)
end
計算量
O(2n)
O(n*log n)
マージソート:mergeSort(s)
if (s.size == 1)
return s
elsif (s.size == 2)
return [s.min, s.max]
else
x=mergeSort(sの前半分)
y=mergeSort(sの後半分)
return merge(x,y)
end
27
ハノイの塔とマージソートの比較
• ハノイの塔は再帰法を使っていても、その計
算量は O(2n)
• マージソートでは、O(n*log n)
この違いは何か？
半分！
答え：
元の問題に対し、一定の比で小さな問題に
して解く（マージソート）か、一定の差で小さな
問題にして解く（ハノイの塔）か。(p.53-54)
28
再帰呼出しを使わない方がよい例
• フィボナッチ数列(Fibonacci sequence)
定義：非負整数nに対するフィボナッチ数F(n)
とは
n=0 または n=1 のとき、１
それ以外： F(n) = F(n-1)+F(n-2)
１１２３５８１３２１３４５５８９１４４ …
この形から、「ハノイの塔」タイプであることが明らか
29
フィボナッチ数F(n)を求める
• 先の定義を単純にプログラムすると以下のとおり：
def fibo1(n)
if (n==0 || n==1)
return 1
else
return fibo1(n-1)+fibo1(n-2)
end # if
end #def
これを用いて fibo1(30)や
fibo1(50)を計算させてみよう
30
フィボナッチ数F(n)の別な求め方
• 実は再帰を使わず、F(1），F(2),F(3),…
の順にF(n)まで計算すれば、ずっと効率がよい
…計算量のオーダーはO(n)
def fibo2(n)
return 1 if (n==0 || n==1)
x = 1; y = 1
for i in 2..n
z = x+y ; x = y; y = z
end # for
return z
これを用いて
end # def
fibo2(30)や
fibo2(50)を計算させてみよう
31
実は。。。
• 教科書p.56にあるように、フィボナッチ数F(n)
はO(log n)で求めることができる。
n
1 1 

A(n)  
1 0   FF(n(n)1)   A(n 1) FF((10))   A(n 1)11
とすると
ここで
 F (n) 
 F (1) 
1

  A(n  1)
  A(n  1) 
 F (n  1) 
 F (0) 
1
1 1 1 1   2 1 


  

1 0 1 0   1 0 
 2 1  2 1   5 3 


  

 1 0  1 0   3 2 
これを用いて F(10)やF (30)を計算しよう
32
まとめ：ハノイの塔の問題とフィボナッチ
数の問題の違い
• ハノイの塔の問題で求めなければならないのは、「
実際に円盤を移すこと」。円盤を移す回数が計算量
となる。これは再帰を使わなくても同じ値になる。
指示手順を求めるという場合、具体的に「どの円盤
をどこに移すか」という指示一つ一つが、「円盤を移
すこと」と同じなので、指示の個数＝円盤を移す個数
、となる。だからいずれにせよ 2nに比例した計算量
• フィボナッチ数(関数F)を求める問題では、nが与えら
れた時にF(n)の値が求められればよい。これは定義
通りに再帰を使わずに、 O(log n)という効率的な求め
方がある。
33

Download Report