2011/06/21-24 情報知能学科「アルゴリズムとデータ構造」 担当：白井英俊 5章　再帰呼出しと分割統治 杉原厚吉．（２００１）.「データ構造とアルゴリズム」. 東京：共立出版. 2011/06/21-24 情報知能学科「アルゴリズムとデータ構造」 担当：白井英俊

5.1 再帰呼び出し 複雑な問題を分割して解くことの代表的なものが再帰 ― 小問題が大問題の類似形の場合に有効 5.1　再帰呼び出し 複雑な問題を分割して解くことの代表的なものが再帰 ― 小問題が大問題の類似形の場合に有効 再帰呼び出し（recursive call) ―　手続き（関数）の中で自分自身（その関数）を呼び出すこと 特長：ある種の手続きを簡潔に表現できる 特に、問題自身が再帰的な場合に有効 木構造、配列、グラフ構造など、構造が「再帰的」になっているときなど ただし、どんな問題でも再帰がよい、というわけではない

再帰的な構造、効率の悪い問題 Hanoiの塔：再帰的な構造をしていて、計算量が大きな問題の典型例 (右図はWikipediaより拝借） 問題：ｎ枚の円盤を3本あるうちの一つの柱から別な柱に移す手順を求める 入力：円盤の枚数、柱の名称(a,b,c) 出力：円盤を移す手順

プログラム 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に移す hanoi(n－1,b,a,c) # n－1枚の円盤をbからcに移す 　　end # if end # def

ハノイの塔の計算量 円盤を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)は２の等比数列

ハノイの塔の計算量 円盤をn枚移すのにかかる計算量を f(n) とすると、 f(n) は O(2n) 2枚移す: f(2) = 2*f(1)+1 = 3 = 22 -1 3枚移す: f(3) = 2*f(2)+1 = 7 = 23 -1 …. n枚移す: f(n) = 2*f(n-1)+1 = 2n -1

