$ \DeclareMathOperator{\arccosh}{arccosh} \DeclareMathOperator{\arcsinh}{arcsinh} \DeclareMathOperator{\rank}{rank} \DeclareMathOperator{\rot}{rot} \DeclareMathOperator{\grad}{grad} \DeclareMathOperator{\diver}{div} $



一般化ハノイの塔

ハノイの塔は円盤(disk)の枚数を$n$とすると、柱(peg)の数が3本のときには$2^n$回の移動をすればとくことができるのは良く知られている事実です。 しかし、柱の本数を増やしたらどうなるのでしょうか?
柱の数が 3 本以上の場合の最短ステップ数を考察してみました。
(注意) 情報科学の授業のレポートとして提出したものを改変して記事にしています。 また、解答プログラムは Ruby プログラムとして提出したものを JavaScript に移植したものです。 従って繋がりがおかしなところや言い回しが変なところがあるかもしれませんがご容赦ください。
なお、アルゴリズムの解説は分かりにくい[1]と思いますが、自分でもこれで精一杯なので。 まぁ、プログラムを見て「おぉ!解けてる!!」と思ってくれれば結構です^^

[1]…というか分からない

1JavaScript プログラム

(おそらく)最短手順でハノイの塔を解くプログラムです。 あまり調子に乗って柱や円盤の数を多くするとブラウザが固まりますのでご注意ください。
DOM に対応したブラウザでご覧ください。 また JavaScript を有効化してください。 Mozilla Firefox 3 、 Opera 9 及び Internet Explorer 7 での動作を確認しました。

柱数 : NaN

円盤数 : NaN

ステップ数 : NaN / NaN

次へ もう一度

オート : ms

2一般化ハノイの塔のアルゴリズム

一般化ハノイの塔のアルゴリズムについて解説します。

2.1アルゴリズムの概要

3本のときは比較的簡単な分割統治で解けましたが、 一般化するとかなり難しくなるので以下ではそのアルゴリズムについて解説していきます。
なお一般化に際していくつかの注意点があります。

2.1.1最短手順について

インターネットで調べた最短の操作回数と、 本アルゴリズムの要する操作回数が完全に一致しているのでインターネットの情報 [1] が間違っていなければ最短です[2]

2.1.2手順の一意性について

pegが3本の時に最短で解こうとすると、手順は1通りに定まりますが、4本以上になると複数の解答が得られる可能性があります。 本アルゴリズムでも複数個の解を求められますが、それらが本当にすべての解かどうかは分かりません [3]

2.2最短手数の考察

最短手数をpeg数(npeg)とdisk数(ndisk)をいろいろと変えて実験してみると、以下の表のようになります。 ただし、$s=\text{npeg}-3$, $n=\text{ndisk}$としてあります。
表1 - 最短手数 (s=npeg-3, n=ndisk)
s\verb+\+n012345678910
001371531631272555111023
101359131725334149
201357111519232731
30135791317212529
さらにここで二項間の差をとってみます。 すると以下の表のようになります。
表2 - 最短手数の差
s\verb+\+n12345678910
01248163264128256512
11224448888
21222444444
31222244444
すると二項間の差により以下の表のようにグループ分けができることに気づきます。
最短手数(グループ分け)
左から順に、グループ0、グループ1、…と番号を振っていきます。 境界上の要素が左右どちらのグループに入るかの揺らぎがあるので、 これらが左のグループに入るようなグループ分けを「左寄りグループ」、 右のグループに入るようなグループ分けを「右寄りグループ」、 とそれぞれ名づけます。
ところでもう一度最短手数の差の表を見てもらうと、s(またはnpeg)が増加すると、 同じ数が続く場所が長くなっていきます。 そこで同じ数がいくつ続くのかを書き出してみたのが、以下の表です。
表3 - 最短手数の差 (数字がいくつ続くか)
s\verb+\+n12345
011111
112345
21361015
314102035
この数列は、パスカルの三角形(以下の図)を斜めに読んだものになっています。
パスカルの三角形(Wikipediaより)
従って、パスカルの三角形を用いれば最短手数は簡単に計算できることになります。

2.3最短アルゴリズム

それでは最短アルゴリズムを解説していきます。

2.3.1分割統治 - 3枚のときとのアナロジー

一般化する前に3枚の時(npeg=3, ndisk=n)にどうしていたのかを思い出すと、
  1. 上から(n-1)枚のdiskを何らかの方法で1番のpegに移す
  2. (n-1)番のdiskを2番のpegに移す
  3. (1)で移したdiskを2番のpegに何らかの方法で移す
