多柱汉诺塔问题浅析

汉诺塔问题

汉诺塔（Tower of Hanoi）是一个数学游戏：有三根柱子，其中一根柱子自底向上串着尺寸渐小的多个圆盘，遵循以下规则：
1、一次只能移动一个圆盘；
2、大圆盘不能放在小圆盘上面。
请问最少需要移动多少步，才能将所有圆盘移到另一根柱子上？

解答： 设移动N$N$N个圆盘所需的最少步数为F(N)$F(N)$F(N)。将三根柱子分别命名为A、B、C，要把N$N$N个圆盘从A柱移至C柱，拆解为如下步骤：
1、将N−1$N-1$N−1个圆盘从A柱移至B柱，需要F(N−1)$F(N-1)$F(N−1)步；
2、将余下的最大圆盘从A柱移至C柱，需要一步；
3、将N−1$N-1$N−1个圆盘从B柱移至C柱，需要F(N−1)$F(N-1)$F(N−1)步。
得到最少移动步数的递推公式F(N)=2F(N−1)+1$F(N)=2F(N-1)+1$F(N)=2F(N−1)+1。易知F(1)=1$F(1)=1$F(1)=1，可得通项公式F(N)=2N−1$F(N)=2^N-1$F(N)=2N−1。

推广： 如果有四根或者更多柱子，所需的最少移动步数又是多少？

Frame-Stewart算法

该算法采用递推的思想来求解多柱汉诺塔问题。设M$M$M根柱子、N$N$N个圆盘所需的最少移动步数为FM(N)$F_M(N)$FM​(N)，将移动步骤拆解为：
1、将r$r$r个圆盘移到另一根柱子上（非目标柱），需要FM(r)$F_M(r)$FM​(r)步；
2、将余下的N−r$N-r$N−r个圆盘移至目标柱，需要FM−1(N−r)$F_{M-1}(N-r)$FM−1​(N−r)步；
3、将r$r$r个圆盘移至目标柱，需要FM(r)$F_M(r)$FM​(r)步。
得到递推公式
FM(N)=min1≤r<N{2FM(r)+FM−1(N−r)}$F_M(N)=\min\limits_{1\le r<N}\{2F_M(r)+F_{M-1}(N-r)\}$FM​(N)=1≤r<Nmin​{2FM​(r)+FM−1​(N−r)}
代码：

#include <iostream>
#include <math.h>
#include <map>
using namespace std;

// the least number of movements for n disks, m pegs
map<pair<int, int>, double> mapLeastMoves;
double LeastMoves(const int n, const int m) {
    if (n < 0 || m < 3)
        return -1;
    if (n == 1)
        return 1;
    const auto index = make_pair(n, m);
    if (mapLeastMoves.count(index) > 0)
        return mapLeastMoves[index];
    double least_moves;
    if (m == 3) {
        least_moves = pow(2., n) - 1;
    } else {
        least_moves = 2 * LeastMoves(n - 1, m) + LeastMoves(1, m - 1);
        for (int r = n - 2; r > 0; --r) {
            double moves = 2 * LeastMoves(r, m) + LeastMoves(n - r, m - 1);
            if (moves < least_moves)
                least_moves = moves;
            else // a little optimization
                break;
        }
    }
    mapLeastMoves[index] = least_moves;
    return least_moves;
}

void main() {
    int M = 7, N = 10;
    cout << "M\\N";
    for (int n = 1; n <= N; ++n)
        cout << "\tN = " << n;
    cout << endl;
    for (int m = 3; m <= M; ++m) {
        cout << "M = " << m;
        for (int n = 1; n <= N; ++n)
            cout << "\t" << LeastMoves(n, m);
        cout << endl;
    }
    system("pause");
}

输出：

M\N     N = 1   N = 2   N = 3   N = 4   N = 5   N = 6   N = 7   N = 8   N = 9   N = 10
M = 3   1       3       7       15      31      63      127     255     511     1023
M = 4   1       3       5       9       13      17      25      33      41      49
M = 5   1       3       5       7       11      15      19      23      27      31
M = 6   1       3       5       7       9       13      17      21      25      29
M = 7   1       3       5       7       9       11      15      19      23      27

多柱情形下的通项公式

