ハノイの塔における最短経路の性質

ハノイの塔の状態と、それを表す文字列を同一視し、状態 \(X\) に対して、円盤 \(k\) が位置する杭を \(X_k\) と表します。 また、円盤 \(1, \ldots, k-1\) のみを考えた \(k-1\) 枚の円盤からなるハノイの塔の状態を \(X_{< k}\) と表します。

状態 \(X\) から状態 \(Y\) への最小操作回数を \(d(X,Y)\) とします。 \(d(X,Y)\) について、いくつかの性質を示します。

\(X\) がすべての円盤が同じ杭 \(x\) にある状態であるとき、\(d(X,Y)\) を \(d(x,Y)\) と表すことにします。 さらに、\(Y\) もすべての円盤が同じ杭 \(y\) にある状態であるとき、\(d(X,Y)\) を \(d_N(x,y)\) と表します。このとき、以下が成り立ちます。

\(d(x,Y) \leq 2^N-1\) であり、操作回数 \(d(x,Y)\) を達成する手順は \(1\) 通りである。 また、\(x \neq y\) ならば、\(d_N(x,y)=2^N-1\) である。

証明

\(2\) つの主張を同時に \(N\) に関する帰納法で示します。 \(N=1\) のときは、どちらも自明です。 以下、\(N>1\) とし、\(N-1\) 枚の円盤について両方の主張が成り立つと仮定します。

まず、\(d(x,Y)\leq 2^N-1\) を示します。

\(Y_N=x\) ならば、円盤 \(N\) を動かさず、円盤 \(1,\ldots,N-1\) のみを操作することで、帰納法の仮定より高々 \(2^{N-1}-1\) 回で到達できます。

\(Y_N\neq x\) ならば、以下の手順を用います。

• 円盤 \(1,\ldots,N-1\) を杭 \(z \ (z\neq x,Y_N)\) に移す。
• 円盤 \(N\) を杭 \(Y_N\) に移す。
• 円盤 \(1,\ldots,N-1\) を状態 \(Y_{<N}\) にする。

帰納法の仮定より、この手順の操作回数は高々

\[(2^{N-1}-1)+1+(2^{N-1}-1)=2^N-1\]

回です。したがって、どちらの場合も \(d(x,Y)\leq 2^N-1\) が成り立ちます。

次に、最適な手順では円盤 \(N\) を高々 \(1\) 回しか動かさないことを示します。 最適な手順で円盤 \(N\) を \(2\) 回以上動かすと仮定します。

初めの \(2\) 回の移動で円盤 \(N\) が杭 \(x\) に戻る場合、その間の小さい円盤の移動はそのまま実行し、円盤 \(N\) の \(2\) 回の移動だけを取り除くことで手順を短縮できます。 これは最適性に反します。

したがって、初めの \(2\) 回の移動で杭 \(x\) に戻らない場合だけを考えればよく、この場合は以下の操作が必要になります。

• 円盤 \(1,\ldots,N-1\) をある杭 \(a \ (a\neq x)\) に移す。
• 円盤 \(N\) を杭 \(x,a\) と異なる杭に移す。
• 円盤 \(1,\ldots,N-1\) を杭 \(x\) に移す。
• 円盤 \(N\) を杭 \(a\) に移す。

帰納法の仮定より、この時点までに必要な操作回数は少なくとも

\[d_{N-1}(x,a)+1+d_{N-1}(a,x)+1=(2^{N-1}-1)+1+(2^{N-1}-1)+1=2^N\]

回です。 これは \(d(x,Y)\leq 2^N-1\) に反するため、最適な手順では円盤 \(N\) を動かす回数は \(1\) 回以下です。

\(Y_N=x\) ならば、円盤 \(N\) は動かさないため、円盤 \(N-1\) までの問題に帰着されます。 帰納法の仮定より、最適な手順は \(1\) 通りです。

\(Y_N\neq x\) ならば、円盤 \(N\) はちょうど \(1\) 回動かすため、最適な手順は先ほど挙げた手順に限られます。 帰納法の仮定より、その前後で円盤 \(1,\ldots,N-1\) を移動する最適な手順はそれぞれ \(1\) 通りなので、全体の最適な手順も \(1\) 通りです。

これで \(1\) つ目の主張が示されました。

最後に、\(Y\) のすべての円盤が杭 \(y \ (y\neq x)\) にある場合を考えます。 最適な手順は、杭 \(z \ (z\neq x,y)\) を用いて以下のようになります。

• 円盤 \(1,\ldots,N-1\) を杭 \(z\) に移す。
• 円盤 \(N\) を杭 \(y\) に移す。
• 円盤 \(1,\ldots,N-1\) を杭 \(y\) に移す。

