Ruby、同じことの繰り返しは君に任せるよ 〜 再帰でハノイの塔を解こう！〜
もし問題が同じパターンの繰り返しを含んでいて
その極限の解が明らかならば
その問題の解決には再帰が使えるかもしれない
再帰はある問題の答えの中にその問題自体を含む不思議な構造だ
「GNU」は「GNU's Not UNIX」の頭文字からなる略称だ
ここで「GNU」は問題であり
その答え「GNU's Not UNIX」の中に問題自体が含まれている
だからGNUは明らかに再帰だ
「これじゃ答えになってない」
「つまり再帰は問題解決の役には立たない」
そういう声が聞こえてきそうだ
つまりあなたは「GNU's Not UNIX」が
「(GNU's Not UNIX)'s Not UNIX」になることを知っており
「((((GNU's Not UNIX)'s Not UNIX)'s Not UNIX)'s Not UNIX)'s Not UNIX」になることも知っており
したがって”どこまで行っても望みの答えは得られない”
ということに既に気がついているということだ
その通り！素晴らしい！
確かにGNUの意味はどこまで行っても得られないけど
それは再帰における極限の解が明らかにされていないからだ
仮にGNUの再帰を100回繰り返せば
「GNUはUNIXになる」とでもいう極限条件が与えられれば
答えは一応得られる(釈然とはしないけれども…)
GNUのことは諦めて「階乗」のことについて考えてみよう
「階乗」は自然数nに対する1からnまでの自然数の総乗を言う*1
つまり5の階乗5!は
5! = 1 * 2 * 3 * 4 * 5 = 120
となる
これをRuby1.9では以下のように書ける
1 class Integer
2 def !
3 (1..self).inject(:*)
4 end
5 end
6
7 puts 5.!
8 # >> 120
一方
5の階乗は以下のようにも表現できる
5! = 5 * 4!
つまり5の階乗は5に4の階乗を掛けたものとして表現できる
これはGNUの場合と同様に答えになっていない
5!がわからないのと同様に4!なんてものもわからないからだ
でもそう
これこそが再帰のマジックなんだ
幸いなことにGNUの場合と異なって
階乗の極限値ははっきりしている
1! = 1
だから階乗計算は再帰で解くことが出来るんだ
Rubyではこれらの式をそのまま書ける
1 class Integer
2 def factorial
3 return 1 if self == 1
4 self * (self-1).factorial
5 end
6 end
7
8 puts 5.factorial
9 # >> 120
もう少し凝って以下のようにしてもいい
1 class Integer
2 def 階乗
3 self * (self == 1 ? 1 : (self-1).階乗)
4 end
5 end
6
7 puts 5.階乗
8 # >> 120
でも
階乗計算なんて
会計用電卓のhp12cにだって簡単にできるんだから
ちっともうれしくない
それじゃあもう一歩進んで
「ハノイの塔」をやってみよう！
「ハノイの塔」は3本のポールと
サイズの異なる複数枚のドーナツ円盤を使ったパズルだ
スタートのポールに重ねられたすべての円盤を
予備のポールを活用しながら
ゴールとなるポールにすべて移動できれば正解だ
移動は一枚ずつ行い
如何なるときも
小さい円盤を大きい円盤の下に置いてはいけない*2
最小の円盤を1として
ポールの名前を(Start, Goal, Temp)とした場合
2枚の円盤(1、2)のハノイの答えは次のようになる
- 円盤1をStartからTempへ移動する
- 円盤2をStartからGoalへ移動する
- 円盤1をTempからGoalへ移動する
3枚の円盤(1、2、3)のハノイの答えは次のようになる
- 円盤1をStartからGoalへ移動する
- 円盤2をStartからTempへ移動する
- 円盤1をGoalからTempへ移動する
- 円盤3をStartからGoalへ移動する
- 円盤1をTempからStartへ移動する
- 円盤2をTempからGoalへ移動する
- 円盤1をStartからGoalへ移動する
まずはハノイの塔が再帰でいけるか検討してみる
答えの中に問いが含まれており
極限の答えがはっきりしていれば再帰でいける
例えば、円盤3枚の場合の問いをhanoi(3)とした場合
hanoi(3) = 3 * hanoi(2)
のような
答えの中に問いが含まれている形になればいい
一方
極限の答えはわかっている
円盤が0のとき(n=0)は動かすものが何もないのだから
hanoi(0) = 何もしない
となる
じゃあ円盤が1枚(n=1)のときはどうなるだろう
hanoi(1) = ”円盤1をStartからGoalに移動する”
円盤が1枚しかない場合の最適な移動はこれ以外にない
そうすると円盤が複数枚(n枚)ある場合の移動に関して
以下のような手順が見えてくる
- Startにある一番下の円盤nをGoalに移動できるようにするため、その前の手順として、他のすべての円盤(1〜n-1)の束をどうにかしてTempに一旦移動させる
- そして、Startにある一番下の円盤nをGoalに移動する
- その後、Tempに置いた他の円盤(1〜n-1)の束をすべてどうにかしてGoalに移動させる
ここで
1.に注目すると
これはまさにn-1枚の円盤を
StartからTempに移動させるというハノイの問題だ！
また
3.に注目すると
これもまたn-1枚の円盤を
TempからGoalに移動させるというハノイの問題だ！
つまりハノイの問題は
その答えにハノイの問題を含んだ再帰的なものになる！
そしてその極限の値n=0の答えは明らかだ
よって「ハノイの塔」は再帰で解くことができる！
これをもう少しまとめると
hanoi(n)の答えは以下のようになる
hanoi(n) =
1. n = 0 のときは何もしない,
2. hanoi(n-1)を求める。但し移動はStart => Temp,
3. "円盤nをStartからGoalへ移動する”,
4. hanoi(n-1)を求める。但し移動はTemp => Goal
これをRubyで記述してみる
1 POLES = ['Start', 'Goal', 'Temp']
2
3 def hanoi(n, from=POLES[0], to=POLES[1])
4 temp = (POLES - [from, to]).to_s
5 return if n == 0
6 hanoi(n-1, from, temp)
7 puts "move #{n} #{from} => #{to}"
8 hanoi(n-1, temp, to)
9 end
10
11 hanoi(3)
12
13 # >> move 1 Start => Goal
14 # >> move 2 Start => Temp
15 # >> move 1 Goal => Temp
16 # >> move 3 Start => Goal
17 # >> move 1 Temp => Start
18 # >> move 2 Temp => Goal
19 # >> move 1 Start => Goal
せっかくだから
円盤をA,B,C,…として
Hanoiクラスも書いてみよう
1 class Hanoi
2 POLES = ['Start', 'Goal', 'Temp']
3 DISCS = ('A'..'Z').to_a
4
5 def initialize(n)
6 @n = n
7 @from = POLES[0]
8 @to = POLES[1]
9 @cnt = 0
10 @result = []
11 end
12
13 def steps
14 @result = []
15 hanoi(@n, @from, @to)
16 end
17
18 def to_s
19 @result = []
20 answer = ""
21 result = hanoi(@n, @from, @to)
22 result.each_with_index do |(disc,from,to), i|
23 answer << "#{i+1}: move #{DISCS[disc-1]} #{from} => #{to}\n"
24 end
25 answer
26 end
27
28 private
29 def hanoi(n, from, to)
30 tmp = (POLES - [from, to]).to_s
31 return @result if n == 0
32 hanoi(n-1, from, tmp)
33 @cnt += 1
34 @result << [n, from, to]
35 hanoi(n-1, tmp, to)
36 end
37 end
38
39 if __FILE__ == $0
40 h = Hanoi.new(3)
41 puts h
42 end
43 # >> 1: move A Start => Goal
44 # >> 2: move B Start => Temp
45 # >> 3: move A Goal => Temp
46 # >> 4: move C Start => Goal
47 # >> 5: move A Temp => Start
48 # >> 6: move B Temp => Goal
49 # >> 7: move A Start => Goal
Rubyを使って再帰とハノイの塔を勉強したので
それをまとめてみました
参考になればうれしいです
(参考サイト)
再帰的アルゴリズム
第１７章 再帰的手続き 他
(追記:2008/7/10)Hanoiクラスを少し修正しました
