每日算法 — 使用java实现汉诺塔：记忆化搜索与状态空间动态规划

引言

汉诺塔（Tower of Hanoi）是计算机科学中最经典的递归问题之一。传统解法使用递归分治，但当面对多柱汉诺塔或带限制条件的变体时，朴素的递归会导致大量重复计算。本文将使用Java实现基于记忆化搜索（Memoization）的汉诺塔求解器，通过动态规划思想将时间复杂度从指数级降至多项式级，并支持求解四柱汉诺塔（Frame-Stewart算法）等扩展问题。

核心算法思路

状态空间建模

将汉诺塔问题抽象为状态转移问题：
– 状态：每根柱子上盘的分布情况
– 目标状态：所有盘从起始柱移动到目标柱
– 转移：将最上面的盘从一根柱子移动到另一根柱子

记忆化搜索

对于四柱汉诺塔，Frame-Stewart算法指出：将n个盘分成上下两部分（上k个，下n-k个），先移动上k个到辅助柱，再移动下n-k个到目标柱，最后将上k个移动到目标柱。最优的k值需要通过搜索确定。

记忆化搜索缓存每个(n, 柱数)子问题的最优解，避免重复计算。

Java实现

基础汉诺塔与状态表示

import java.util.*;

/**
 * 汉诺塔状态表示
 */
public class HanoiState {
    private List<Stack<Integer>> pegs; // 每根柱子上的盘（栈底到栈顶）
    private int numPegs;
    private int numDisks;

    public HanoiState(int numDisks, int numPegs) {
        this.numDisks = numDisks;
        this.numPegs = numPegs;
        this.pegs = new ArrayList<>();
        for (int i = 0; i < numPegs; i++) {
            pegs.add(new Stack<>());
        }
        // 初始状态：所有盘在0号柱
        for (int i = numDisks; i >= 1; i--) {
            pegs.get(0).push(i);
        }
    }

    /**
     * 创建状态副本（用于搜索）
     */
    public HanoiState copy() {
        HanoiState copy = new HanoiState(0, numPegs);
        copy.numDisks = this.numDisks;
        copy.pegs = new ArrayList<>();
        for (Stack<Integer> peg : this.pegs) {
            Stack<Integer> newPeg = new Stack<>();
            newPeg.addAll(peg);
            copy.pegs.add(newPeg);
        }
        return copy;
    }

    /**
     * 执行移动操作
     */
    public boolean move(int from, int to) {
        if (from < 0 || from >= numPegs || to < 0 || to >= numPegs) return false;
        if (pegs.get(from).isEmpty()) return false;
        int disk = pegs.get(from).peek();
        if (!pegs.get(to).isEmpty() && pegs.get(to).peek() < disk) return false;

        pegs.get(from).pop();
        pegs.get(to).push(disk);
        return true;
    }

    /**
     * 检查是否达成目标
     */
    public boolean isGoal(int targetPeg) {
        return pegs.get(targetPeg).size() == numDisks;
    }

    /**
     * 生成状态的唯一键（用于记忆化）
     */
    public String getKey() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < numPegs; i++) {
            sb.append("[");
            for (int disk : pegs.get(i)) {
                sb.append(disk).append(",");
            }
            sb.append("]");
        }
        return sb.toString();
    }

    public List<Stack<Integer>> getPegs() { return pegs; }
    public int getNumPegs() { return numPegs; }
    public int getNumDisks() { return numDisks; }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < numPegs; i++) {
            sb.append("柱").append(i).append(": ");
            sb.append(pegs.get(i).toString()).append("\n");
        }
        return sb.toString();
    }
}

/**
 * 移动步骤记录
 */
public class Move {
    int from, to, disk;

    public Move(int from, int to, int disk) {
        this.from = from;
        this.to = to;
        this.disk = disk;
    }

    @Override
    public String toString() {
        return String.format("将盘 %d 从柱 %d 移到柱 %d", disk, from, to);
    }
}

三柱汉诺塔递归与记忆化

import java.util.*;

/**
 * 三柱汉诺塔求解器（经典递归 + 记忆化优化）
 */
public class ThreePegHanoi {
    private List<Move> moves = new ArrayList<>();

    /**
     * 经典递归解法
     */
    public void solveRecursive(int n, int from, int to, int aux) {
        if (n <= 0) return;
        solveRecursive(n - 1, from, aux, to);
        moves.add(new Move(from, to, n));
        solveRecursive(n - 1, aux, to, from);
    }

    public List<Move> getMoves() { return moves; }

