プログラマーは今こそアルゴリズムを書くべき!!2~再帰アルゴリズムでハノイの塔を解く~
アルゴリズム第二弾ということで今回はハノイの塔を再帰アルゴリズムで解く説明をしていきます。
という流れで説明します。
ハノイの塔とは?
次の図のようなものがあったとします。
簡単に説明すると3つの棒があって、円盤が上から小さい順に重ねられている。
これを次の条件のもと別の棒に全て移動させることができれば終了。
条件
- 一回の移動に一枚しか移動できない。
- 小さい円盤の上に大きい円盤をのせてはいけない。
これだけ!
このルールで上記の図を次のようにすると終了。
ここで3枚円盤が合った場合、何回で移動できるかを少し考えてみて下さい。
ハノイの塔の最小移動回数
先ほどの回答ですが、
まず円盤が一枚のときは
1回
二枚のときは
3回
三枚のときは
7回
四枚のときは
15回となります。
。。。
というわけで何やら数列っぽくなっているのがわかります。
なので n 回の時も考えてみます。
枚数 => 回数とすると
1 => 1
2 => 3
3 => 7
4 => 15
。。。
n => (2^n) - 1
となりました!!
というわけで n 回の時の回数を出すための式は上記の式で表すことができます。
でもちょっとこれって本当にそうなのかという感じもなくはないですよね。
帰納法かなんかで証明するのもかったるいですし…
ここで少し考えなおしてもっと簡単に移動回数を出す方法を考えてみましょう。
再帰アルゴリズムでハノイの塔を解く
一度整理するために、移動方法をもう一度考えてみましょう。
一枚の場合
単純に
左 -> 中
で一回
二枚の場合
移動する円盤は上から順に1,2,3,4,...,nという添字をつけます。
左1 -> 右1 , 左2 -> 中2, 右1 -> 中1
で三回
三枚の場合
左1 -> 中1, 左2 -> 右2, 中1 -> 右1, 左3 -> 中3, 右1 -> 左1, 右2 -> 中2, 左1 -> 中1
で七回
。。。
ここであることに気がつくはずです。
三枚を例にとると
- まず二枚分を移動
- 最後の一枚を目的のところに移動
- 最初に動かした二枚分を目的のところに移動
。。。
じゃあその二枚はどう移動させるか
- 上の一枚を移動
- 下の一枚を目的のところに移動
- 最初に移動した円盤を目的のところに移動
移動方法に法則が!!
これを式に表すと次のようになります。
前提条件
一枚分の移動コスト = 1 = move(1)
として、move(n)はn枚の円盤を移動コストとします。
二枚の場合
move(2) = move(1) + move(1) + move(1) = 3
三枚の場合
move(3) = move(2) + move(1) + move(2) = 7
四枚の場合
move(4) = move(3) + move(1) + move(3) = 15
となりました。先ほどのn乗を使うものよりもはるかに簡単です。
そしてこのようにある関数Aの値を出すためにその関数Aを使うようなアルゴリズムを再帰アルゴリズムといいます。
「ある関数Aの値を出すためにその関数Aを使うようなアルゴリズムを再帰アルゴリズムといいます」
一応二回言っといた笑
というわけで、次に n 回のハノイの塔を解くコードを書いていきます
実装(ruby)
def move(n) if n == 1 return 1 end return move(n-1) + move(1) + move(n-1) end puts move(1) puts move(2) puts move(3) puts move(4) puts move(5)
結果はこんな感じ
1 3 7 15 31
解説は短いので不要ですね。
単純に1の時は1を
それ以外のときはmove(n-1) + move(1) + move(n-1)
を返しています。
というわけで再帰アルゴリズムを使うといとも簡単に実装が出来るというものでした。
ただハノイの塔は例外ですが、大抵の場合繰り返しを使ったほうがマシンに負荷をかけないケースが多いようです。
フィボナッチや階乗なんかがその例。
ハノイの塔の一般項にべき乗というマシンに負荷がかかる演算が入っているから
再帰を用いてなるべく加算だけで行った方がよいということです。
負荷がかかりやすいのは
掛け算 > 足し算
なので。
同じようになるべく掛け算の回数を減らして計算量を小さくするアルゴリズムに高速フーリエ変換などがあります。これはいつか紹介したいですね。
それでは再帰アルゴリズムの紹介でした!!
