ハノイの塔

ハノイの塔

　ハノイの塔は1883年にフランスのＥ．Lucas（リュカ）が考案したゲームと言われています。著書『数学遊戯』の中にあるそうです。　

　これは次のようなゲームです。

hanoi

例　３枚の円盤の場合（ｎ＝３）

　台の上に３本の棒A，B，Cが固定されていて，棒Ａにｎ枚の円盤が棒を通して重ねられています。円盤は下へいくほど半径が大きくなっています。

　このとき，次の規則に従って，円盤をＡからBに移動してください。

一回に一枚の円盤しか動かしてはいけません。
移動の途中で円盤の大小を逆に積んではいけません。常に大きい方の円盤が下になるようにして下さい。
棒A，B，C以外のところに円盤を置いてはいけません。

　このゲームは元々手で実際にやるものですし，実際に玩具としてこのようなものがあるそうです。しかしここではこれをプログラミングの問題，即ち，解く手順をコンピュータを使って求める問題としましょう。

　プログラミングの問題としてはこのハノイの塔は再帰を使う典型例として有名なものです。

　上の図にある３枚の円盤の場合を，実際に解くことは比較的簡単に思いつきます。しかし一般的に適用できるアルゴリズムを見つけるのは中々難しそうに見えます。実際，非再帰のプログラミング技法で解こうとすると大変難しい問題になります。

　しかし，再帰を使うと以下のように驚くべき簡単なものとして実現できます。

Sub  Hanoi(n,A$,B$,C$)
   If n>0 then
      Call Hanoi(n-1,A$,C$,B$)
      Print n;"番の円盤を";A$;"から";B$;"へ移動"
      Call Hanoi(n-1,C$,B$,A$)
   End if
End Sub

　説明をしましょう。アイデアは単純です。

　円盤が２枚の場合を考えてみましょう。上から１，２と円盤に番号をつけます。この場合，AからBへの移動は次のようにして実現出来ます。

(ア) 　１をAからCへ移動
(イ) 　２をAからBへ移動
(ウ) 　１をCからBへ移動

です。

　さて一般の場合を考えます。その操作が出来たとして，その操作を Hanoi(n,A$,B$,C$) と表します。これはn枚の円盤をA$からB$にC$を補助的に使って移動するという操作です。

　一般の場合，１からｎ－１の円盤を１纏まりとして考えて，それを１つの円盤と見ます。そうすると，２つの場合と同じ状況になります。このとき，(ア) に対応する操作はHanoi(n-1,A$,C$,B$)です。そして，(イ) はｎ番の円盤をAからBへ移動します。(ウ) は１纏まりとみた円盤をCからBへ移動しますから，Hanoi(n-1,C$,B$,A$)です。

　これを再帰的プログラムにしたのが，上のHanoi です。これで終わりです！

Hanoi の塔の証明

　「プログラムとは」の項で

良いプログラマは正しいプログラムを書くだけでなく，

それが正しく動作することを分かりやすく証明する必要がある

ということを書きました。その標語に従って上のプログラムが正しく動作すること証明しましょう。いつもの通り，説明のため行番号を付けます。

01  Sub  Hanoi(n,A$,B$,C$)
02     If n>0 then
03        Call Hanoi(n-1,A$,C$,B$)
04        Print n;"番の円盤を";A$;"から";B$;"へ移動"
05        Call Hanoi(n-1,C$,B$,A$)
06     End if
07  End Sub

　ここでHanoi(n,A$,B$,C$) という操作の意味を正確にしておく必要があります。

この操作は1～nまで順に積まれたn枚の円盤をA$からB$に移動する操作。
操作開始時，A$には1～nまで順に積まれたn個の円盤がある。
操作終了後，B$には1～nまで順に円盤が積まれたものになる。
その際，C$を補助的に使っても良い。
さらに，この操作はゲームの規則(1),(2),(3) を満たしている。
またn+1 以上の円盤があっても，この操作はそれに関係なく行われる。

　証明は数学的帰納法を使うのが適当です。

n=0 の場合は，2行の条件を満たしませんから，Hanoi(n,A$,C$,B$) は何もしない操作になります。
n=1 の場合。
n=1 の場合，3～4行が実行されますが，3，5行は Hanoi(0,A$,C$,B$)，Hanoi(0,C$,B$,A$) で何も実行しません。つまり，この場合は，4行だけ実行されます。従って，1番の円盤をA$からB$へ移動と言う操作で，この場合正しい操作になっています。
n-1 のとき，Hanoi が正しい操作を行っていると仮定します。このとき　nの場合正しい操作になることを示します。

