如何证明汉诺塔的分治算法是最优解

约 2407 字大约 8 分钟

技术算法数学递归

2026-08-01

汉诺塔是算法课上最经典的递归问题：三根柱子、若干个大小不同的圆盘，圆盘最初从小到大叠在一根柱子上，每次只能移动一个，任何时候都不能把大盘压在小盘上，目标是把整摞盘完整搬到另一根柱子。

大多数人第一次接触汉诺塔，很快就能理解它的分治解法：先挪走上面的小盘，再移最大的盘，最后把小盘叠回去。但能解决问题只说明算法正确，不能说明它最优——理论上完全可能存在某种更巧妙的方案，用更少的步数完成。

要证明分治算法最优，得同时回答两个问题：分治算法到底需要移动多少次（上界），以及任何合法方案最少必须移动多少次（下界）。两个数恰好相等时，最优性才真正成立。

如何证明汉诺塔的分治算法是最优解

从递推式推出分治算法需要 2ⁿ − 1 步，再盯住最大圆盘证明任何方案都不可能更少，最后用数学归纳法把上下界收口——顺便看清正确性证明和最优性证明的区别。

分治解法与递推式
为什么任何算法都不能更快
绕路为什么没用
归纳法收口
上界与下界的方法论

最优性证明的结构

证明一个算法最优，本质是让“能做到的”和“不可能突破的”两个数字相遇。

上界

构造一个可行方案：分治算法用 2ⁿ − 1 步确实能完成。

下界

证明必然性：最大圆盘移动前后各藏着一个 n−1 规模的子问题，谁也绕不开。

归纳收口

上界 ≤ 2ⁿ − 1 ≤ 下界同时成立，夹出精确值 T(n) = 2ⁿ − 1。

指数增长

递推每层翻倍，64 个盘就是 2⁶⁴ − 1 步——简洁的递归不等于便宜的成本。

分治思路与递推式

设有 $n$ 个圆盘，起始柱 $A$ ，辅助柱 $B$ ，目标柱 $C$ 。最大的圆盘压在最底下，想动它，必须先把上面 $n-1$ 个盘全部挪走——整个过程自然拆成三步：

把上面 $n-1$ 个盘从 $A$ 移到 $B$ （一个规模更小的汉诺塔问题）；
把最大的第 $n$ 个盘从 $A$ 移到 $C$ （一步）；
把 $B$ 上的 $n-1$ 个盘移到 $C$ ，叠回最大盘上（又一个 $n-1$ 规模的汉诺塔问题）。

用 $T(n)$ 表示移动 $n$ 个盘的步数，分治算法满足：

T(n) = 2T(n-1) + 1,\qquad T(1) = 1

逐层展开：

\begin{aligned} T(n) &= 2T(n-1)+1\\ &= 2\bigl(2T(n-2)+1\bigr)+1 = 2^2T(n-2)+2+1\\ &= 2^{n-1}T(1)+2^{n-2}+\cdots+2+1\\ &= 2^{n-1}+2^{n-2}+\cdots+2+1 \end{aligned}

等比数列求和，得到：

T(n) = 2^n - 1

递归写成代码也就几行，可以直接跑一下验证步数：

python playground

def hanoi(n, src, aux, dst, moves):
    if n == 1:
        moves.append(f"{src} -> {dst}")
        return
    hanoi(n - 1, src, dst, aux, moves)
    moves.append(f"{src} -> {dst}")
    hanoi(n - 1, aux, src, dst, moves)

moves = []
hanoi(3, 'A', 'B', 'C', moves)
print(f"共 {len(moves)} 步：", moves)   # 2^3 - 1 = 7

到这里只证明了分治算法能在 $2^n-1$ 步内完成——它是一个上界。其他算法会不会更快，还没排除。

为什么任何算法都不能更快

证明下界的钥匙，是盯住最大的圆盘。

无论采取什么策略，最大盘最初在起始柱底部，最终必须到目标柱底部，所以它必然要被移动。而在它被移动的那一刻，局面被规则锁死了：

它上面的 $n-1$ 个盘必须已经全部移走，否则它取不出来；
目标柱必须是空的——目标柱上但凡有一个更小的盘，它就放不上去；
一共只有三根柱子，所以那 $n-1$ 个盘只能全部待在辅助柱上，而且仍要保持合法的大小顺序。

也就是说，不管算法中间怎么折腾，在移动最大盘之前，它都必须完成一件事：把 $n-1$ 个盘从起始柱完整搬到辅助柱。这本身就是一个 $n-1$ 规模的汉诺塔问题，至少要 $T(n-1)$ 步。

