2011/06/21 情報知能学科「アルゴリズムとデータ構造」 担当：白井英俊

Presentation on theme: "2011/06/21 情報知能学科「アルゴリズムとデータ構造」 担当：白井英俊"— Presentation transcript:

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

2 本章の目的 問題の性質を見極めて、「複雑な問題を、より単純な小問題に分割して解く」ことを学ぶ
効率は『計算量』だけではない。問題を解くための考えやすさ、分かりやすさも大事 複雑な問題を分割して解くことの代表的なものが再帰 ― 小問題が大問題の類似形の場合に有効 分割することで効率が悪くなることもある！

3 5.1 再帰呼び出し 再帰呼び出し（recursive call) ― 手続き（関数）の中で自分自身（その関数）を呼び出すこと
5.1　再帰呼び出し 再帰呼び出し（recursive call) ―　手続き（関数）の中で自分自身（その関数）を呼び出すこと 特長：ある種の手続きを簡潔に表現できる 特に、問題自身が再帰的な場合に有効 例：　二進木のなぞり ：「二進木」は『左の部分木』、と『右の部分木』に分かれる。だから、木を中間順 (inorder)になぞるには、 　　　（1）左の木をinorderでなぞる、(2)木の根を表示する、 　　 (3)右の木をinorderでなぞる、 とすればよい。 　　これは、「左の木」も「右の木」も、木全体の類似形だから、再帰を使うのが有効

4 中間順による二進木のなぞり：inorder関数
　この前は「インスタンスメソッド」として実現。今度は二進木のインスタンスを引数とする「関数」として実現することを考える 　再帰の場合、『どのような場合に再帰しない（停止する）か』という検査を最初に実行（参考：数学的帰納法） def inorder(tree) if (tree != nil) # tree==nilなら再帰しない inorder(tree.left) # 左の部分木を中間順で print tree.data # 頂点のデータを表示 inorder(tree.right) # 右の部分木を中間順で end # if end # def インスタンスメソッドとの比較： (1)「木」を表す引数が必要 　インスタンスメソッドでは 　 (2) インスタンスの部品（イン スタンス変数）の参照方法

5 インスタンスメソッドと「関数」 インスタンスメソッド
class Vertex def initialize(data, left, right) @data = data @left = left @right = right end # initialize attr_attribute :data, :left, :right def inorder 　 @left.inorder != nil　 print @data @right.inorder != nil　 end # def of inorder end # class インスタンスメソッドの呼出し： xをVertexのインスタンスとすると x.inorder xのクラスに付随するメソッドinorder が呼び出される それに対し 関数としてのinorderの 実現では、Vertexのインス タンスを引数して呼出す： inorder(x)

6 中間順による木のなぞり（関数版） inorder(1) 実行結果 １ inorder(2) ２ ３ ４ ５ ６ ７ ８ ９ １０
　　　　　　　　　　　　　 １ 　　　　　　　　　　２　　　　　　　　　　３ 　　　　　　４　　　　　　５　　　　６　　　　７ 　　　　８　　　９　　１０ に対して： inorder(1) ② ③ inorder(2) ① print(1) ② inorder(3) ① ③ ② ③ inorder(6) inorder(4) ① print(2) print(3) inorder(5) inorder(7) inorder(10) inorder(8) print(4) print(5) inorder(9) 8 4 ９ 2 10 ５ 1 6 3 7

7 先行順による木のなぞり 先行順（頂点、左の部分木、右の部分木） def preorder(tree) 同様に、関数として実現することを考える
if (tree != nil) # tree==nilなら再帰しない print tree.data # 頂点のデータを表示 preorder(tree.left) # 左の部分木をpreorderで preorder(tree.right) # 右の部分木をpreorderで end # if end # def

8 先行順による木のなぞり ２ ３ ４ ５ ６ ７ ８ ９ １０ 実行 １ に対して： 1 2 4 8 9 5 10 3 6 7 ① ③ ① ②
実行　　　　　　　　　　　１ 　　　　　　　　　　２　　　　　　　　３ 　　　　　　４　　　　　　５　　　６　　　７ 　　８　　　９　　１０ に対して： ③ ① ② ① ③ ② ① ② ③ ② 1 2 4 8 9 5 10 3 6 7