5.2 分割統治法 再帰呼び出しによる効率のよいアルゴリズムの例： マージソート(merge sort) 5.2　分割統治法 再帰呼び出しによる効率のよいアルゴリズムの例：　マージソート(merge sort) 入力： n = 2k (kは正整数）個の数の集合S（配列とする） 出力： Sの要素を昇順に並べたもの（配列とする） 手続き： |S|=2ならば、[min(S),max(S)]を返す 　　さもなくば、Sをn/2個ずつに分け、それぞれをマージソート(mergeSort)する。この二つの結果を、昇順に並べ(merge）、それを返す。 Sの最小要素 Sの最大要素

マージソートの実現(0) アルゴリズムから、mergeSortの全体像は： def mergeSort(s) n = s.size if (n == 2) # |S|=2の場合の手続きを書く---（１） else # それ以外の場合の手続きを書く---(2) end # if end # def

マージソートの実現(1) |S|=2のときに[min(S),max(S)]を返す def mergeSort(s) n = s.size これは簡単。条件文の使い方さえ分かっていれば… def mergeSort(s) n = s.size return s if n==1 # 一般性を考慮 if (n == 2) # s[0]とs[1]を比較して、 #　 [小さい方の要素、大きい方の要素] 　を返す else # 次で考える end # if end # def

マージソートの実現のために (1) |S|=2のときに[min(S),max(S)]を返す アルゴリズムを実現するには、以下の作業をするための「アルゴリズム」が必要： (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]　 により配列として取り出せる

mergeSortの動き(1) mergeSort([20, 10, 5, 15, 3, 7, 13, 18]) 0 1 2 3 4 5 6 7 mergeSort([20, 10, 5, 15, 3, 7, 13, 18]) def mergeSort(s) 8 n = s.size mid = (n－1)/2 x = mergeSort(s[0 .. mid]) y = mergeSort(s[(mid+1) .. (n－1)]) return merge(x,y) 3

mergeSortの動き(2) mergeSort([20, 10, 5, 15]) def mergeSort(s) 4 1 0 1 2 3 mergeSort([20, 10, 5, 15]) def mergeSort(s) 4 n = s.size mid = (n－1)/2 x = mergeSort(s[0 .. mid]) y = mergeSort(s[(mid+1) .. (n－1)]) return merge(x,y) 1

mergeSortの動き(3) mergeSort([20, 10]) def mergeSort(s) 2 true n = s.size 0 1 mergeSort([20, 10]) def mergeSort(s) 2 n = s.size if (s.size == 2) # [最小の要素、最大の要素]を返す return else … end true [10, 20]

mergeSortの動き(4) mergeSort([ 5, 15]) def mergeSort(s) n = s.size 0 1 mergeSort([ 5, 15]) def mergeSort(s) 2 n = s.size if (s.size == 2) # [最小の要素、最大の要素]を返す return else … end true [ 5, 15]

mergeSortの動き(2続） mergeSort([20, 10, 5, 15]) def mergeSort(s) [10, 20] 0 1 2 3 mergeSort([20, 10, 5, 15]) 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) [10, 20] [5,15]

マージ(merge)とは？ ・「再帰法」は、今作ろうとしている手続き(mergeSort)が小さな問題に対しては「ちゃんと正しい値を返してくれる」と考えて作る方法。だから、以下は「ソートされた数の配列が返されると仮定してよい」： 　　mergeSort(s[0..mid])　　# 配列sの前半 mergeSort(s[(mid+1)..(n-1)]) # 配列sの後半 とすると、考えなければならない問題は、返した結果を合わせて、昇順に並べる方法

マージ(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] というような昇順の配列を返す!

マージ(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

＜ mergeの動き(1) > < merge ( , ) [10, 20] [5, 15] xlen ylen 0 1 def merge(x, y) result = [ ] xlen = x.size ‐1; ylen = y.size ‐1 xc = 0; yc = 0　 while (xc <= xlen　&& yc <= ylen ) # x[xc]とy[yc]を比較しresultに入れる # 適切なプログラムを書く end # while 0 1 0 1 2 ＜ 10 20 5 15 y x 比較(小さい方をresultへ) x の残りの要素をすべてresultに入れる yc xc > < result [ ]

mergeSortの動き(２） mergeSort([20, 10, 5, 15]) def mergeSort(s) [10, 20] 0 1 2 3 mergeSort([20, 10, 5, 15]) 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) [10, 20] [5,15] [5, 10, 15, 20]

＜ < < mergeの動き(2) merge ( , ) [ 3, 7] [13, 18] xlen ylen 13 18 y [ 3, 7] [13, 18] xlen ylen 0 1 ２ 0 1 ＜ 3 7 13 18 y x 比較(小さい方をresultへ) yc xc y の残りの要素をすべてresultに入れる < < result [ ]

mergeSortの動き(1続) mergeSort([20, 10, 5, 15, 3, 7, 13, 18]) 0 1 2 3 4 5 6 7 mergeSort([20, 10, 5, 15, 3, 7, 13, 18]) def mergeSort(s) 8 n = s.size mid = (n－1)/2 x = mergeSort(s[0 .. mid]) y = mergeSort(s[(mid+1) .. (n－1)]) return merge(x,y) 3 [5,10,15,20] [3,7,13,18]

＜ < > mergeの動き(3) xlen ylen merge ( , ) [ 5, 10, 15, 20] 5 10 15 0 1 2 3 0 1 2 3 4 merge ( , ) [ 5, 10, 15, 20] 5 10 15 20 [ 3, 7, 13, 18] 3 7 13 18 yc xc xの残りの要素をすべてresultに入れる 比較(小さい方をresultへ) < > [ ] 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]

分割統治法 入力データの大きさをnとすると、そのデータを大きさ n/b の問題 a 個に分割し、それぞれを再帰的に解いた結果を利用して、元の問題の解を作るという方法(教科書、p.51)で、かつ 　計算時間 f(n) が n=1の時、 f(n) = c (ｃは定数） n ≧2の時、 f(n)=a*f(n/b) + cn （a,b,cは定数） 　となるもの(マージソートでは a=b=2) マージソートの計算量は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 ハノイの塔: hanoi(n,a,b,c) if (n == 1) 1枚円盤をaからcに移動 else hanoi(n-1,a,c,b) hanoi(n-1,b,a,c) end 計算量 　　　　　O(2n) 　　　　 O(n*log n)

ハノイの塔とマージソートの比較 ハノイの塔は再帰法を使っていても、その計算量は O(2n) マージソートでは、O(n*log n) この違いは何か？ 半分！ 答え： 　元の問題に対し、一定の比で小さな問題にして解く（マージソート）か、一定の差で小さな問題にして解く（ハノイの塔）か。(p.53-54)

再帰呼出しを使わない方がよい例 フィボナッチ数列(Fibonacci sequence) 定義：　非負整数nに対するフィボナッチ数F(n)とは 　　　 n=0　または n=1 のとき、１ 　　　それ以外： F(n) = F(n-1)+F(n-2) 　この形から、「ハノイの塔」タイプであることが明らか １ １ ２ ３ ５ ８ １３ ２１ ３４ ５５ ８９ １４４　…

フィボナッチ数F(n)を求める これを用いて fibo1(30)やfibo1(50)を計算させてみよう 先の定義を単純にプログラムすると以下のとおり： 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)を計算させてみよう

フィボナッチ数F(n)の別な求め方 これを用いて fibo2(30)やfibo2(50)を計算させてみよう 実は再帰を使わず、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)を計算させてみよう

実は。。。 教科書p.56にあるように、フィボナッチ数F(n)はO(log n)で求めることができる。 とすると ここで これを用いて F(10)やF (30)を計算しよう

まとめ：ハノイの塔の問題とフィボナッチ数の問題の違い ハノイの塔の問題で求めなければならないのは、「実際に円盤を移すこと」。円盤を移す回数が計算量となる。これは再帰を使わなくても同じ値になる。 　　指示手順を求めるという場合、具体的に「どの円盤をどこに移すか」という指示一つ一つが、「円盤を移すこと」と同じなので、指示の個数＝円盤を移す個数、となる。だからいずれにせよ 2nに比例した計算量 フィボナッチ数(関数F)を求める問題では、nが与えられた時にF(n)の値が求められればよい。これは定義通りに再帰を使わずに、 O(log n)という効率的な求め方がある。