    /**
     * 计算最少步数（公式法）
     */
    public static long minMoves(int n) {
        return (1L << n) - 1; // 2^n - 1
    }
}

四柱汉诺塔记忆化搜索（Frame-Stewart算法）

import java.util.*;

/**
 * 四柱汉诺塔记忆化搜索求解器
 */
public class FourPegHanoi {
    // 记忆化缓存：key="n_disks,num_pegs" -> 最优步数
    private Map<String, Long> memo = new HashMap<>();
    // 缓存最优分割点
    private Map<String, Integer> bestK = new HashMap<>();

    /**
     * 计算n个盘在m个柱上的最少移动步数（Frame-Stewart算法）
     */
    public long solve(int n, int m) {
        if (n <= 0) return 0;
        if (m <= 2) return Long.MAX_VALUE; // 至少需要3根柱
        if (m == 3) return (1L << n) - 1; // 三柱公式

        String key = n + "," + m;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }

        long minSteps = Long.MAX_VALUE;
        int optimalK = 1;

        // 枚举分割点k（将n个盘分为上k个和下n-k个）
        for (int k = 1; k < n; k++) {
            // 步骤1：用m根柱移动上k个到辅助柱
            long steps1 = solve(k, m);
            // 步骤2：用m-1根柱（一根被占用）移动下n-k个到目标柱
            long steps2 = solve(n - k, m - 1);
            // 步骤3：用m根柱将上k个从辅助柱移到目标柱
            long steps3 = solve(k, m);

            long total = steps1 + steps2 + steps3;
            if (total < minSteps) {
                minSteps = total;
                optimalK = k;
            }
        }

        memo.put(key, minSteps);
        bestK.put(key, optimalK);
        return minSteps;
    }

    /**
     * 生成完整的移动步骤（带路径重建）
     */
    public List<Move> generateMoves(int n, int from, int to, int[] auxPegs) {
        List<Move> moves = new ArrayList<>();
        generateMovesHelper(n, from, to, auxPegs, moves);
        return moves;
    }

    private void generateMovesHelper(int n, int from, int to, int[] auxPegs, List<Move> moves) {
        if (n <= 0) return;
        if (auxPegs.length == 0) {
            // 无辅助柱，直接移动
            moves.add(new Move(from, to, n));
            return;
        }
        if (auxPegs.length == 1) {
            // 一根辅助柱，使用经典三柱递归
            threePegHelper(n, from, to, auxPegs[0], moves);
            return;
        }

        // 多辅助柱：使用Frame-Stewart分割
        int m = auxPegs.length + 2; // 总柱数
        String key = n + "," + m;
        int k = bestK.getOrDefault(key, Math.max(1, n / 2));

        // 选择一个辅助柱作为"临时目标"
        int tempTarget = auxPegs[0];
        int[] remainingAux = Arrays.copyOfRange(auxPegs, 1, auxPegs.length);
        int[] auxWithTarget = new int[auxPegs.length];
        auxWithTarget[0] = to;
        System.arraycopy(auxPegs, 1, auxWithTarget, 1, auxPegs.length - 1);

        // 步骤1：移动上k个到临时目标
        generateMovesHelper(k, from, tempTarget, remainingAux, moves);
        // 步骤2：移动下n-k个到目标（少一个辅助柱）
        generateMovesHelper(n - k, from, to, remainingAux, moves);
        // 步骤3：将上k个从临时目标移到最终目标
        generateMovesHelper(k, tempTarget, to, remainingAux, moves);
    }

    private void threePegHelper(int n, int from, int to, int aux, List<Move> moves) {
        if (n <= 0) return;
        threePegHelper(n - 1, from, aux, to, moves);
        moves.add(new Move(from, to, n));
        threePegHelper(n - 1, aux, to, from, moves);
    }

    /**
     * 打印最优分割策略
     */
    public void printOptimalStrategy(int n, int m) {
        System.out.println("四柱汉诺塔最优策略分析（" + n + "盘，" + m + "柱）：");
        System.out.println("最少步数: " + solve(n, m));

        for (int i = 1; i <= n; i++) {
            String key = i + "," + m;
            Integer k = bestK.get(key);
            if (k != null) {
                System.out.printf("  %d盘: 最优分割k=%d, 步数=%d%n", 
                    i, k, solve(i, m));
            }
        }
    }
}

状态空间BFS求解器（用于验证和变体问题）

import java.util.*;

/**
 * 基于状态空间BFS的汉诺塔求解器
 * 适用于带限制条件的变体问题
 */
public class HanoiBFS {