帰納法の仮定より、操作回数は

\[d_N(x,y)=d_{N-1}(x,z)+1+d_{N-1}(z,y)=2(2^{N-1}-1)+1=2^N-1\]

となります。 これで \(2\) つ目の主張も示され、帰納法が完成しました。

次に、一般の \(X\) の場合を考えます。

\(X_N = Y_N\) ならば \(d(X,Y)\) を達成する手順において円盤 \(N\) は移動しない。

証明

\(a = X_N\) とおきます。 円盤 \(N\) が移動すると仮定します。 円盤 \(N\) が \(a \to b \to a\) のように移動する場合は明らかに無駄なので、\(a \to b \to c \to a\) のように移動する場合を考えればよいです。 このとき、少なくとも以下の手順を踏む必要があります。

• 円盤 \(1, \ldots, N-1\) を杭 \(c\) に移す。
• 円盤 \(N\) を杭 \(a\) から杭 \(b\) に移す。
• 円盤 \(1, \ldots, N-1\) を杭 \(a\) に移す。
• 円盤 \(N\) を杭 \(b\) から杭 \(c\) に移す。
• 円盤 \(1, \ldots, N-1\) を杭 \(b\) に移す。
• 円盤 \(N\) を杭 \(c\) から杭 \(a\) に移す。
• 円盤 \(1, \ldots, N-1\) を状態 \(Y_{< N}\) にする。

このとき、操作回数は最低でも \(1 + d_{N-1}(c,a) + 1 + d_{N-1}(a,b) + 1\) 回かかります。 \(d_{N-1}(c,a) = d_{N-1}(a,b) = 2^{N-1}-1\) であるため、最低でも \(2(2^{N-1}-1) + 3 = 2^N+1\) 回以上かかることになります。 一方で、円盤 \(N\) を動かさず、円盤 \(N-1\) 以下を \(X_{< N}\) から \(Y_{< N}\) の状態へ直接操作することを考えます。 この場合、円盤 \(1,\ldots,N-1\) をいったんすべて同じ杭に集めてから状態 \(Y_{<N}\) にすることで、前述の性質と操作の可逆性より、高々 \(2(2^{N-1}-1)=2^N-2\) 回で到達できます。したがって、円盤 \(N\) を移動する手順が最適になることはありません。

この性質によって、\(X_k \neq Y_k\) なる最大の \(k\) をとれば、円盤 \(1,\ldots,k\) のみを考慮すればよいことになります。

\(X_N \neq Y_N\) とし、\(X_N, Y_N\) と異なる杭を杭 \(z\) とするとき、操作回数 \(d(X,Y)\) を達成する手順は以下のいずれか（または両方）である。

• パターン \(1\)
  • 円盤 \(1, \ldots, N-1\) を杭 \(z\) に移す。
  • 円盤 \(N\) を杭 \(Y_N\) に移す。
  • 円盤 \(1, \ldots, N-1\) を状態 \(Y_{<N}\) にする。
• パターン \(2\)
  • 円盤 \(1, \ldots, N-1\) を杭 \(Y_N\) に移す。
  • 円盤 \(N\) を杭 \(z\) に移す。
  • 円盤 \(1, \ldots, N-1\) を杭 \(X_N\) に移す。
  • 円盤 \(N\) を杭 \(Y_N\) に移す。
  • 円盤 \(1, \ldots, N-1\) を状態 \(Y_{<N}\) にする。

証明

円盤 \(N\) を動かす回数が \(1\) 回、\(2\) 回のとき、それぞれパターン \(1\)、パターン \(2\) が最適になることは明らかです。 よって、円盤 \(N\) を \(3\) 回以上動かすことがないことを示せばよいです。 前述の性質の証明と同様に、円盤 \(N\) を \(a \to b \to c \to a \to \cdots\) のように移動する場合を考えればよく、この時の操作回数は \(2^N+1\) 回以上です。 一方で、パターン \(1\) の操作回数は \(d(X_{< N}, z) + 1 + d(z, Y_{< N})\) 回であり、\(2^N-1\) 回以下です。 したがって、円盤 \(N\) を \(3\) 回以上動かす手順が最適になることはありません。

\(d(X,Y)\) を達成する操作手順がちょうど \(2\) 通りとなる条件は、パターン \(1\) とパターン \(2\) の操作回数が等しくなることであるため、以下のようになります。 （ここでは \(X_k \neq Y_k\) なる最大の整数を \(k\) とし、\(X_k, Y_k\) と異なる杭を杭 \(z\) としています。）

