汉诺塔是流传数百年的经典递归问题：将n个大小不一的圆盘从起始柱移动到目标柱，期间只能借助一根辅助柱，且任何时候大盘都不能压在小盘之上。传统解法用递归即可在 2^n-1 步内完成，但递归仅给出一种可行解，并未探索整个状态空间。本文将换个视角，用Java将汉诺塔建模为状态空间搜索问题，依次实现BFS广度优先搜索求最短路径，以及A*启发式搜索大幅加速求解过程，从图论角度重新理解这一经典问题。
一、问题建模：状态空间表示
1.1 状态编码
将n个盘子从0开始编号（0号最小，n-1号最大）。每根柱子用0、1、2表示。一个状态就是每个盘子所在的柱子编号。由于共有n个盘子，每个盘子有3种位置，状态空间大小为 3^n。
为了高效地放入哈希表和优先队列，我们使用三进制整数编码：
/**
* 将状态数组编码为唯一整数（三进制）
* state[i] 表示第i个盘子所在的柱子（0,1,2）
* 编码规则：code = state[0] + state[1]*3 + state[2]*3^2 + ...
*/
static int encode(int[] state) {
int code = 0;
int pow = 1;
for (int i = 0; i < state.length; i++) {
code += state[i] * pow;
pow *= 3;
}
return code;
}
/**
* 将整数解码回状态数组
*/
static int[] decode(int code, int n) {
int[] state = new int[n];
for (int i = 0; i < n; i++) {
state[i] = code % 3;
code /= 3;
}
return state;
}
1.2 合法性检验与状态转移
一个移动是否合法，取决于被移动盘子是否是所在柱子的最上方，以及目标柱子是否为空或顶部盘子更大。
/**
* 获取每根柱子上最上方（即编号最小）的盘子
* 返回数组 top[peg] = 该柱子最上方盘子的编号，若柱子为空则为 -1
*/
static int[] getTopDisks(int[] state) {
int[] top = {-1, -1, -1};
for (int i = 0; i < state.length; i++) {
int peg = state[i];
// 由于盘子按编号从小到大遍历，第一个遇到的即为最上方
if (top[peg] == -1) {
top[peg] = i;
}
}
return top;
}
/**
* 生成当前状态的所有合法后继状态
* @param state 当前状态数组
* @return 所有合法移动后的新状态编码列表
*/
static List<int[]> getNeighbors(int[] state) {
List<int[]> neighbors = new ArrayList<>();
int[] top = getTopDisks(state);
for (int from = 0; from < 3; from++) {
int disk = top[from];
if (disk == -1) continue; // 柱子为空
for (int to = 0; to < 3; to++) {
if (from == to) continue;
int targetTop = top[to];
// 目标柱子为空，或顶部盘子比当前盘子大（编号更大）
if (targetTop == -1 || targetTop > disk) {
int[] next = state.clone();
next[disk] = to;
neighbors.add(next);
}
}
}
return neighbors;
}
二、核心算法一：BFS广度优先搜索
BFS天然适合在无权图中求最短路径。将汉诺塔的每个状态视为图中的节点，每次合法移动视为一条权重为1的边，则从初始状态到目标状态的最短路径长度，就是最少移动步数。
import java.util.*;
/**
* 汉诺塔BFS求解器
* 求从初始状态到目标状态的最短移动序列
*/
public class HanoiBFS {
private final int n; // 盘子数量
private final int startPeg; // 起始柱
private final int targetPeg; // 目标柱
private final int initState; // 初始状态编码
private final int goalState; // 目标状态编码
public HanoiBFS(int n, int startPeg, int targetPeg) {
this.n = n;
this.startPeg = startPeg;
this.targetPeg = targetPeg;
int[] init = new int[n];
Arrays.fill(init, startPeg);
this.initState = encode(init);
int[] goal = new int[n];
Arrays.fill(goal, targetPeg);
this.goalState = encode(goal);
}
/**
* BFS搜索最短路径
* @return 最短路径上的状态序列（包含起点和终点），若无解返回空列表
*/
public List<int[]> solve() {
// 已访问状态：记录到达该状态的前驱状态编码，用于路径回溯
Map<Integer, Integer> parent = new HashMap<>();
// 记录前驱状态中移动的是哪个盘子
Map<Integer, Integer> movedDisk = new HashMap<>();
Queue<Integer> queue = new ArrayDeque<>();
parent.put(initState, -1);
queue.offer(initState);
while (!queue.isEmpty()) {
int curCode = queue.poll();
if (curCode == goalState) {
return reconstructPath(parent);
}
int[] curState = decode(curCode, n);
for (int[] next : getNeighbors(curState)) {
int nextCode = encode(next);
if (!parent.containsKey(nextCode)) {
parent.put(nextCode, curCode);
queue.offer(nextCode);
}
}
}
return Collections.emptyList(); // 汉诺塔必有解，不会走到这里
}
/**
* 根据parent映射回溯重构路径
*/
private List<int[]> reconstructPath(Map<Integer, Integer> parent) {
List<int[]> path = new ArrayList<>();
int cur = goalState;
while (cur != -1) {
path.add(decode(cur, n));
cur = parent.get(cur);
}
Collections.reverse(path);
return path;
}
// encode, decode, getNeighbors 方法见上文...
static int encode(int[] state) { /* ... */ }
static int[] decode(int code, int n) { /* ... */ }
static List<int[]> getNeighbors(int[] state) { /* ... */ }
static int[] getTopDisks(int[] state) { /* ... */ }
public static void main(String[] args) {
HanoiBFS solver = new HanoiBFS(4, 0, 2);
List<int[]> path = solver.solve();
System.out.println("BFS求解 4层汉诺塔，最少步数: " + (path.size() - 1));
System.out.println("状态序列:");
for (int[] s : path) {
System.out.println(Arrays.toString(s));
}
}
}
BFS的局限性在于它需要遍历整个状态空间的最短路径层。对于n=4，3^4=81个状态尚可接受；但n=10时状态数高达59049，BFS的内存和时间开销将急剧膨胀。
三、核心算法二：A*启发式搜索
A*算法在BFS的基础上引入启发式函数 h(state)，优先扩展”看起来离目标更近”的状态。只要h是可采纳的（admissible，即从不高估真实代价），A*就能保证找到最优解。
3.1 可采纳启发式函数设计
对于汉诺塔，一个简洁而有效的启发式是：统计不在目标柱子上的盘子数量。因为每个不在目标位置的盘子至少需要移动一次，所以该值是真实代价的下界。
更紧的下界是：找到编号最大的不在目标柱子的盘子k，则至少还需要 2^{k+1} - 1 步（先把k上面的所有盘子移到辅助柱，移动k，再把那堆移回来）。本文采用后者，效率更高。
/**
* 计算启发式值 h(state)
* 找到最大的不在目标柱子上的盘子，返回 2^(k+1) - 1
* 若所有盘子都在目标柱子上，返回0
*/
static int heuristic(int[] state, int targetPeg) {
int maxOff = -1;
for (int i = state.length - 1; i >= 0; i--) {
if (state[i] != targetPeg) {
maxOff = i;
break;
}
}
if (maxOff == -1) return 0;
return (1 << (maxOff + 1)) - 1; // 2^(k+1) - 1
}
3.2 A*搜索实现
import java.util.*;
/**
* 汉诺塔A*求解器
* 使用优先队列按 f = g + h 排序，g为已走步数，h为启发式估计
*/
public class HanoiAStar {
private final int n;
private final int targetPeg;
private final int initState;
private final int goalState;
public HanoiAStar(int n, int startPeg, int targetPeg) {
this.n = n;
this.targetPeg = targetPeg;
int[] init = new int[n];
Arrays.fill(init, startPeg);
this.initState = encode(init);
int[] goal = new int[n];
Arrays.fill(goal, targetPeg);
this.goalState = encode(goal);
}
/**
* A\*搜索最短路径
*/
public List<int[]> solve() {
// 记录到达每个状态的最小实际代价 g
Map<Integer, Integer> gScore = new HashMap<>();
Map<Integer, Integer> parent = new HashMap<>();
// 优先队列按 f = g + h 排序
PriorityQueue<Node> openSet = new PriorityQueue<>(Comparator.comparingInt(a -> a.f));
int h0 = heuristic(decode(initState, n), targetPeg);
gScore.put(initState, 0);
openSet.offer(new Node(initState, h0));
while (!openSet.isEmpty()) {
Node current = openSet.poll();
int curCode = current.code;
int curG = gScore.get(curCode);
if (curCode == goalState) {
return reconstructPath(parent, curCode);
}
// 如果该节点已被更优路径访问过，跳过
if (current.f > curG + heuristic(decode(curCode, n), targetPeg)) {
continue;
}
int[] curState = decode(curCode, n);
for (int[] next : getNeighbors(curState)) {
int nextCode = encode(next);
int tentativeG = curG + 1;
if (tentativeG < gScore.getOrDefault(nextCode, Integer.MAX_VALUE)) {
parent.put(nextCode, curCode);
gScore.put(nextCode, tentativeG);
int h = heuristic(next, targetPeg);
openSet.offer(new Node(nextCode, tentativeG + h));
}
}
}
return Collections.emptyList();
}
/**
* 路径回溯
*/
private List<int[]> reconstructPath(Map<Integer, Integer> parent, int goal) {
List<int[]> path = new ArrayList<>();
int cur = goal;
while (cur != -1) {
path.add(decode(cur, n));
cur = parent.getOrDefault(cur, -1);
}
Collections.reverse(path);
return path;
}
/**
* 优先队列节点
*/
private static class Node {
final int code; // 状态编码
final int f; // f = g + h
Node(int code, int f) {
this.code = code;
this.f = f;
}
}
// encode, decode, getNeighbors, getTopDisks, heuristic 方法...
static int encode(int[] state) {
int code = 0, pow = 1;
for (int i = 0; i < state.length; i++) {
code += state[i] * pow;
pow *= 3;
}
return code;
}
static int[] decode(int code, int n) {
int[] state = new int[n];
for (int i = 0; i < n; i++) {
state[i] = code % 3;
code /= 3;
}
return state;
}
static int[] getTopDisks(int[] state) {
int[] top = {-1, -1, -1};
for (int i = 0; i < state.length; i++) {
int peg = state[i];
if (top[peg] == -1) top[peg] = i;
}
return top;
}
static List<int[]> getNeighbors(int[] state) {
List<int[]> neighbors = new ArrayList<>();
int[] top = getTopDisks(state);
for (int from = 0; from < 3; from++) {
int disk = top[from];
if (disk == -1) continue;
for (int to = 0; to < 3; to++) {
if (from == to) continue;
int targetTop = top[to];
if (targetTop == -1 || targetTop > disk) {
int[] next = state.clone();
next[disk] = to;
neighbors.add(next);
}
}
}
return neighbors;
}
static int heuristic(int[] state, int targetPeg) {
int maxOff = -1;
for (int i = state.length - 1; i >= 0; i--) {
if (state[i] != targetPeg) {
maxOff = i;
break;
}
}
if (maxOff == -1) return 0;
return (1 << (maxOff + 1)) - 1;
}
public static void main(String[] args) {
HanoiAStar solver = new HanoiAStar(5, 0, 2);
long start = System.currentTimeMillis();
List<int[]> path = solver.solve();
long cost = System.currentTimeMillis() - start;
System.out.println("A*求解 5层汉诺塔，最少步数: " + (path.size() - 1));
System.out.println("耗时: " + cost + " ms");
}
}
3.3 A*的优势对比
以n=5为例，最优解需要31步。BFS需要扩展几乎整个状态空间的前31层，而A*凭借 2^{k+1}-1 的强大启发式，通常只需扩展数百个节点即可找到最优解。当n增大到8时，BFS因内存爆炸而无法在普通设备上运行，A*仍能在毫秒级完成。
四、进阶：将移动序列可视化
为了让搜索结果更直观，我们可以将状态序列转换为人类可读的移动指令：
/**
* 将相邻两个状态转换为一个移动描述
* @param before 移动前状态
* @param after 移动后状态
* @return 移动描述，如 "将盘子1从柱子0移到柱子2"
*/
static String moveDescription(int[] before, int[] after) {
for (int i = 0; i < before.length; i++) {
if (before[i] != after[i]) {
return String.format("将盘子%d从柱子%d移到柱子%d", i, before[i], after[i]);
}
}
return "无移动";
}
/**
* 打印完整移动序列
*/
static void printMoves(List<int[]> path) {
System.out.println("=== 移动序列 ===");
for (int i = 0; i < path.size() - 1; i++) {
System.out.printf("第%2d步: %s%n", i + 1, moveDescription(path.get(i), path.get(i + 1)));
}
}
五、复杂度分析
| 算法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| BFS | O(3^n) | O(3^n) | n ≤ 6，教学演示 |
| A*（可采纳启发式） | O(b^d)，d=2^n-1 | O(3^n) | n ≤ 10，实际求解 |
| 递归经典解 | O(2^n) | O(n) 递归栈 | n 任意，只求解不求路径 |
其中A*的 O(b^d) 是理论最坏情况，由于启发式函数极强，实际扩展节点数远小于BFS。汉诺塔的最优解长度恒为 2^n-1，A*的启发式 2^{k+1}-1 在接近目标时急剧收敛，是其高效的关键。
六、完整项目结构
hanoi-search/
├── src/
│ ├── HanoiBFS.java # BFS最短路径教学版
│ ├── HanoiAStar.java # A*高效求解版
│ └── HanoiUtils.java # 公共工具类（编码、解码、邻居生成等）
└── README.md
编译与运行：
javac src/HanoiAStar.java
java -cp src HanoiAStar
总结
本文将汉诺塔从传统的递归问题重新定义为状态空间搜索问题，核心收获包括：
- 三进制状态编码将组合状态压缩为整数，使汉诺塔能够高效地放入哈希表和优先队列。
- BFS提供了在无权状态图中求最短路径的通用框架，验证了汉诺塔的最优解长度确为
2^n-1。 - A*算法配合
2^{k+1}-1的可采纳启发式，将搜索空间从指数级膨胀降为可控范围，展现了启发式搜索在组合优化中的威力。 - 从工程角度看，当问题可以被建模为图且需要最优路径时，A* 算法往往是在 完备性（保证最优）与 效率 之间的最佳平衡点。