    /**
     * BFS搜索最短路径
     * @param initial 初始状态
     * @param targetPeg 目标柱编号
     * @return 最短移动序列
     */
    public List<Move> solveBFS(HanoiState initial, int targetPeg) {
        Queue<HanoiState> queue = new LinkedList<>();
        Map<String, String> parent = new HashMap<>(); // 记录前驱状态
        Map<String, Move> moveTo = new HashMap<>();   // 记录到达该状态的移动
        Set<String> visited = new HashSet<>();

        String startKey = initial.getKey();
        queue.offer(initial);
        visited.add(startKey);
        parent.put(startKey, null);

        while (!queue.isEmpty()) {
            HanoiState current = queue.poll();
            String currentKey = current.getKey();

            if (current.isGoal(targetPeg)) {
                return reconstructPath(parent, moveTo, currentKey);
            }

            // 尝试所有合法移动
            int numPegs = current.getNumPegs();
            for (int from = 0; from < numPegs; from++) {
                if (current.getPegs().get(from).isEmpty()) continue;

                for (int to = 0; to < numPegs; to++) {
                    if (from == to) continue;

                    HanoiState next = current.copy();
                    if (next.move(from, to)) {
                        String nextKey = next.getKey();
                        if (!visited.contains(nextKey)) {
                            visited.add(nextKey);
                            queue.offer(next);
                            parent.put(nextKey, currentKey);
                            int disk = current.getPegs().get(from).peek();
                            moveTo.put(nextKey, new Move(from, to, disk));
                        }
                    }
                }
            }
        }

        return null; // 无解
    }

    /**
     * 重建路径
     */
    private List<Move> reconstructPath(Map<String, String> parent, 
                                        Map<String, Move> moveTo, 
                                        String goalKey) {
        List<Move> path = new ArrayList<>();
        String current = goalKey;

        while (parent.get(current) != null) {
            path.add(moveTo.get(current));
            current = parent.get(current);
        }

        Collections.reverse(path);
        return path;
    }
}

主程序入口

/**
 * 汉诺塔算法主程序
 */
public class HanoiSolver {
    public static void main(String[] args) {
        System.out.println("=== 三柱汉诺塔（经典递归）===");
        int n3 = 5;
        ThreePegHanoi threePeg = new ThreePegHanoi();
        threePeg.solveRecursive(n3, 0, 2, 1);
        System.out.println(n3 + "盘最少步数: " + ThreePegHanoi.minMoves(n3));
        System.out.println("移动步骤:");
        for (Move m : threePeg.getMoves()) {
            System.out.println("  " + m);
        }

        System.out.println("\n=== 四柱汉诺塔（Frame-Stewart + 记忆化）===");
        int n4 = 10;
        FourPegHanoi fourPeg = new FourPegHanoi();
        fourPeg.printOptimalStrategy(n4, 4);

        // 对比三柱与四柱的步数
        System.out.println("\n步数对比（" + n4 + "盘）：");
        System.out.println("  三柱: " + ((1L << n4) - 1));
        System.out.println("  四柱: " + fourPeg.solve(n4, 4));

        System.out.println("\n=== 状态空间BFS验证（3盘3柱）===");
        HanoiState initial = new HanoiState(3, 3);
        HanoiBFS bfs = new HanoiBFS();
        List<Move> bfsPath = bfs.solveBFS(initial, 2);
        System.out.println("BFS最短路径长度: " + bfsPath.size());
        for (Move m : bfsPath) {
            System.out.println("  " + m);
        }

        // 性能测试：记忆化 vs 无记忆化
        System.out.println("\n=== 性能测试：四柱15盘 ===");
        long start = System.currentTimeMillis();
        long steps15 = fourPeg.solve(15, 4);
        long time = System.currentTimeMillis() - start;
        System.out.println("15盘四柱最少步数: " + steps15);
        System.out.println("计算耗时: " + time + "ms");
    }
}

算法复杂度分析

其中四柱记忆化搜索通过缓存子问题解，将原本指数级的递归降至多项式级。

总结

本文通过Java实现了多种汉诺塔求解策略，核心要点包括：

• 记忆化搜索将四柱汉诺塔的指数级复杂度降至多项式级
• Frame-Stewart算法为多柱问题提供了最优分割策略
• 状态空间BFS可处理带限制条件的变体问题
• 动态规划思想通过缓存子问题解避免重复计算

读者可以尝试扩展至五柱、六柱汉诺塔，或引入额外的移动限制（如不允许大盘压小盘以外的特定规则），进一步探索状态空间的动态规划解法。