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

5章再帰呼出しと分割統治
杉原厚吉．（２００１）.「データ構造とアルゴリズム」.
東京：共立出版.
2011/06/21
情報知能学科「アルゴリズムとデータ構造」
担当：白井英俊
本章の目的
• 問題の性質を見極めて、「複雑な問題を、より
単純な小問題に分割して解く」ことを学ぶ
• 効率は『計算量』だけではない。問題を解くた
めの考えやすさ、分かりやすさも大事
• 複雑な問題を分割して解くことの代表的なも
のが再帰 ― 小問題が大問題の類似形の場
合に有効
• 分割することで効率が悪くなることもある！
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
インスタンスメソッドの呼出し：
xをVertexのインスタンスとすると
x.inorder
def inorder
@left.inorder if @left != nil
print @data
@right.inorder if @right != nil
end # def of inorder
end # class
xのクラスに付随するメソッドinorder
が呼び出される
それに対し
関数としてのinorderの
実現では、Vertexのインス
タンスを引数して呼出す：
inorder(x)
中間順による木のなぞり（関数版）
• 実行結果
②
①
②
③
１
２ ③
①
② ４
５
③
① ８
９１０
inorder(1)
inorder(2)
print(1)
３
６
inorder(3)
７
に対して：
8
4
９
2
10
５ 1
6
3
7
inorder(4)
inorder(6)
print(2)
print(3)
inorder(5)
inorder(7)
inorder(10)
inorder(8)
print(4)
print(5)
inorder(9)
先行順による木のなぞり
同様に、関数として実現することを考える
• 先行順（頂点、左の部分木、右の部分木）
def preorder(tree)
if (tree != nil) # tree==nilなら再帰しない
print tree.data
# 頂点のデータを表示
preorder(tree.left) # 左の部分木をpreorderで
preorder(tree.right) # 右の部分木をpreorderで
end # if
end # def
先行順による木のなぞり
①
実行
②
①
②
①
②
８
２
１
③
③
３
４ ③
５
９１０ ②
①
６
に対して：
1
2
4
8
9
5
10
3 6 7
７
後行順による木のなぞり
これも、関数として実現することを考える
• 後行順（左の部分木、右の部分木、頂点）
def postorder(tree)
if (tree != nil) # tree==nilなら再帰しない
postorder(tree.left) # 左の部分木をpostorderで
postorder(tree.right) # 右の部分木をpostorderで
print tree.data
# 頂点のデータを表示
end # if
end # def
後行順による木のなぞり
③
実行
①
①
③
③
２
１
８
３
②
４ ② ① ５
９１０
①
②
②
６
に対して：
8
9
4
10 5 2
6 7 3 1
７
応用：数式の構文木
例： (a+b)*(c-d*e) は次の二進木で表現される（葉に
は変数が、葉以外の頂点は演算子が書かれる）
これを数式の「構文木」
と呼ぶ。数式の構造
＊
＋
a
ー
b
（どこの塊同士がどのような
演算によって結合されてい
るか)が明示されている
＊
c
d
e
数式の構文木の演習
＊
＋
ー
• 先の木を
b c
１）中間順(inorder) a
＊
２）先行順(preorder)
d
e
３）後行順(postorder)
でそれぞれなぞると…
参考：ポーランド記法、逆ポーランド記法
数式の構文木の演習（解）
• (a+b)*(c-d*e) の構文木を以下の方法でなぞ
ると：
１）中間順(inorder)
a+b*c–d*e
２）先行順(preorder): 数式のポーランド記法
*+a b–c* d e
３）後行順(postorder)：逆ポーランド記法
日本語的！
a b+ c d e*–*
２進木以外の「木のなぞり」
• 「先行順」と「後行順」による木のなぞ
りは、２進木でなくとも使える(中間順も無
理すればできなくはない)
一般の木の表現
• 一般の木構造を次のようなデータ構造（ノード
と呼ぶ）で表す
class Node
@parent
def initialize(u,v,w,x)
@label = u
self
@parent = v
@nextBrother
@firstChild = w
@nextBrother = x
@firstChild
end
注意：枝の向きが明らかな場合は矢印を省略する
end
木の表現(続)
クラスNodeを図示すると、次のようになる
頂点一個一個が以下の構造をもつ
@parent
親頂点
label (ラベル）
parent (親）
self
@nextBrother
firstChild(第一子）
nextBrother(次の兄弟）
@firstChild
子頂点
兄弟頂点
NodeクラスとVertexクラスの比較
class Node
# 一般の木の頂点を表現するクラス
def initialize(label, parent, firstChild, nextBrother)
@parent = 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
子の頂点
一般の木のなぞり
class Node
• ある頂点 n からみると
def initialize(u,v,w,x)
子の頂点すべてを取り
@label = u
出すことは、すぐにはで
@parent = v
最初の子しか見えない
きない
@firstChild = w
比較：二進木では子の頂点は左と
@nextBrother = x
右だけで、それぞれ@leftと
end
@rightで取り出せた
end
だから、「木をなぞる」には、「子頂点をすべて取り
出す」ためのしかけが必要
それには、「次の兄弟」を使う！
一般の木において子頂点をすべて表
示する：「木のなぞり」の準備
右の木を例にとって考える。
v0を対象とすると、その「子」は
どのようにしたら取り出せるだろ
うか？
答え：
v0.firstChild = v1
v1
v0.firstChild.nextBrother
例題の木
v1
v4
v1
v0.firstChild.nextBrother.nextBrother
ある頂点の「兄弟」頂点をすべて取り出す
インスタンスメソッドがほしい！
子頂点＝最初の子(s)＋sの「兄弟」頂点
v0
v3
v2
v6
v5
Nodeクラス
@parent
self
@firstChild
@nextBrother
兄弟頂点を訪問するメソッド
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
を対象とすると、その「親」は
どのようにしたら取り出せるだ
ろうか？
また「先祖」（親、親の親、親の
親の親…)は？
答え：
v５.parent = v1
v5.parent.parent = v0
ある頂点の「先祖」頂点とは、
(1) （親がいれば)親、に加えて
(2) 親の「先祖」頂点
例題の木
v1
v4
v0
v3
v2
v6
v5
Nodeクラス
@parent
self
@firstChild
@nextBrother
先祖の頂点の配列を求める（続）
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][email protected]
end
プログラミング演習
一般の木において（Nodeクラスを使用）
treeTemplate.rb 参照のこと
(1)先行順に木の頂点を訪れるインスタンスメ
ソッド preorder
(2) 後行順に木の頂点を訪れるインスタンスメ
ソッド postorder を作る
再帰的な構造、効率の悪い問題
• 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に移す
print ’move the disk from ’,a,’ to ’,c,”\n”
hanoi(n－1,b,a,c) # n－1枚の円盤をbからcに移す
end # if
end # def
ハノイの塔の計算量
• 円盤をn枚移すのにかかる計算量を f(n)
とすると、このアルゴリズムは g(n)=f(n)＋αとすると、g(n)は
２の等比数列
f(n) = 2*f(n-1)+α
という計算量が必要である。(円盤を1枚移す手間を定数「 α 」と
している）
したがって、f(n) は O(2n)
これはアルゴリズムのせいではなく、問題自体が難し
い（指数オーダーの計算量を必要とする）から
＝＞アルゴリズムが簡潔に書けるからといって、その
アルゴリズムの効率がよいということにはならない
（予習)5.2 分割統治法
• 再帰呼び出しによる効率のよいアルゴリズムの例：
マージソート(merge sort)
• 入力： n = 2k (kは正整数）個の数の集合S（配列と
する）
• 出力： Sの要素を昇順に並べたもの（配列とする）
Sの最小要素
Sの最大要素
• 手続き：
|S|=2ならば、[min(S),max(S)]を返す
さもなくば、Sをn/2個ずつに分け、それぞれをマー
ジソート(mergeSort)する。この二つの結果を、昇順
に並べ(merge）、それを返す。
マージソートの実現(0)
アルゴリズムから、mergeSortの全体像は：
def mergeSort(s)
n = s.size
if (n == 2)
# |S|=2の場合の手続きを書く---（１）
else
# それ以外の場合の手続きを書く---(2)
end # if
end # def
マージソートの実現(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
マージソートの実現のために
アルゴリズムを実現するには、以下の作業をするための「アル
ゴリズム」が必要：
(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]
により配列として取り出せる
マージ(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
# ｘとｙの最後の要素のインデックス
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 (ｃは定数）
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のとき、１
それ以外： 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
FIBO2(p.54)の1行目を訂正
for i in 2..n
z = x+y ; x = y; y = z
end # for
return z
end # def
実は。。。
• 教科書p.56にあるように、フィボナッチ数F(n)
はO(log n)で求めることができる。

Download Report