9 後行順による木のなぞり 後行順（左の部分木、右の部分木、頂点） def postorder(tree)
これも、関数として実現することを考える 後行順（左の部分木、右の部分木、頂点） def postorder(tree) if (tree != nil) # tree==nilなら再帰しない postorder(tree.left) # 左の部分木をpostorderで postorder(tree.right) # 右の部分木をpostorderで print tree.data # 頂点のデータを表示 end # if end # def

10 後行順による木のなぞり ２ ３ ４ ５ ６ ７ ８ ９ １０ 実行 １ に対して： 8 9 4 10 5 2 6 7 3 1 ③ ① ② ③
実行　　　　　　　　　　　１ 　　　　　　　　　　２　　　　　　　　３ 　　　　　　４　　　　　　５　　　６　　　７ 　　８　　　９　　１０ に対して： ① ② ③ ② ③ ① ② ① ① ② 8 9 4 10 5 2 6 7 3 1

11 応用：数式の構文木 例： (a+b)*(c-d*e) は次の二進木で表現される（葉には変数が、葉以外の頂点は演算子が書かれる） これを数式の「構文木」 と呼ぶ。数式の構造 （どこの塊同士がどのような 演算によって結合されてい るか)が明示されている ＊ ＋ ー a b c ＊ d e

12 数式の構文木の演習 ＊ ー ＋ c a b d e 先の木を １） 中間順(inorder) ２） 先行順(preorder)
　　３）　後行順(postorder) 　でそれぞれなぞると… 参考：ポーランド記法、逆ポーランド記法 ＊ ー ＋ c a b d e

13 数式の構文木の演習（解） 日本語的！ (a+b)*(c-d*e) の構文木を以下の方法でなぞると： １） 中間順(inorder)
　２）　先行順(preorder): 数式のポーランド記法 * + a b – c * d e 　３）　後行順(postorder)：　逆ポーランド記法 　 a b + c d e * – * 日本語的！

14 ２進木以外の「木のなぞり」 「先行順」と「後行順」による木のなぞりは、２進木でなくとも使える(中間順も無理すればできなくはない)

15 一般の木の表現 一般の木構造を次のようなデータ構造（ノードと呼ぶ）で表す class Node
　　　一般の木の表現 一般の木構造を次のようなデータ構造（ノードと呼ぶ）で表す class Node def initialize(u,v,w,x) @label = u @parent = v @firstChild = w @nextBrother = x end @parent @firstChild self @nextBrother 注意：枝の向きが明らかな場合は矢印を省略する