\[ d(X_{< k}, z) + 1 + d(Y_{< k}, z) = d(X_{< k}, Y_k) + 1 + d_{k-1}(X_k, Y_k) + 1 + d(Y_{< k}, X_k) \]

対称性より、\(d(z, Y_{< k}) = d(Y_{< k}, z)\) および \(d(X_k, Y_{< k}) = d(Y_{< k}, X_k)\) であることを用いています。

\(d_{k-1}(X_k, Y_k) = 2^{k-1}-1\) に注意して式を整理すると、以下のようになります。

\[(d(X_{< k}, Y_k) - d(X_{< k}, z)) + (d(Y_{< k}, X_k) - d(Y_{< k}, z)) + 2^{k-1} = 0\]

ここで、\(\Delta(X, p, q) = d(X, q) - d(X, p) \ (p \neq q)\) と定義します。 \(d\) の再帰的な性質を考えると、\(\Delta\) は以下の式を満たすことがわかります。

\[\Delta(X_{< m + 1}, p, q) = C(X_m, p, q) 2^{m-1} + \Delta(X_{< m}, p', q')\]

このとき、各変数は以下の通りです。

• \(C(x, p, q)\) は、\(x = p\) なら \(1\)、\(x = q\) なら \(-1\)、\(x \neq p,q\) なら \(0\) となるコストの差分です。
• 新しいターゲット \((p', q')\) は、\(x\) の値に応じて一意に決まります。具体的には、\(p'\)は以下のようになります。（\(q'\) についても同様です。）
  • \(x = p\) のとき、\(p' = p\)
  • \(x \neq p\) のとき、\(p'\) は \(x, p\) と異なる杭

これを繰り返すことで、\(\Delta(X_{< k}, z, Y_k) + \Delta(Y_{< k}, z, X_k) + 2^{k-1}\) は次のように \(2\) のべき乗の和で表せます。

\[\Delta(X_{< k}, z, Y_k) + \Delta(Y_{< k}, z, X_k) + 2^{k-1} = 2^{k-1} + \sum_{m=1}^{k-1} c_m 2^{m-1}\]

ただし、\(c_m = C(X_m, p_m, q_m) + C(Y_m, r_m, s_m) \in \{-2, -1, 0, 1, 2\}\) です。

桁DPによる数え上げ

\(2^{k-1} + \displaystyle\sum_{m=1}^{k-1} c_m 2^{m-1} = 0\) となるような文字列 \(X, Y\) の組み合わせを数え上げます。 円盤のサイズが大きい方から小さい方（\(k-1\) から \(1\)）へ向かって、\(V = 2^{k-i} + \displaystyle\sum_{m=i}^{k-1} c_m 2^{m-i}\) を管理する桁DPを行います。 \(V\) は初期状態で \(V = 1\) であり、各ビット \(m\) において以下の更新を行います。

\[V_{next} = 2V + c_m\]

最終的に \(m=1\) を終えたときに \(V=0\) となることが目標です。 \(c_m \in \{-2, -1, 0, 1, 2\}\) であるため、途中で \(V \notin \{-1, 0, 1\}\) となってしまった場合、それ以降どのように遷移しても \(V=0\) に戻ることはありません。 したがって、\(V\) の状態としては \(\{-1, 0, 1\}\) の \(3\) 通りだけを持てば十分です。

DPの具体的な状態は以下のようになります。

\(\mathrm{dp}[x][y][V]\)

• \(x\) : \(X\) 側のターゲットのペア（\(6\) 通り）
• \(y\) : \(Y\) 側のターゲットのペア（\(6\) 通り）
• \(V\) : 現在の差分 \(V \in \{-1, 0, 1\}\) （\(3\) 通り）

まだ \(X_k \neq Y_k\) となる円盤が見つかっていない状態の数 \(c\) を管理し、\(N\) から \(1\) へ向かって文字列を走査しながら、以下のように更新します。

• \(A_m = B_m\) となるように文字を選ぶ場合は、\(c\) を更新する。
• \(A_m \neq B_m\) となるように文字を選ぶ場合は、その時点でパスが分岐するため、\(c\) 通りの状態を \(\mathrm{dp}\) の \(V=1\) に対応する初期状態に加算する。
• すでに \(X_k \neq Y_k\) となる \(k\) が決まっていた \(\mathrm{dp}\) に対しては、各 \(A_m, B_m\) の選び方についてコスト \(c_m\) および新しい \(X, Y\) のターゲットを計算し、状態を更新する。

計算量は \(O(N)\) （ただし \(6 \times 6 \times 3 \times 9 = 972\) 程度の定数倍がかかる）となり、十分高速に答えを求めることができます。