汉诺塔（Tower of Hanoi）是经典的递归问题，传统解法使用分治递归。本文将从动态规划（DP）的角度重新分析汉诺塔问题，并引入状态压缩技术高效记录和查询子问题解。
问题重述
汉诺塔问题：有三根柱子A、B、C，初始时A柱上有n个大小不一的盘子，大盘在下小盘在上。目标是将所有盘子从A柱移动到C柱，规则：
1. 每次只能移动一个盘子
2. 大盘不能放在小盘上
动态规划建模
状态定义
定义DP状态为三元组 (n, src, dst)，表示将n个盘子从src柱移动到dst柱所需的最少步数。由于有三根柱子，辅助柱为aux = 6 – src – dst（假设柱子编号为1,2,3）。
状态转移方程
将n个盘子从src移动到dst的最优策略：
1. 将上面n-1个盘子从src移动到aux：DP(n-1, src, aux) 步
2. 将第n个（最大的）盘子从src移动到dst：1步
3. 将n-1个盘子从aux移动到dst：DP(n-1, aux, dst) 步
$$DP(n, src, dst) = DP(n-1, src, aux) + 1 + DP(n-1, aux, dst)$$
边界条件：DP(1, src, dst) = 1
经典解
上述递归直接给出经典结果：DP(n) = 2^n – 1
状态压缩技术
对于更复杂的汉诺塔变体（如限制某些移动、多柱汉诺塔等），需要记录每个盘子的位置。使用状态压缩：
- 每个盘子可能在3根柱子之一，用2个比特表示
- n个盘子的状态可用2n个比特压缩存储
- 使用位运算快速判断移动合法性
Java实现
import java.util.*;
/**
* 汉诺塔动态规划求解器
* 使用DP状态转移与位运算状态压缩记录盘子位置
*/
public class HanoiDP {
// 柱子编号：0=A, 1=B, 2=C
private static final char[] PEG_NAMES = {'A', 'B', 'C'};
// 状态压缩：每个盘子用2位表示所在柱子（0-2），最多支持32个盘子（64位long）
private long state;
private int n; // 盘子数量
// DP记忆化表：state -> 到达目标状态的最少步数
private Map<Long, Integer> memo;
// 路径记录：用于输出最优移动序列
private Map<Long, Long> parent;
private Map<Long, String> moveRecord;
public HanoiDP(int n) {
this.n = n;
this.state = 0; // 所有盘子在A柱（用0表示）
this.memo = new HashMap<>();
this.parent = new HashMap<>();
this.moveRecord = new HashMap<>();
}
/**
* 获取第i个盘子（0-based，0是最小盘）所在的柱子
*/
int getPeg(long s, int disk) {
return (int) ((s >> (disk * 2)) & 3);
}
/**
* 设置第i个盘子所在的柱子
*/
long setPeg(long s, int disk, int peg) {
long mask = ~(3L << (disk * 2));
return (s & mask) | ((long) peg << (disk * 2));
}
/**
* 初始化状态：所有盘子都在A柱（0）
*/
long initialState() {
return 0;
}
/**
* 目标状态：所有盘子都在C柱（2）
*/
long goalState() {
long s = 0;
for (int i = 0; i < n; i++) {
s = setPeg(s, i, 2);
}
return s;
}
/**
* 检查从from柱移动最上面的盘子到to柱是否合法
* 返回移动的盘子编号，-1表示非法
*/
int canMove(long s, int from, int to) {
if (from == to) return -1;
// 找到from柱最上面的盘子（编号最小的在from柱的盘子）
int topFrom = -1;
for (int i = 0; i < n; i++) {
if (getPeg(s, i) == from) {
topFrom = i;
break; // i从小到大，第一个就是最上面的
}
}
if (topFrom == -1) return -1; // from柱为空
// 找到to柱最上面的盘子
int topTo = -1;
for (int i = 0; i < n; i++) {
if (getPeg(s, i) == to) {
topTo = i;
break;
}
}
// 如果to柱为空，或者from柱最上面的盘子比to柱最上面的小
if (topTo == -1 || topFrom < topTo) {
return topFrom;
}
return -1;
}
/**
* 执行移动，返回新状态
*/
long moveDisk(long s, int disk, int to) {
return setPeg(s, disk, to);
}
/**
* BFS搜索最少步数（适用于小n，状态空间为3^n）
*/
public int solveBFS() {
long start = initialState();
long goal = goalState();
if (start == goal) return 0;
Queue<Long> queue = new LinkedList<>();
Set<Long> visited = new HashSet<>();
Map<Long, Integer> dist = new HashMap<>();
Map<Long, Long> parentMap = new HashMap<>();
Map<Long, String> moveMap = new HashMap<>();
queue.offer(start);
visited.add(start);
dist.put(start, 0);
while (!queue.isEmpty()) {
long cur = queue.poll();
int d = dist.get(cur);
// 尝试所有6种移动（A->B, A->C, B->A, B->C, C->A, C->B）
int[][] moves = {{0,1}, {0,2}, {1,0}, {1,2}, {2,0}, {2,1}};
for (int[] mv : moves) {
int disk = canMove(cur, mv[0], mv[1]);
if (disk == -1) continue;
long next = moveDisk(cur, disk, mv[1]);
if (!visited.contains(next)) {
visited.add(next);
dist.put(next, d + 1);
parentMap.put(next, cur);
moveMap.put(next, "移动盘子" + (disk+1) + "从" + PEG_NAMES[mv[0]] + "到" + PEG_NAMES[mv[1]]);
if (next == goal) {
// 保存路径
this.parent = parentMap;
this.moveRecord = moveMap;
return d + 1;
}
queue.offer(next);
}
}
}
return -1;
}
/**
* 使用数学公式直接计算最少步数：2^n - 1
*/
public int solveFormula() {
return (1 << n) - 1; // 2^n - 1
}
/**
* 经典递归解法（分治策略）
*/
public void solveRecursive(int disks, int from, int to, List<String> moves) {
if (disks == 0) return;
int aux = 3 - from - to; // 辅助柱（假设柱子编号为0,1,2）
solveRecursive(disks - 1, from, aux, moves);
moves.add("移动盘子" + disks + "从" + PEG_NAMES[from] + "到" + PEG_NAMES[to]);
solveRecursive(disks - 1, aux, to, moves);
}
/**
* 动态规划递归（带记忆化）
* 求解将第k到第n-1个盘子从src移动到dst的最少步数
*/
public int solveDP(int k, int src, int dst) {
if (k >= n) return 0;
if (k == n - 1) return 1; // 最后一个盘子
int aux = 3 - src - dst;
String key = k + "_" + src + "_" + dst;
if (memo.containsKey((long)key.hashCode())) {
return memo.get((long)key.hashCode());
}
// DP转移：先移动上面的盘子到辅助柱，再移动当前盘子，最后移动辅助柱的盘子到目标柱
int steps = solveDP(k + 1, src, aux) + 1 + solveDP(k + 1, aux, dst);
memo.put((long)key.hashCode(), steps);
return steps;
}
/**
* 打印BFS找到的最优路径
*/
public void printPath() {
long goal = goalState();
List<String> path = new ArrayList<>();
long cur = goal;
while (parent.containsKey(cur)) {
path.add(moveRecord.get(cur));
cur = parent.get(cur);
}
Collections.reverse(path);
System.out.println("最优移动序列（共" + path.size() + "步）：");
for (int i = 0; i < path.size(); i++) {
System.out.println((i + 1) + ". " + path.get(i));
}
}
/**
* 打印当前状态的柱子分布
*/
public void printState(long s) {
for (int peg = 0; peg < 3; peg++) {
System.out.print(PEG_NAMES[peg] + ": ");
List<Integer> disks = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (getPeg(s, i) == peg) {
disks.add(i + 1);
}
}
System.out.println(disks);
}
}
/**
* Frame-Stewart算法（四柱汉诺塔最优算法）
* 将n个盘子从A柱移动到D柱，使用k根柱子
*/
public int frameStewart(int disks, int k) {
if (disks == 0) return 0;
if (disks == 1) return 1;
if (k == 3) return (1 << disks) - 1; // 经典三柱
int min = Integer.MAX_VALUE;
// 尝试将m个盘子先用k根柱子移动到辅助柱，剩下n-m个用k-1根柱子移动
for (int m = 1; m < disks; m++) {
int steps = 2 * frameStewart(m, k) + frameStewart(disks - m, k - 1);
min = Math.min(min, steps);
}
return min;
}
public static void main(String[] args) {
int n = 4; // 4个盘子
System.out.println("汉诺塔动态规划求解器（" + n + "个盘子）\n");
HanoiDP solver = new HanoiDP(n);
// 1. 数学公式
System.out.println("=== 数学公式 ===");
System.out.println("最少步数：2^" + n + " - 1 = " + solver.solveFormula());
System.out.println();
// 2. 经典递归
System.out.println("=== 经典递归解法 ===");
List<String> recursiveMoves = new ArrayList<>();
solver.solveRecursive(n, 0, 2, recursiveMoves);
System.out.println("步数：" + recursiveMoves.size());
for (int i = 0; i < recursiveMoves.size(); i++) {
System.out.println((i + 1) + ". " + recursiveMoves.get(i));
}
System.out.println();
// 3. BFS验证（适用于小n）
System.out.println("=== BFS状态压缩搜索 ===");
long start = System.currentTimeMillis();
int bfsSteps = solver.solveBFS();
long end = System.currentTimeMillis();
System.out.println("BFS最少步数：" + bfsSteps);
System.out.println("BFS耗时：" + (end - start) + "ms");
if (n <= 4) {
solver.printPath();
}
System.out.println();
// 4. 状态压缩演示
System.out.println("=== 状态压缩演示 ===");
System.out.println("初始状态：");
solver.printState(solver.initialState());
System.out.println("\n目标状态：");
solver.printState(solver.goalState());
System.out.println("\n状态编码（初始）：" + Long.toBinaryString(solver.initialState()));
System.out.println("状态编码（目标）：" + Long.toBinaryString(solver.goalState()));
System.out.println();
// 5. 四柱汉诺塔Frame-Stewart算法
System.out.println("=== Frame-Stewart算法（四柱汉诺塔） ===");
for (int disks = 1; disks <= 10; disks++) {
int steps = solver.frameStewart(disks, 4);
System.out.println(disks + "个盘子，" + steps + "步（三柱需要" + ((1 << disks) - 1) + "步）");
}
}
}
动态规划视角的深入分析
重叠子问题与最优子结构
汉诺塔问题满足动态规划的两大性质：
- 最优子结构：整体最优解包含子问题的最优解。将n个盘子从A移到C，必须先最优地将n-1个盘子从A移到B
- 重叠子问题：相同的子问题（如移动k个盘子）在不同阶段重复出现，记忆化可避免重复计算
状态压缩的优势
对于n个盘子，传统方法需要存储每个盘子的位置，空间复杂度O(n)。使用位压缩：
- 每个盘子2比特，n个盘子共2n比特
- 可存储在单个long变量中（最多32个盘子）
- 状态转移通过位运算完成，时间复杂度O(1)
状态空间大小为3^n（每个盘子有3种位置选择），对于n=20约为35亿，BFS不可行，但数学公式直接给出O(1)解。
Frame-Stewart算法：四柱汉诺塔
对于四柱（或更多柱）汉诺塔，经典递归不再最优。Frame-Stewart算法给出最优策略：
- 选择m（1 ≤ m < n），将m个盘子用k柱移动到某辅助柱
- 将剩下n-m个盘子用k-1柱（一根柱子被占用）移动到目标柱
- 将m个盘子从辅助柱用k柱移动到目标柱
$$F(n, k) = \min_{1 \leq m < n} {2 \cdot F(m, k) + F(n-m, k-1)}$$
四柱汉诺塔的最优解至今未被严格证明，但Frame-Stewart算法被广泛认为是最优的。
复杂度对比
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 数学公式 | O(1) | O(1) | 经典三柱汉诺塔 |
| 递归 | O(2^n) | O(n) | 输出移动序列 |
| 记忆化DP | O(n) | O(n) | 带约束的变体 |
| BFS状态压缩 | O(3^n) | O(3^n) | 小n验证/变体问题 |
| Frame-Stewart | O(n^2) | O(n^2) | 四柱汉诺塔 |
总结
本文从动态规划角度重新分析了汉诺塔问题，使用状态压缩技术高效表示和转移状态。虽然经典三柱汉诺塔有简单的数学解，但DP和状态压缩方法为处理更复杂的变体（如限制移动、多柱汉诺塔）提供了通用框架。Frame-Stewart算法展示了如何将问题分解为子问题并通过动态规划求解，是组合优化中的经典范例。
