Aritalab:Lecture/Algorithm/Towers of Hanoi

ハノイの塔

(フランスの数学者 エドゥアール リュカ によるパズル, 1883)

台の上に３本の棒が固定されていて、一番左の棒をＡ、真ん中の棒をＢ、一番右の棒をＣとします。Ａにはn枚の円盤がはまっており、円盤は下へいくほど半径が大きくなっています。次のルールに従い、棒Ｂを利用して全ての円盤をＡからＣに移すとき、何回の移動が必要になるでしょうか。

• 一回に一枚の円盤しか動かしてはいけない。
• 常に大きい方の円盤が下になるようにする。（移動の途中で円盤の大小を逆に積んではいけない。）

必要な手数

この問題を解くには漸化式（ぜんかしき）を使います。

解

n (>0) 枚の円盤を移動する手数を T_n と書きます。上から n - 1 枚の円盤をまず B の棒に移し、一番大きい円盤を C に移してから、B にある n - 1 枚をもう一度全て C に移せばよいので、以下の漸化式を得ます。

• T₀ = 0
• T_n+1 = 2 T_n + 1 (n > 0)

実際に

• 1 枚の円盤があるとき T₁ = 1 回、
• 2 枚の円盤があるとき T₂ = 2 + 1 = 3 回、
• 3 枚の円盤があるとき T₃ = 3 * 2 + 1 = 7 回
• 4 枚の円盤があるとき T₃ = 7 * 2 + 1 = 15 回
• 5 枚の円盤があるとき T₃ = 15 * 2 + 1 = 31 回

の移動が必要なことを確認しましょう。

手数の解法

必要な移動の数に 1 を足すと、2, 4, 6, 8, 16, 32 のように 2 の階乗から 1 を引いた数になっています。だから答えは 2ⁿ - 1 です。これを数式を用いて解いてみましょう。

手数を計算するテクニックとして S_n = T_n/2ⁿ とおきます。

• S₀ = 0
• S_n+1 = S_n + 2^-(n+1) (n > 0)

この式は

• 1 枚の円盤があるとき S₁ = 1 / 2
• 2 枚の円盤があるとき S₂ = 3 / 2² = 3/4
• 3 枚の円盤があるとき S₃ = 7 / 2³ = 7/8

となっています。分母が分子よりも常に大きいので 1 より少し小さい数です。続けていくと、規則性がわかります。

• 4 枚の円盤があるとき S₄ = 15 / 2⁴ = 15/16
• 5 枚の円盤があるとき S₅ = 31 / 2⁵ = 31/32

分子は分母の数よりちょうど 1 だけ小さい数です。これを数学的に解くには等比数列の和の公式を利用します。

S_n = 2^-1 + 2^-2 + ... 2^-n

= 2^-1(1 + 1/2 + 1/4 + 1/8 ... 2^-(n-1))

= 2^-1(1 - 2^-n) / ( 1 - 1/2 ) = 1 - 2^-n

元々の漸化式との関係を使うと T_n = 2ⁿS_n = 2ⁿ-1 となります。 上の円盤の動かし方をよくみても、これが円盤を動かすのに最低限必要な手数であることがわかります。 つまりこの数より少ない回数で円盤を動かすことはできません。

まとめると、 n 枚の円盤を動かすのに最低限必要な手数は 2ⁿ-1 、つまり n に対して指数的に増加していくことがわかりました。問題のサイズ (つまり n ) が大きくなると、かかる時間は急速に増えていきます。

教訓

パズルでも規模が大きくなると急速に（指数的に）時間を要する、つまり難しくなる問題があります。

ハノイの塔の場合、 8 枚の円盤が棒にささっていると最短の手数で移動させても 2⁸ - 1 = 255 手が必要です。 20 枚の円盤が棒にささっている場合、最短の手数でも 1,048,576 手です。つまり 1 秒に一枚動かしても 12 日以上かかります。ウェブ上で画像を検索すると、多くのパズルは7枚か8枚の円盤があるようです。枚数がこれ以上の場合、挑戦しないほうが時間を有効に使えそうです。