将FM−1(N−r)$F_{M-1}(N-r)$FM−1​(N−r)继续展开，FM(N)$F_M(N)$FM​(N)的推导公式可以改写成如下形式
FM(N)=minrM,rM−1,…,r3{2[FM(rM)+FM−1(rM−1)+⋯+F3(r3)]+1},s.t.{0≤rm<N,∀m∈[3,M]∑Mm=3rm+1=N$F_M(N)=\min\limits_{r_M,r_{M-1},\dots,r_3}\{2[F_M(r_M)+F_{M-1}(r_{M-1})+\dots+F_3(r_3)]+1\},\\s.t.\quad\begin{cases}0\le r_m<N,\forall m\in[3,M]\\\sum_{m=3}^M{r_m}+1=N\end{cases}$FM​(N)=rM​,rM−1​,…,r3​min​{2[FM​(rM​)+FM−1​(rM−1​)+⋯+F3​(r3​)]+1},s.t.{0≤rm​<N,∀m∈[3,M]∑m=3M​rm​+1=N​
用Δ$\Delta$Δ表示N$N$N加一时FM(N)$F_M(N)$FM​(N)的增量，设ΔFM(N)=FM(N)−FM(N−1)$\Delta F_M(N)=F_M(N)-F_M(N-1)$ΔFM​(N)=FM​(N)−FM​(N−1)，易得
⎧⎩⎨⎪⎪⎪⎪⎪⎪ΔFM(1)=1ΔFM(N+1)=2minm∈[3,M]{ΔFm(rm+1)}ΔFM(N+1)≥ΔFM(N)$\begin{cases}\Delta F_M(1)=1\\\Delta F_M(N+1)=2\min\limits_{m\in[3,M]}\{\Delta F_m(r_m+1)\}\\\Delta F_M(N+1)\ge\Delta F_M(N)\end{cases}$⎩⎪⎪⎨⎪⎪⎧​ΔFM​(1)=1ΔFM​(N+1)=2m∈[3,M]min​{ΔFm​(rm​+1)}ΔFM​(N+1)≥ΔFM​(N)​
若rm+1=1,∃m∈[3,M]$r_m+1=1,\exists m\in[3,M]$rm​+1=1,∃m∈[3,M]，则ΔFM(N+1)=2ΔFm(1)=2$\Delta F_M(N+1)=2\Delta F_m(1)=2$ΔFM​(N+1)=2ΔFm​(1)=2。此时Unexpected text node: '&ThickSpace;'$\text{Unexpected text node: '\&ThickSpace;'}$∑m=3M​rm​<∑m=3M​1=M−2⟹N<M−1，将N+1$N+1$N+1替换为N$N$N，可知
ΔFM(N)=2, if 1<N≤M−1$\Delta F_M(N)=2, \text{ if }1<N\le M-1$ΔFM​(N)=2, if 1<N≤M−1
若rm+1>1,∀m∈[3,M]$r_m+1>1,\forall m\in[3,M]$rm​+1>1,∀m∈[3,M]，且rm+1≤m−1,∃m∈[3,M]$r_m+1\le m-1,\exists m\in[3,M]$rm​+1≤m−1,∃m∈[3,M]，则ΔFM(N+1)=2ΔFm(rm+1)=4$\Delta F_M(N+1)=2\Delta F_m(r_m+1)=4$ΔFM​(N+1)=2ΔFm​(rm​+1)=4。此时Unexpected text node: '&ThickSpace;'$\text{Unexpected text node: '\&ThickSpace;'}$∑m=3M​rm​<∑m=3M​(m−1)=21​M(M−1)−1⟹N<21​M(M−1)，将N+1$N+1$N+1替换为N$N$N，可知
ΔFM(N)=4, if M−1<N≤12M(M−1)$\Delta F_M(N)=4, \text{ if }M-1<N\le\frac{1}{2}M(M-1)$ΔFM​(N)=4, if M−1<N≤21​M(M−1)
若rm+1>m−1,∀m∈[3,M]$r_m+1>m-1,\forall m\in[3,M]$rm​+1>m−1,∀m∈[3,M]，且rm+1≤12M(M−1),∃m∈[3,M]$r_m+1\le \frac{1}{2}M(M-1),\exists m\in[3,M]$rm​+1≤21​M(M−1),∃m∈[3,M]，则ΔFM(N+1)=2ΔFm(rm+1)=8$\Delta F_M(N+1)=2\Delta F_m(r_m+1)=8$ΔFM​(N+1)=2ΔFm​(rm​+1)=8。此时Unexpected text node: '&ThickSpace;'$\text{Unexpected text node: '\&ThickSpace;'}$∑m=3M​rm​<∑m=3M​21​m(m−1)=61​(M+1)M(M−1)−1⟹N<61​(M+1)M(M−1)，将N+1$N+1$N+1替换为N$N$N，可知
ΔFM(N)=8, if 12M(M−1)<N≤16(M+1)M(M−1)$\Delta F_M(N)=8, \text{ if }\frac{1}{2}M(M-1)<N\le\frac{1}{6}(M+1)M(M-1)$ΔFM​(N)=8, if 21​M(M−1)<N≤61​(M+1)M(M−1)
从上式中找寻规律，由数学归纳法可以证得
ΔFM(N)=2t, if CM−2M−3+t<N≤CM−2M−2+t$\Delta F_M(N)=2^t, \text{ if }C_{M-3+t}^{M-2}<N\le C_{M-2+t}^{M-2}$ΔFM​(N)=2t, if CM−3+tM−2​<N≤CM−2+tM−2​
由FM(N)=∑Nn=1ΔFM(n)$F_M(N)=\sum_{n=1}^N{\Delta F_M(n)}$FM​(N)=∑n=1N​ΔFM​(n)可知，对于M=k+2$M=k+2$M=k+2根柱子、N$N$N个圆盘的汉诺塔问题，
FM(N)=1+∑T−1t=12t(Ckk+t−Ckk−1+t)+2T(N−Ckk−1+T), if Ckk−1+T<N≤Ckk+T$F_M(N)=1+\sum_{t=1}^{T-1}{2^t(C_{k+t}^k-C_{k-1+t}^k)}+2^{T}(N-C_{k-1+T}^k), \text{ if }C_{k-1+T}^{k}<N\le C_{k+T}^{k}$FM​(N)=1+t=1∑T−1​2t(Ck+tk​−Ck−1+tk​)+2T(N−Ck−1+Tk​), if Ck−1+Tk​<N≤Ck+Tk​