本題は、ハノイの塔における円盤の最小移動回数を求めるもの。他のサイトと異なるところは、塔の本数が4以上であること。

円盤がN枚あり、塔がP本ある場合、円盤の最小移動回数を M(N,P) とする。MはMoveの意。

塔が3本ある場合の最小移動回数は、よく知られているように、M(N, 3) = 2N-1 で与えられる。つまり、円盤が1枚なら1回、2枚なら3回、3枚なら7回という具合に、指数的に増える。

さて、塔が4本に増えた場合に、どう考えれば良いだろう。

話しを判りやすくするため、塔に名前A, B, C, Dをつけ、円盤を上からの小さい順にa, b, c, d, … とする。スタート状態ではすべての円盤が塔Aに集まっていて、ゴール状態では塔Dに移動したとする。

円盤が1枚。移動回数は1回で済むので、考える意味がない。M(1,4) = 1。

円盤が2枚。円盤aを塔Bに移し、円盤bを塔Dに移動。最後に円盤aを塔BからDに移し、完成する。これで、計3回の移動で済む。M(2,4) = 3。
 ここで発想を変えてみる。 上記の過程では、円盤aは M(1,4)と同じ回数で塔Bに移したと考えてよさそう。塔Dと塔Bとの違いはあるものの、本質的には同一視と考えてよさそう。円盤bは塔B以外の塔A, C, Dの3本を使って移動したので、M(1,3)の移動と考える。最後にあった、円盤aが塔Bから塔Dへの移動回数も、M(1,4)と考えられる。つまり、
    M(2,4) = M(1,4) + M(1,3) + M(1,4) = M(1,3) + 2*M(1,4) = 1 + 2*1 = 3
という漸化式が成り立つ。

円盤が3枚。ここでは上の発想を応用してみる。円盤aをM(1,4)という回数で塔Bに移動し、残り2枚の円盤bとcはM(2,3)で塔Dに移動。最後に円盤aをM(1,4)をもって塔Dに移すので、移動回数は計
    M(1,4) + M(2,3) + M(1,4) = M(2,3) + 2*M(1,4) = 3 + 2*1 = 5
になる。しかしこれでは最小移動回数であるかどうかは不明なので、円盤aとbをM(2,4)で塔Bに移し、円盤cをM(1,3)で塔Dに移し、最後に塔Bにある円盤aとbを塔Dに移してみる。この場合の移動回数は、
    M(2,4) + M(1,3) + M(2,4) = M(1,3) + 2*M(2,3) = 1 + 2*3 = 7
になる。ということで、一般的に、
    M(3,4) = min( M(2,3)+2*M(1,4), M(1,3)+2*M(2,3) ) = min(5,7) = 5
つまり、上から一枚ずつ増やした時の移動回数の中から、最小移動回数のものを使えばよい。

飛躍があるかもしれないが、一般式はつぎになるだろう。

<ハノイの塔における最小移動回数 M(N, P)>
  N: 塔の本数(3以上の整数)。 P: 円盤の数(1以上の整数)。
  M(N,1) = 1   M(N,P) = min ( M(K,P-1) + 2*M(N-K,P )  (N > 3、P > 1、K = 1,2,...,N-1)
ただし、min は最小値の意味。  初期条件: すべてのNに対し、M(N, 3) = 2N-1

上の例でもう一度検証してみる。
   M(1,4) = 1
   M(2,4) = M(1,3)+2*M(1,4) = 1+2 = 3
   M(3,4) = min { M(2,3)+2*M(1,4), M(1,3)+2*M(2,4) }
      = min { 3+2*1, 1+2*3 } = min {5, 7} = 5
   M(4,4) = min { M(3,3)+2*M(1,4), M(2,3)+2*M(2,4), M(1,3)+2*M(3,4) }
      = min { 7+2*1, 3+2*3, 1+2*5 } = min {9, 9, 11} = 9
   M(5,4) = min { M(4,3)+2*M(1,4), M(3,3)+2*M(2,4), M(2,3)+2*M(3,4), M(1,3)+2*M(4,4) }
      = min { 15+2*1, 7+2*3, 3+2*5, 1+2*9 } = min {17, 13, 13, 19} = 13
再帰的に計算してゆけばOK。

ついでに、いくつかの計算結果を書いておく。
 円盤の枚数=100、塔の本数=10 の場合の最小移動回数は 601。
 円盤の枚数=100、塔の本数=20 の場合の最小移動回数は 361。
 円盤の枚数=200、塔の本数=4 の場合の最小移動回数は 14680065。天文数字にならない。
 円盤の枚数=200、塔の本数=20 の場合の最小移動回数は 801。思ったほど少ないかな。

<追加>
塔の本数が4本の場合では、最小移動回数はと円盤の枚数との関係は以下になる。
  円盤の枚数   0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, …
  最小移動回数 0, 1, 3, 5, 9, 13, 17, 25, 33, 41, 49, 65, 81, 97, 113, 129, 161, …
  前後の差     1, 2, 2, 4, 4, 4, 8, 8, 8, 8, 16, 16, 16, 16, 16, 32,
規則的に増加していく。

塔の本数が5本の場合では、最小移動回数はと円盤の枚数との関係は以下になる。
  円盤の枚数   0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, …
  最小移動回数 0, 1, 3, 5, 7, 11, 15, 19, 23, 27, 31, 39, 47, 55, 63, 71, 79, 87, …
  前後の差     1, 2, 2, 2, 4, 4, 4, 4, 4, 4, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 16,
  つまり、     1が1個、2が3個、4が6個、8が10個、16が15個、32が21個と並んでいき、
  前後の差         2    3     4      5     6
規則的に増加していく。

<オリジナル問題>
 ハノイ塔の本数をP (4 <= p <= 50> 、円盤数をN (0 <= N <= 10000) としたときの、円盤の最小移動回数を表示せよ。
 計算制限時間 10秒。
</オリジナル問題>

<メモ> 
本題の漸化式は ACM問題 #10444 Multi-Peg Towers of Hanoi を解くために導いたもの。
 参考になるかもしれないので、#10444の解答プログラムを付しておく。

<ハノイ塔の最小移動回数を算出するプログラム> hanoi.c
 円盤枚数 0~200、塔の本数 4~20 がプログラムの入力条件。

Comments are closed.

Post Navigation