でした。
3枚の時には何らかの方法の部分が再帰を使って簡単に書かれ、解くことができたのでした。
これを見習いつつ、一般の時(npeg=p, ndisk=n)にどうするかというと、
  1. 上から(n-1)枚のdiskを何らかの方法で1〜(p-2)番のpegに移す
  2. (n-1)番のdiskを(p-1)番のpegに移す
  3. (1)で移したdiskを(p-1)番のpegに何らかの方法で移す
とします。
さてここで問題なのは、何らかの方法という部分です。 最短でこの方法が実現されれば、それが最短のアルゴリズムだといえるのは明らかでしょう。
しかし3枚の時には移し先が1本しかなく、そこにすべて(0〜(n-2))のdiskを移せば良いので迷うところがありませんでした。 一般の場合には移し先が複数本になるので、どのようにdiskを移せばいいのか迷ってしまいます。

2.3.2問題の単純化 - 制約の付加

そこでどうするかというと、もう少し移し方に制約を加えて、
  • 1番の peg に$0\cdots(a_1-1)$番のdiskを、
  • 2番のpegに$a_1\cdots(a_2-1)$番のdiskを、
  • $\vdots$
  • (p-2)番のpegに$a_{p-3}\cdots(a_{p-2}-1)$番のdiskを、
それぞれ移すようにします(以下の図参照)。
ハノイの塔(npeg=5, ndisk=15)初期状態
ハノイの塔(npeg=5, ndisk=15)(2)の直前の状態
この制約の下で手順が最小になるようにしてみます [4]

2.3.3邪魔者をどける最短手順

それではq番のpegに0番のpegの、上からm枚を移す作業を考えます。
ハノイの塔(npeg=5, ndisk=15)上からm枚をq番のpegへ
この操作を行う直前ではすでに1番から(q-1)番のpegは、今から移したい板よりも小さなものが乗っているので使うことができません。
従ってこの操作は、npeg=n-(q-1)、ndisk=m [5] のハノイの塔問題と同じだと分かります。
これより分割(数列{$a_n$})を決めれば、その中での最短手順が分かるので、後はどのように分割{$a_n$}をとれば最短になるかを考えればいいことになります。

2.3.4分割のとり方

npeg=p, ndisk=nの右寄りグループが$g_r$、左寄りグループが$g_l$であることを、$(p, n, g_r, g_l)$と書くことにします。
すると各分割が、
$\begin{cases} (3, n_3, g_r^3, g_l^3) \\ (4, n_4, g_r^4, g_l^4) \\ \hspace{2em} \vdots \\ (p, n_p, g_r^p, g_l^p) \\ \end{cases}$
である時に、
  • $n_3 + n_4 + \dots + n_p = n-1$ (これは当然)
  • $i \in \{3, 4, \dots, p\}$に対し、$g_r^i=g_r-1 \ \text{or} \ g_l^i=g_r-1$
となるようにすれば良いと分かります。
少し分かりにくいので具体例で説明します。 以下の表を見てください。 ndisk=8、npeg=5(s=2)のとき(図では赤丸)を考えます。
分割のとり方 (npeg=5, ndisk=8での例 説明用)
さて、npeg=5、ndisk=8は左寄りグループも右寄りグループも2なので、 グループ1(表の青色の多角形で囲まれた部分)の中のうち各sから一つずつ要素をとってきて、 それらの要素のn値の合計が7(=ndisk-1)になるようにします。
従って、たとえば以下の表の赤丸の要素をとってくるとこの条件を満たします。
分割のとり方 (npeg=5, ndisk=8での例 #1)
つまり、0番のpegから上の2枚のdiskを1番のpegに、3枚を2番のpegに、2枚を3番のpegに、それぞれ移すようにすれば最短となることを表します。
移し終わると以下の図のようになります。
ハノイの塔(npeg=5, ndisk=8) (1)適用後
なおこの分割は一意的ではありません。 たとえばnpeg=5、ndisk=8の時には、分割のとり方 #1だけではなく、 以下の表のようなとり方でも最短となります。
分割のとり方 (npeg=5, ndisk=8での例 #2)

2.3.5そして再帰へ

以上の説明が、何らかの方法での部分の中核にあたる部分です。 どのpegに何枚のdiskを移せばいいのか分かったので、後は自己再帰をするだけで解けてしまいます。

[2]自力で証明できなかったので、そこはインターネットの情報を信頼することにします
[3]証明はしていませんが、おそらくすべてだと思います
[4]前にも挙げましたが、この制約を入れた上での最短手順が制約がない場合の最短手順と一致するかどうかは不明です。
[5]図の場合には、n=5, q=3, m=3ですから、npeg=3、ndisk=3の問題と同値で、その最低操作回数は良く知られたように$2^3-1=7$です。