2011/06/21 情報知能学科「アルゴリズムとデータ構造」 担当:白井英俊 5章 再帰呼出しと分割統治 杉原厚吉.(2001).「データ構造とアルゴリズム」. 東京:共立出版. 2011/06/21 情報知能学科「アルゴリズムとデータ構造」 担当:白井英俊
本章の目的 問題の性質を見極めて、「複雑な問題を、より単純な小問題に分割して解く」ことを学ぶ 効率は『計算量』だけではない。問題を解くための考えやすさ、分かりやすさも大事 複雑な問題を分割して解くことの代表的なものが再帰 ― 小問題が大問題の類似形の場合に有効 分割することで効率が悪くなることもある!
5.1 再帰呼び出し 再帰呼び出し(recursive call) ― 手続き(関数)の中で自分自身(その関数)を呼び出すこと 5.1 再帰呼び出し 再帰呼び出し(recursive call) ― 手続き(関数)の中で自分自身(その関数)を呼び出すこと 特長:ある種の手続きを簡潔に表現できる 特に、問題自身が再帰的な場合に有効 例: 二進木のなぞり :「二進木」は『左の部分木』、と『右の部分木』に分かれる。だから、木を中間順 (inorder)になぞるには、 (1)左の木をinorderでなぞる、(2)木の根を表示する、 (3)右の木をinorderでなぞる、 とすればよい。 これは、「左の木」も「右の木」も、木全体の類似形だから、再帰を使うのが有効
中間順による二進木のなぞり:inorder関数 この前は「インスタンスメソッド」として実現。今度は二進木のインスタンスを引数とする「関数」として実現することを考える 再帰の場合、『どのような場合に再帰しない(停止する)か』という検査を最初に実行(参考:数学的帰納法) def inorder(tree) if (tree != nil) # tree==nilなら再帰しない inorder(tree.left) # 左の部分木を中間順で print tree.data # 頂点のデータを表示 inorder(tree.right) # 右の部分木を中間順で end # if end # def インスタンスメソッドとの比較: (1)「木」を表す引数が必要 インスタンスメソッドでは 不要(@selfと同じだから) (2) インスタンスの部品(イン スタンス変数)の参照方法 @data, @left, @right
インスタンスメソッドと「関数」 インスタンスメソッド class Vertex def initialize(data, left, right) @data = data @left = left @right = right end # initialize attr_attribute :data, :left, :right def inorder @left.inorder if @left != nil print @data @right.inorder if @right != nil end # def of inorder end # class インスタンスメソッドの呼出し: xをVertexのインスタンスとすると x.inorder xのクラスに付随するメソッドinorder が呼び出される それに対し 関数としてのinorderの 実現では、Vertexのインス タンスを引数して呼出す: inorder(x)
中間順による木のなぞり(関数版) inorder(1) 実行結果 1 inorder(2) 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 に対して: 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 9 2 10 5 1 6 3 7
先行順による木のなぞり 先行順(頂点、左の部分木、右の部分木) def preorder(tree) 同様に、関数として実現することを考える if (tree != nil) # tree==nilなら再帰しない print tree.data # 頂点のデータを表示 preorder(tree.left) # 左の部分木をpreorderで preorder(tree.right) # 右の部分木をpreorderで end # if end # def
先行順による木のなぞり 2 3 4 5 6 7 8 9 10 実行 1 に対して: 1 2 4 8 9 5 10 3 6 7 ① ③ ① ② 実行 1 2 3 4 5 6 7 8 9 10 に対して: ③ ① ② ① ③ ② ① ② ③ ② 1 2 4 8 9 5 10 3 6 7
後行順による木のなぞり 後行順(左の部分木、右の部分木、頂点) 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
後行順による木のなぞり 2 3 4 5 6 7 8 9 10 実行 1 に対して: 8 9 4 10 5 2 6 7 3 1 ③ ① ② ③ 実行 1 2 3 4 5 6 7 8 9 10 に対して: ① ② ③ ② ③ ① ② ① ① ② 8 9 4 10 5 2 6 7 3 1
応用:数式の構文木 例: (a+b)*(c-d*e) は次の二進木で表現される(葉には変数が、葉以外の頂点は演算子が書かれる) これを数式の「構文木」 と呼ぶ。数式の構造 (どこの塊同士がどのような 演算によって結合されてい るか)が明示されている * + ー a b c * d e
数式の構文木の演習 * ー + c a b d e 先の木を 1) 中間順(inorder) 2) 先行順(preorder) 3) 後行順(postorder) でそれぞれなぞると… 参考:ポーランド記法、逆ポーランド記法 * ー + c a b d e
数式の構文木の演習(解) 日本語的! (a+b)*(c-d*e) の構文木を以下の方法でなぞると: 1) 中間順(inorder) 2) 先行順(preorder): 数式のポーランド記法 * + a b – c * d e 3) 後行順(postorder): 逆ポーランド記法 a b + c d e * – * 日本語的!
2進木以外の「木のなぞり」 「先行順」と「後行順」による木のなぞりは、2進木でなくとも使える(中間順も無理すればできなくはない)
一般の木の表現 一般の木構造を次のようなデータ構造(ノードと呼ぶ)で表す class Node 一般の木の表現 一般の木構造を次のようなデータ構造(ノードと呼ぶ)で表す class Node def initialize(u,v,w,x) @label = u @parent = v @firstChild = w @nextBrother = x end @parent @firstChild self @nextBrother 注意:枝の向きが明らかな場合は矢印を省略する
木の表現(続) クラスNodeを図示すると、次のようになる 頂点 親頂点 兄弟頂点 子頂点 label (ラベル) parent (親) 一個一個が以下の構造をもつ 親頂点 label (ラベル) parent (親) firstChild(第一子) nextBrother(次の兄弟) @parent @firstChild self @nextBrother 兄弟頂点 子頂点
NodeクラスとVertexクラスの比較 class Node # 一般の木の頂点を表現するクラス def initialize(label, parent, firstChild, nextBrother) @parent = parent # 親ノード @firstChild = firstChild # 第一子 @nextBrother = nextBrother # 次の兄弟 @label = label end # def initialize end 頂点のラベル(値) class Vertex # 2進木用の頂点を表現するクラス def initialize(data, left ,right) @left = left # 左の部分木 @right = right # 右の部分木 @data = data # 頂点の値 end # def initialize end # class 子の頂点
一般の木のなぞり ある頂点 n からみると 子の頂点すべてを取り出すことは、すぐにはできない class Node def initialize(u,v,w,x) @label = u @parent = v @firstChild = w @nextBrother = x end ある頂点 n からみると 子の頂点すべてを取り出すことは、すぐにはできない 比較:二進木では子の頂点は左と右だけで、それぞれ@leftと@rightで取り出せた 最初の子しか見えない だから、「木をなぞる」には、「子頂点をすべて取り出す」ためのしかけが必要 それには、「次の兄弟」を使う!
一般の木において子頂点をすべて表示する:「木のなぞり」の準備 右の木を例にとって考える。 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の「兄弟」頂点
兄弟頂点を訪問するメソッド class Node # 一般の木の頂点を表現するクラス def initialize(label, parent, firstChild, nextBrother) @parent = parent # 親ノード @firstChild = firstChild # 第一子 @nextBrother = nextBrother # 次の兄弟 @label = label end # def initialize attr_accessor :parent, :firstChild, :nextBrother, :label def brothers return if (@nextBrother == nil) # 次の兄弟がいない場合 print @nextBrother.label @nextBrother.brothers # 次次と兄弟を訪問 end
参考:先祖の頂点を要素とする配列を求める 右の木を例にとって考える。v5を対象とすると、その「親」はどのようにしたら取り出せるだろうか? また「先祖」(親、親の親、親の親の親…)は? 例題の木 v0 v1 v3 v2 v6 答え: v5.parent = v1 v5 v4 v5.parent.parent = v0 @parent Nodeクラス ある頂点の「先祖」頂点とは、 (1) (親がいれば)親 、に加えて (2) 親の「先祖」頂点 self @nextBrother @firstChild
先祖の頂点の配列を求める(続) class Node # 一般の木の頂点を表現するクラス def initialize(label, parent, firstChild, nextBrother) @parent = parent # 親ノード @firstChild = firstChild # 第一子 @nextBrother = nextBrother # 次の兄弟 @label = label end # def initialize attr_accessor :parent, :firstChild, :nextBrother, :label def ancestors return [ ] if (@parent == nil) # 親がいない場合 # そうでなければ 親+親の先祖 を返す return [@parent]+@parent.ancestors end
プログラミング演習 一般の木において(Nodeクラスを使用) treeTemplate.rb 参照のこと (1)先行順に木の頂点を訪れるインスタンスメソッド preorder (2) 後行順に木の頂点を訪れるインスタンスメソッド postorder を作る
再帰的な構造、効率の悪い問題 Hanoiの塔:再帰的な構造をしていて、計算量が大きな問題の典型例 詳しくは別紙の資料参照 詳しくは別紙の資料参照 (右図はWikipediaより拝借) 問題:n枚の円盤を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の等比数列
(予習)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の場合の手続きを書く---(1) 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する)
マージソートの実現(2) 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] により配列として取り出せる
マージ(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)]) は、それぞれソートされた配列を返す。 例: [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] というような昇順の配列を返す関数
マージ(merge)関数を作る def merge(x,y) result = [ ] # マージした結果の記録用 xlen = x.size ‐1; ylen = y.size ‐1 # xとyの最後の要素のインデックス xc = 0; yc = 0 # xとyそれぞれ「見る」要素の番号 while (xc <= xlen && yc <= ylen ) # 未検査要素あり # x[xc]とy[yc]を比較しresultに入れるなど # 適切なプログラムを書く end # while # xかyに未検査のものがある場合の処理を書く end # def
マージソートの完成 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 (cは定数) n ≧2の時、 f(n)=a*f(n/b) + cn (a,b,cは定数) となるもの(マージソートでは a=b=2)
ハノイの塔とマージソートの比較 ハノイの塔は再帰法を使っていても、その計算量は O(2n) マージソートでは、O(n*log n) この違いは何か? 答え: 元の問題に対し、一定の比で小さな問題にして解く(マージソート)か、一定の差で小さな問題にして解く(ハノイの塔)か。(p.53-54)
再帰呼出しを使わない方がよい例 フィボナッチ数列(Fibonacci sequence) 定義: 非負整数nに対するフィボナッチ数F(n)とは n=0 または n=1のとき、1 それ以外: F(n) = F(n-1)+F(n-2) この形から、「ハノイの塔」タイプであることが明らか
フィボナッチ数F(n)を求める 先の定義を単純にプログラムすると以下のとおり: def fibo1(n) if (n==0 || n==1) return 1 else return fibo1(n-1)+fibo1(n-2) end # if end #def
フィボナッチ数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行目を訂正
実は。。。 教科書p.56にあるように、フィボナッチ数F(n)はO(log n)で求めることができる。