これは2006年冬のプログラミングシンポジウムの
GPCCの会議で出た「棒の本数が4本以上のハノイの塔はどうなるのだろう」という疑問について、
1月15日に走り書きして放置していた結果(
西尾泰和の日記(2006-01-16)
)を清書したものです。
ハノイの塔問題を知らない方は
ハノイの塔 - Wikipedia
を参考にしてください。
従来のハノイの塔問題では、棒の数は3本でした。
この場合、板が1枚ならば1手で動かせますが、
2枚の場合は1枚目を脇にどけて2枚目を動かし1枚目を2枚目の上に戻す、
という3手がかかります。
これを、板の枚数2とスタートとゴールをのぞいた
「一時待避用の棒」の本数1とを用いて
「hanoi(2, 1) == 3」と表現します。
また、この待避用の棒が1本あることを
「スペースが1個ある」と表現します。
スペースが1個のハノイの塔問題に関しては
「hanoi(n, 1) = 2 * hanoi(n - 1, 1) + 1」
が正の整数nに付いて成り立つことが知られています。
スペースが2以上の場合には、いったいどういう規則性があるのか、
それを確かめてみました。
スペースが1個の場合の最小手数は、板の枚数が0枚の時の0手から順に
0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, ...
となります。
スペースが2個の場合、3個の場合の最小手数は、
0, 1, 3, 5, 9, 13, 17, 25, 33, 41, 49, 65, 81, 97, 113, 129, ...
0, 1, 3, 5, 7, 11, 15, 19, 23, 27, 31, 39, 47, 55, 63, 71, ...
となります。
この数列の隣り合う項の差を取る(階差数列)と、それぞれ
1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, ...
1, 2, 2, 4, 4, 4, 8, 8, 8, 8, 16, 16, 16, 16, 16, ...
1, 2, 2, 2, 4, 4, 4, 4, 4, 4, 8, 8, 8, 8, 8, ...
同じ数がいくつ続くかを新たな数列にすると、スペースが1個、2個、3個の場合にそれぞれ
1: 1, 1, 1, 1, 1, ...
2: 1, 2, 3, 4, 5, ...
3: 1, 3, 6, 10, 15, ...
となります。
また、この数列の列はパスカルの三角形を45度回転して斜めに読んだものです。
(
パスカルの三角形 - Wikipedia)
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
スペースが3個の場合の数列は三角数と呼ばれるものです。
(
三角数 - Wikipedia)
つまり、スペースがm個のハノイの塔の最小手数の数列の階差数列は、
m次元の三角形を用意して、
0段目には1、1段目には2、k段目には2
kと書き、
小さい順に読みあげたものだと考えられます。スペースが0個のハノイの塔で
1枚しか移動できないのは、0次元の三角形(つまり点)になってしまうからです。
ひとたび規則性がわかってしまうと、その規則性が何に由来するものなのかも想像しやすくなります。階差数列が2になっているのは、1枚板を増やしたときに最小手数が2増えるということです。2はスペースがmの時にm個続くのですが、これはつまりm個スペースがあれば、m枚までの板は積み重ねずに平たくスペースに並べられることによります。そして4が続く領域では「一度小さい板を空いているスペースに置いた後、大きい板を別のスペースに置き、スペースが足りなくなったので小さい板を大きい板の上に移動する」という作業が行われています。この時、スペースがm個なら、最初に平たく置くことができたm枚のうち、小さい方のm-1枚は一番大きい板に乗せることができ、残ったスペースはm-1個になります。これが繰り返されることで三角数が現れるわけです。上のストーリーでは横方向が三角数になることに注目していましたが、実は縦方向が三角数になるということの方が根源的なのかも知れません。
以下はソースコードとその説明です。
# -*- coding: cp932 -*-
#
# ハノイの塔の一般化
#
class CInfinity:
def __cmp__(self, v):
return 1
INFINITY = CInfinity()
def divide(x, y):
if y == 1:
yield (x, None)
else:
for i in range(1, x):
for j in divide(x - i, y - 1):
yield (i, j)
cache = {}
def hanoi(numPlate, numSpace):
if numPlate == 0:
return 0
if numPlate == 1:
return 1
if numSpace >= numPlate - 1:
return numPlate * 2 - 1
if cache.has_key((numPlate, numSpace)):
return cache[(numPlate, numSpace)]
minHand = INFINITY
for d in divide(numPlate - 1, numSpace):
numHand = 0
for i in range(numSpace):
v = hanoi(d[0], numSpace - i)
numHand += v
d = d[1]
if numHand < minHand:
minHand = numHand
result = minHand * 2 + 1
cache[(numPlate, numSpace)] = result
return result
result = [hanoi(n, 2) for n in range(100)]
print result
print [result[n + 1] - result[n] for n in range(99)]
最初のCInfinityは単なる無限大の定義です。
かわりに「十分大きな数」を入れても問題ありません。
次の関数devideはx個のものをy個にわける方法を列挙する関数です。
例えば5個のものを3個にわける方法を列挙させると以下のようになります。
>>> for d in divide(5, 3):
print d
(1, (1, (3, None)))
(1, (2, (2, None)))
(1, (3, (1, None)))
(2, (1, (2, None)))
(2, (2, (1, None)))
(3, (1, (1, None)))
関数hanoiはnumPlate枚の板とnumSpace個のスペースがある場合の最小手数を返す関数です。
板が0枚の時は0手、1枚の時は1手です。
n枚でn - 1個以上のスペースがある場合は、
上からn - 1枚の板をそのスペースに待避させ(n - 1手)、n枚目の板を移動し、
待避させた板を順に元に戻す(n - 1手)だけでよいので、
最小手数は2 * n - 1手になります。
その次のif文は、
結果がすでに計算されている場合には計算し直さずにその結果を再利用しているだけです。
その先の10行程度が肝心の計算を行う部分です。
スペースが1個のハノイの塔では、for文などを使いませんでした。
それは1つに分割する方法が1通りだからです。
例えば6枚と2つのスペースのハノイの塔では、6枚目を動かすために5枚を待避させる際に、
何枚を1つめのスペースに移動し、何枚を2つめのスペースに移動するかで、
4通りの可能性があります。
また、2枚と3枚にわけるのと、3枚と2枚にわけるのでは意味が違います。
前者の場合、スペース2個を利用して2枚を移動するのに3手かかり、
次にスペース1個を利用して3枚を移動するのに7手かかります。
後者の場合は、スペース2個を利用して3枚移動するのに5手で済むので、
残り2枚の移動にかかる3手を加えても2手少なくなります。
6枚を2個のスペースを使って移動する際の最小手数を求めるためには、
全ての5を2つ(d1, d2)にわける方法の中で
「hanoi(d1, 2) + hanoi(d2, 1)」が最小となる数を求める必要があります。
スペースが3つの場合には3つに分割する必要があるので、
2つ目のfor文で手数の計算を一般化しています。
後は0以上100未満のnに付いてhanoi(n, 2)を計算すると、
スペースが2個の場合の最小手数の数列が得られます。
最後の3行では、その数列と、階差数列とを表示しています。
なお、このプログラムはPythonという言語で書かれています。
スペースが3つで板が0枚から99枚までの場合について計算するのには
4秒程度の時間がかかります。
スペースがもっと多い場合について検証する際にはご注意下さい。