移动最大盘本身至少一步。最大盘就位后，那 $n-1$ 个盘还在辅助柱上，最终必须全部搬到目标柱叠好——又是一个 $n-1$ 规模的汉诺塔问题，至少再要 $T(n-1)$ 步。

所以任何合法方案都满足：

T(n) \geq 2T(n-1) + 1

这个不等式里的每一项都是完成任务时必然发生的操作，没有讨价还价的余地。

让最大盘绕路会不会更快

有人会想到一种看似不同的思路：先把最大盘移到辅助柱，再从辅助柱移到目标柱，靠绕路给小盘腾出灵活性。

这条路走不通，原因在于最大盘有个特殊性质：它在哪根柱子的底部，所有小盘都能叠在它上面。它的位置既不挤占小盘的空间，也不给小盘提供任何新的移动能力——挪动它对别人毫无帮助。

而代价是实打实的：移到辅助柱之前要清空它上面的所有盘，从辅助柱再出发之前，又得把落在它上面的盘再清空一次。绕路只会让最大盘多动一次，还附赠一整轮额外的小盘搬运。

所以最优方案里，最大盘只动一次：从起始柱直达目标柱。

用数学归纳法收口

现在可以严格证明：移动 $n$ 个盘的最少步数就是 $2^n - 1$ 。

奠基： $n = 1$ 时，一个盘至少动一次，动一次也确实够， $T(1) = 1 = 2^1 - 1$ 。

归纳：假设 $n-1$ 个盘的最少步数是 $T(n-1) = 2^{n-1} - 1$ 。对 $n$ 个盘，由下界分析：

T(n) \geq 2T(n-1) + 1 = 2\bigl(2^{n-1}-1\bigr) + 1 = 2^n - 1

另一方面，分治算法确实能在恰好 $2^n - 1$ 步内完成，所以 $T(n) \leq 2^n - 1$ 。两边一夹：

2^n - 1 \leq T(n) \leq 2^n - 1 \implies \boxed{T(n) = 2^n - 1}

分治算法达到的步数与任何算法都无法突破的下界完全重合——它就是标准三柱汉诺塔的最优解。

正确性和最优性是两个层次

汉诺塔把算法证明的两个层次展示得很干净：

正确性回答"能不能做对"：所有盘能否按规则搬到目标柱。分治算法靠递归解决两个 $n-1$ 子问题做到了这一点。
最优性回答"有没有浪费"：是否用了最少的资源（这里是移动次数）。算出分治算法要 $2^n-1$ 步只是成本核算，不能排除别人更快；只有证明任何方案都至少要 $2^n-1$ 步，才能宣布无法再优化。

这种"先构造一个能达到的方案，再证明谁都不可能低于它"的套路，在算法分析里非常常见：前者叫上界，后者叫下界，上下界相遇时就得到了精确结果。汉诺塔难得之处在于，它的上下界证明都只有几段话，是理解这套方法论最好的入门例子。

$2^n$ 增长得有多快

盘数 $n$	最少步数 $2^n - 1$
3	7
4	15
10	1 023
20	1 048 575
64	18 446 744 073 709 551 615

盘少的时候数字很温和，但指数增长很快就失控。著名的"梵天塔"传说里是 64 个盘——按每秒移动一个盘算，完成搬运需要约 5 850 亿年，远超宇宙目前约 138 亿年的年龄。

这也是递归算法给人的一个重要提醒：递归形式可以极其简洁，成本却可能极其巨大。分析递归算法时，不能只看代码优不优雅，得认真算它的递推关系和增长速度。

结语

汉诺塔分治算法的最优性，归结起来是一个很干净的事实：为了移动最大盘，必须先把 $n-1$ 个盘全部移到辅助柱；最大盘就位后，又必须把它们从辅助柱移到目标柱。这两个 $n-1$ 规模的子问题加上中间那一步，谁也省不掉，所以任何算法至少需要 $2T(n-1)+1$ 步。

分治算法恰好按这个无法避免的结构执行，一步不多，最终 $T(n) = 2^n - 1$ ——它不仅能正确完成任务，还精确踩在理论下界上。这就是它被称为最优算法的原因。

要点回收

分治解法满足 T(n) = 2T(n−1) + 1，解出 T(n) = 2ⁿ − 1，这是上界。
下界靠盯住最大盘：它移动前后各藏着一个 n−1 规模的子问题，任何方案都绕不开。
上界与下界重合，归纳法收口，最优性成立；绕路只会让最大盘白多动一次。
正确性回答能不能做对，最优性回答有没有浪费——上下界相遇才有精确结果。

版权所有

版权归属：Shuo Liu

许可证：署名-非商业性 4.0 国际 (CC-BY-NC-4.0)