16 木の表現(続) クラスNodeを図示すると、次のようになる 頂点 親頂点 兄弟頂点 子頂点 label (ラベル） parent (親）
一個一個が以下の構造をもつ 親頂点 label (ラベル） parent (親） firstChild(第一子） nextBrother(次の兄弟） @parent @firstChild self @nextBrother 兄弟頂点 子頂点

17 NodeクラスとVertexクラスの比較
class Node　 　　　　# 一般の木の頂点を表現するクラス def initialize(label,　parent,　firstChild,　nextBrother) = parent　　　　 # 親ノード @firstChild = firstChild # 第一子 @nextBrother = nextBrother # 次の兄弟 @label = label end # def 　initialize end 頂点のラベル（値） class Vertex　　　# ２進木用の頂点を表現するクラス 　　 def initialize(data,　left　,right) 　 @left = left 　# 左の部分木 　 @right = right # 右の部分木 　 @data = data # 頂点の値 　 end # def initialize end # class 子の頂点

18 一般の木のなぞり ある頂点 n からみると 子の頂点すべてを取り出すことは、すぐにはできない
class Node def = = = = x end ある頂点 n からみると 　子の頂点すべてを取り出すことは、すぐにはできない 最初の子しか見えない だから、「木をなぞる」には、「子頂点をすべて取り出す」ためのしかけが必要 それには、「次の兄弟」を使う！

19 一般の木において子頂点をすべて表示する：「木のなぞり」の準備
右の木を例にとって考える。 v0を対象とすると、その「子」は どのようにしたら取り出せるだろ うか？ 例題の木 v0 v1 v3 v2 答え： v0.firstChild　= v1 v6 v5 v4 v0.firstChild.nextBrother v1 @parent @firstChild self v0.firstChild.nextBrother.nextBrother v1 Nodeクラス ある頂点の「兄弟」頂点をすべて取り出す インスタンスメソッドがほしい！ @nextBrother 子頂点＝最初の子(s)＋sの「兄弟」頂点

20 兄弟頂点を訪問するメソッド class Node # 一般の木の頂点を表現するクラス
def initialize(label,　parent,　firstChild,　nextBrother) = parent　　　　 # 親ノード @firstChild = firstChild # 第一子 @nextBrother = nextBrother # 次の兄弟 @label = label end # def 　initialize 　 attr_accessor :parent, :firstChild, :nextBrother, :label def brothers return if == nil) # 次の兄弟がいない場合 @nextBrother.brothers　　　　　　# 次次と兄弟を訪問 end

21 参考：先祖の頂点を要素とする配列を求める
右の木を例にとって考える。v5を対象とすると、その「親」はどのようにしたら取り出せるだろうか？ また「先祖」（親、親の親、親の親の親…)は？ 例題の木 v0 v1 v3 v2 v6 答え： v５.parent　= v1 v5 v4 v5.parent.parent = v0 @parent Nodeクラス ある頂点の「先祖」頂点とは、 (1) （親がいれば)親　、に加えて (2) 親の「先祖」頂点 self @nextBrother @firstChild

22 先祖の頂点の配列を求める（続） class Node # 一般の木の頂点を表現するクラス
def initialize(label,　parent,　firstChild,　nextBrother) = parent　　　　 # 親ノード @firstChild = firstChild # 第一子 @nextBrother = nextBrother # 次の兄弟 @label = label end # def 　initialize 　 attr_accessor :parent, :firstChild, :nextBrother, :label def ancestors return [ ] if == nil) # 親がいない場合 # そうでなければ　親＋親の先祖　を返す return end

23 プログラミング演習 一般の木において（Nodeクラスを使用） treeTemplate.rb 参照のこと (1)先行順に木の頂点を訪れるインスタンスメソッド preorder (2) 後行順に木の頂点を訪れるインスタンスメソッド postorder を作る

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

25 プログラム 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

26 ハノイの塔の計算量 円盤をn枚移すのにかかる計算量を f(n) とすると、このアルゴリズムは f(n) = 2*f(n-1)+α
という計算量が必要である。(円盤を1枚移す手間を定数「 α 」としている） したがって、f(n) は O(2n) これはアルゴリズムのせいではなく、問題自体が難しい（指数オーダーの計算量を必要とする）から ＝＞アルゴリズムが簡潔に書けるからといって、そのアルゴリズムの効率がよいということにはならない g(n)=f(n)＋αとすると、g(n)は２の等比数列

27 （予習)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の最大要素

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

29 マージソートの実現(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

30 マージソートの実現のために (1) |S|=2のときに[min(S),max(S)]を返す
アルゴリズムを実現するには、以下の作業をするための「アルゴリズム」が必要： (1) |S|=2のときに[min(S),max(S)]を返す (2) Sをn/2個ずつに分け、それぞれをマージソート(mergeSort)し、二つのマージソートが返した結果を合わせて、昇順に並べる(mergeする）

31 マージソートの実現(２) 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]　 により配列として取り出せる

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

33 マージ(merge) つまり mergeSort(s[0..mid]) mergeSort(s[(mid+1)..(n－1)])
は、それぞれソートされた配列を返す。 例：　[1,3,5,9,11,15,18,20] 　　[2,4,6,8,10,12,14,16] マージ(merge)は、この二つを入力として、 [1,2,3,4,5,6,8,9,10,11,12,14,15,16,18,20] というような昇順の配列を返す関数

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

35 マージソートの完成 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]

36 分割統治法 入力データの大きさを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)

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

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

39 フィボナッチ数F(n)を求める 先の定義を単純にプログラムすると以下のとおり： def fibo1(n) if (n==0 || n==1)
return 1 else return fibo1(n-1)+fibo1(n-2) end # if end #def

40 フィボナッチ数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(p.54)の1行目を訂正

41 実は。。。 教科書p.56にあるように、フィボナッチ数F(n)はO(log n)で求めることができる。