　まず，開始時 A$ には1～nまで順に積まれたn枚の円盤があります。

　そこで，3行で，Hanoi(n-1,A$,C$,B$)を呼びます。このとき，A$ には1～nまでの円盤がありますから，この操作は可能です。ここで Hanoi は n-1 の時は正しい操作をすると言う仮定から，3行の結果，1～n-1までの円盤が規則(1),(2),(3) を満たしながらC$に移動します。
　この過程で1～n-1以外の円盤の上に乗せることもありますが，あったとしても，それは n 以上のものです。従って規則(2)を満たします。

　次に，4行でn番の円盤をA$からB$へ移動します。今 1～n-1までの円盤は C$ にありますから，B$に円盤があるとしてもそれはn+1番以上の円盤です。従って，nの円盤をB$に移動しても規則(2)を満たします。

　最後に，5行でHanoi(n-1,C$,B$,A$)を呼びます。これは先ほど移動した，1～n-1の円盤を C$ から B$ に移動するものです。これもHanoi は n-1 の時は正しい操作をすると言う仮定から，正しく動作し，規則(2)を満たします。

　以上から，nの場合も正しい操作になります。

Hanoi の塔での移動回数

　ハノイの塔の解法プログラム Hanoi での移動の回数を計算してみましょう。移動の回数を H(n) と表します。

Hanoi(n,A$,B$,C$)は3,4,5行で移動を出力しますが，3行は H(n-1) 回の移動，4行は 1回の移動， 5行はH(n-1)回の移動を出力します。従って，

H(1)=1, n >1 のとき，H(n)=H(n-1)+1+H(n-1)=2*H(n-1)+1

となります。この漸化式は，

H(1)=1, n>1 のとき， (H(n)+1)=2*(H(n-1)+1)

と書けますから，H(n)+1 = 2ⁿ です。故に，

H(n)=2ⁿ-1

となります。

　この数値はかなり大きなものです。例えば，H(10)=1023ですし，H(40)=1099511627775となります。

ハノイの塔の解法 Hanoi は最良か？

　プログラム Hanoi でハノイの塔の問題の解が得られることは分かりました。しかしその解法は n が大きくなるにつれて膨大な移動回数になります。

　もっと良い方法は無いのでしょうか。しかし，実は

ハノイの塔の解法は Hanoi が使ったアルゴリズムが最良

なのです。次にその証明をしてみましょう。

　最良の移動法を与えるアルゴリズムをHanoiBest(n) という名前を付けましょう。これはn枚の円盤についてのハノイの塔の最良アルゴリズムを与えるものとします。このアルゴリズムを使って実際にハノイの塔を考えて見ます。

　どのようなアルゴリズムを使っても，n番目の円盤をAからBへ移動しなくてはなりません。このとき，Bの棒には，n 以下の番号の円盤はあってはいけません。従って，このとき，1～n-1番目までの円盤は C にないといけません。従って，この時点で，HanoiBest(n) の中には HanoiBest(n-1) が少なくとも一回含まれないといけません。更に，n番目の円盤をAからBへ移動した後，Cにある1～n-1の円盤を戻さないといけませんから，その後で少なくとも，もう一回HanoiBest(n-1)を含む必要があります。従って，

HanoiBest(n) の中にはHanoiBest(n-1)を２回と１回の移動が含まれます。

そこで，HanoiBest(n) が出力する移動の回数を HB(n) と表すと，今のことから，

HB(n) ≧２＊HB(n-1) + 1

が得られます。明らかに， HB(1)=1 ですから，Hanoi で使った H(n) と比較すると，上の式ですべて等号が成立するのが H(n) ですから，

HB(n) ≧ H(n)

が得られます。従って，HanoiBest が最良であると言うことから，HB(n)=H(n) となります。即ち，

Hanoi が出力する移動の回数が最良

と言うことになります。

　最後に，Hanoi をTiny Basic での実行するための補足をします。

　Tiny Basic のプログラムとして実行する場合は，Hanoi を call して下さい。例えば次がn=5 の場合の完全なプログラムです。

Call Hanoi(5,"A","B","C")
End
Sub  Hanoi(n,A$,B$,C$)
   If n>0 then
      Call Hanoi(n-1,A$,C$,B$)
      Print n;"番の円盤を";A$;"から";B$;"へ移動"
      Call Hanoi(n-1,C$,B$,A$)
   End if
End Sub