每日算法 — 使用java实现华容道：IDA*迭代加深搜索与模式数据库启发式

华容道是中国传统滑块拼图游戏的经典代表，其状态空间规模超过 (2.6 \times 10^{13})，远超普通BFS或A搜索在内存与时间上的可承受范围。本文用Java实现一套基于IDA（Iterative Deepening A*）的求解器，并引入模式数据库（Pattern Database）作为高阶启发式函数，在仅使用线性内存的前提下，将平均求解步数缩短至最优解附近。

一、问题建模：状态空间与合法移动

华容道的棋盘为 (4 \times 5) 网格，包含1个 (2 \times 2) 的”曹操”块、5个 (1 \times 2) 或 (2 \times 1) 的”五虎将”块、4个 (1 \times 1) 的”兵”块以及2个空格。目标是将曹操移动到棋盘正下方的出口位置。

/**
 * 华容道棋盘状态表示
 * 使用4x5的二维数组，每个格子记录占据它的方块ID
 * 0表示空格，1~10分别表示不同方块
 */
public class KlotskiState {
    public static final int ROWS = 5;
    public static final int COLS = 4;

    // 棋盘格子: board[row][col] = 方块ID
    private final byte[][] board = new byte[ROWS][COLS];

    // 曹操块的位置（左上角坐标）
    private int caoRow, caoCol;

    // 两个空格的位置
    private int empty1Row, empty1Col, empty2Row, empty2Col;

    /**
     * 从初始布局构造状态
     * layout: 5行4列的二维数组，每个元素为方块ID
     */
    public KlotskiState(byte[][] layout) {
        for (int r = 0; r < ROWS; r++) {
            System.arraycopy(layout[r], 0, board[r], 0, COLS);
        }
        locatePieces();
    }

    /**
     * 定位曹操和空格的位置
     */
    private void locatePieces() {
        int emptyCount = 0;
        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                if (board[r][c] == 1) { // 曹操块ID为1
                    if (c + 1 < COLS && board[r][c + 1] == 1 && 
                        r + 1 < ROWS && board[r + 1][c] == 1) {
                        caoRow = r;
                        caoCol = c;
                    }
                } else if (board[r][c] == 0) {
                    if (emptyCount == 0) {
                        empty1Row = r; empty1Col = c;
                    } else {
                        empty2Row = r; empty2Col = c;
                    }
                    emptyCount++;
                }
            }
        }
    }

    /**
     * 检查是否达到目标状态：曹操位于出口(3,1)即row=3,col=1
     */
    public boolean isGoal() {
        return caoRow == 3 && caoCol == 1;
    }

    /**
     * 生成所有合法的下一步状态
     * 规则：方块可以向空格方向滑动，前提是移动方向上有足够的连续空格
     */
    public List<Move> generateMoves() {
        List<Move> moves = new ArrayList<>();

        // 尝试移动曹操块(2x2)
        addCaoMoves(moves);

        // 尝试移动其他所有方块
        boolean[] visited = new boolean[11];
        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                int id = board[r][c];
                if (id > 1 && !visited[id]) {
                    visited[id] = true;
                    addPieceMoves(moves, id, r, c);
                }
            }
        }
        return moves;
    }

    /**
     * 曹操(2x2)的移动：需要2个连续空格在同一侧
     */
    private void addCaoMoves(List<Move> moves) {
        // 上移：上方两格必须都是空格
        if (caoRow > 0 && board[caoRow - 1][caoCol] == 0 && board[caoRow - 1][caoCol + 1] == 0) {
            moves.add(new Move(1, Direction.UP));
        }
        // 下移
        if (caoRow + 2 < ROWS && board[caoRow + 2][caoCol] == 0 && board[caoRow + 2][caoCol + 1] == 0) {
            moves.add(new Move(1, Direction.DOWN));
        }
        // 左移
        if (caoCol > 0 && board[caoRow][caoCol - 1] == 0 && board[caoRow + 1][caoCol - 1] == 0) {
            moves.add(new Move(1, Direction.LEFT));
        }
        // 右移
        if (caoCol + 2 < COLS && board[caoRow][caoCol + 2] == 0 && board[caoRow + 1][caoCol + 2] == 0) {
            moves.add(new Move(1, Direction.RIGHT));
        }
    }

    /**
     * 添加单个方块的合法移动
     */
    private void addPieceMoves(List<Move> moves, int pieceId, int r, int c) {
        // 判断方块形状：1x2横条、2x1竖条或1x1小兵
        boolean horizontal = (c + 1 < COLS && board[r][c + 1] == pieceId);
        boolean vertical = (r + 1 < ROWS && board[r + 1][c] == pieceId);

        if (horizontal) {
            // 1x2横条
            if (r > 0 && board[r - 1][c] == 0 && board[r - 1][c + 1] == 0)
                moves.add(new Move(pieceId, Direction.UP));
            if (r + 1 < ROWS && board[r + 1][c] == 0 && board[r + 1][c + 1] == 0)
                moves.add(new Move(pieceId, Direction.DOWN));
            if (c > 0 && board[r][c - 1] == 0)
                moves.add(new Move(pieceId, Direction.LEFT));
            if (c + 2 < COLS && board[r][c + 2] == 0)
                moves.add(new Move(pieceId, Direction.RIGHT));
        } else if (vertical) {
            // 2x1竖条
            if (r > 0 && board[r - 1][c] == 0)
                moves.add(new Move(pieceId, Direction.UP));
            if (r + 2 < ROWS && board[r + 2][c] == 0)
                moves.add(new Move(pieceId, Direction.DOWN));
            if (c > 0 && board[r][c - 1] == 0 && board[r + 1][c - 1] == 0)
                moves.add(new Move(pieceId, Direction.LEFT));
            if (c + 1 < COLS && board[r][c + 1] == 0 && board[r + 1][c + 1] == 0)
                moves.add(new Move(pieceId, Direction.RIGHT));
        } else {
            // 1x1小兵
            if (r > 0 && board[r - 1][c] == 0)
                moves.add(new Move(pieceId, Direction.UP));
            if (r + 1 < ROWS && board[r + 1][c] == 0)
                moves.add(new Move(pieceId, Direction.DOWN));
            if (c > 0 && board[r][c - 1] == 0)
                moves.add(new Move(pieceId, Direction.LEFT));
            if (c + 1 < COLS && board[r][c + 1] == 0)
                moves.add(new Move(pieceId, Direction.RIGHT));
        }
    }

    /**
     * 执行移动，返回新状态（深拷贝）
     */
    public KlotskiState applyMove(Move move) {
        KlotskiState next = new KlotskiState(this.board);
        // ... 具体移动逻辑省略，包含边界检查与状态更新
        next.locatePieces();
        return next;
    }
}

/**
 * 移动方向枚举
 */
enum Direction { UP, DOWN, LEFT, RIGHT }

/**
 * 一次移动操作
 */
record Move(int pieceId, Direction dir) {}

二、IDA*核心算法：内存受限下的最优搜索

普通A在最坏情况下需要存储整个前沿集合，华容道的状态空间规模使其不可行。IDA通过迭代加深外层循环与深度优先内层搜索的结合，将内存复杂度降至 (O(d))（(d) 为解深度），同时保留A*的最优性保证。

/**
 * IDA*求解器
 * 核心思想：外层循环不断增加f值阈值threshold，
 * 内层DFS只探索f(s) = g(s) + h(s) <= threshold的节点
 */
public class IDAStarSolver {

    private final Heuristic heuristic;
    private int nodesExpanded = 0;
    private int maxDepthReached = 0;

    // 当前阈值，每次迭代后更新为超过阈值的最小f值
    private int threshold;

    // 记录路径，避免循环
    private final List<Move> path = new ArrayList<>();

    public IDAStarSolver(Heuristic heuristic) {
        this.heuristic = heuristic;
    }

    /**
     * 启动IDA*搜索，返回从初始状态到目标状态的最短移动序列
     */
    public List<Move> solve(KlotskiState initial) {
        // 初始阈值设为启发式估计值
        threshold = heuristic.estimate(initial);

        while (true) {
            nodesExpanded = 0;
            int nextThreshold = Integer.MAX_VALUE;

            int result = search(initial, 0, nextThreshold);

            if (result == FOUND) {
                return new ArrayList<>(path);
            }
            if (result == Integer.MAX_VALUE) {
                return null; // 无解
            }

            threshold = result; // 下次迭代使用新的阈值
            System.out.println("阈值提升至: " + threshold + ", 本轮扩展节点: " + nodesExpanded);
        }
    }

    private static final int FOUND = -1;

    /**
     * 深度优先搜索，返回下一个阈值或FOUND
     * @param state 当前状态
     * @param g 已走步数（实际代价）
     * @param nextThreshold 用于记录超过当前阈值的最小f值
     */
    private int search(KlotskiState state, int g, int nextThreshold) {
        int f = g + heuristic.estimate(state);

        if (f > threshold) {
            return f; // 超出当前阈值，返回此节点的f值供外层更新阈值
        }

        if (state.isGoal()) {
            return FOUND; // 找到目标
        }

        nodesExpanded++;
        maxDepthReached = Math.max(maxDepthReached, g);

        int minOverThreshold = Integer.MAX_VALUE;

        for (Move move : state.generateMoves()) {
            // 剪枝：避免立即回退上一步（与上一步相反的方向移动同一方块）
            if (!path.isEmpty() && isReverseMove(path.get(path.size() - 1), move)) {
                continue;
            }

            KlotskiState next = state.applyMove(move);
            path.add(move);

            int result = search(next, g + 1, nextThreshold);

            if (result == FOUND) {
                return FOUND;
            }

            if (result < minOverThreshold) {
                minOverThreshold = result;
            }

            path.remove(path.size() - 1); // 回溯
        }

        return minOverThreshold;
    }

    /**
     * 判断两次移动是否互为逆操作
     */
    private boolean isReverseMove(Move last, Move current) {
        if (last.pieceId() != current.pieceId()) return false;
        return (last.dir() == Direction.UP && current.dir() == Direction.DOWN) ||
               (last.dir() == Direction.DOWN && current.dir() == Direction.UP) ||
               (last.dir() == Direction.LEFT && current.dir() == Direction.RIGHT) ||
               (last.dir() == Direction.RIGHT && current.dir() == Direction.LEFT);
    }

    public int getNodesExpanded() {
        return nodesExpanded;
    }
}

三、模式数据库启发式：打破曼哈顿距离的局限

简单的曼哈顿距离或”阻挡块数”启发式在华容道中往往严重低估真实代价，导致搜索效率低下。模式数据库（Pattern Database, PDB）的核心思想是：从目标状态反向BFS，预计算子问题的最优解代价，运行时通过查表获得不可低估的启发值。

对华容道而言，我们将曹操块与部分关键小兵组成一个”模式”，其余方块视为不可区分的障碍物，反向搜索该模式到达各位置的最短步数。

/**
 * 模式数据库：预计算子问题的最优解代价
 * 本实现以"曹操 + 2个关键小兵"为模式，其余方块视为障碍
 */
public class PatternDatabase implements Heuristic {

    // 数据库：编码后的状态 -> 到目标的最短步数
    private final Map<Long, Byte> database = new HashMap<>();

    /**
     * 构建模式数据库
     * 从目标状态反向BFS，记录模式块到达每个布局的最短步数
     */
    public void build() {
        // 目标状态编码：曹操在出口(3,1)，小兵在合理位置
        long goal = encodeGoalState();

        Queue<long[]> queue = new ArrayDeque<>(); // [编码, 步数]
        queue.offer(new long[]{goal, 0});
        database.put(goal, (byte) 0);

        int built = 0;
        while (!queue.isEmpty()) {
            long[] curr = queue.poll();
            long state = curr[0];
            byte steps = (byte) curr[1];

            // 生成所有反向移动（等价于正向移动）
            for (long neighbor : generateNeighbors(state)) {
                if (!database.containsKey(neighbor)) {
                    database.put(neighbor, (byte) (steps + 1));
                    queue.offer(new long[]{neighbor, steps + 1});
                }
            }

            built++;
            if (built % 100000 == 0) {
                System.out.println("PDB已构建: " + built + " 个状态");
            }
        }

        System.out.println("模式数据库构建完成，共 " + database.size() + " 个状态");
    }

    /**
     * 从完整棋盘状态中提取模式并查表
     */
    @Override
    public int estimate(KlotskiState state) {
        long key = encodeState(state);
        Byte value = database.get(key);
        return value != null ? value : 0; // 若不在数据库中，返回0（保证可采纳）
    }

    /**
     * 状态编码：将曹操(2x2)位置 + 两个小兵(1x1)位置压缩为long
     * 曹操位置: 4 bits for row, 4 bits for col
     * 小兵位置: 各5 bits for cell index (0~19)
     */
    private long encodeState(KlotskiState state) {
        // 具体编码逻辑：提取曹操和特定小兵的位置
        // 返回紧凑的64位编码
        long key = 0;
        // ... 编码实现
        return key;
    }

    private long encodeGoalState() {
        // 曹操在(3,1)，小兵在目标附近的编码
        return encodeState(new KlotskiState(createGoalLayout()));
    }

    private byte[][] createGoalLayout() {
        byte[][] layout = new byte[5][4];
        // 曹操在出口位置
        layout[3][1] = 1; layout[3][2] = 1;
        layout[4][1] = 1; layout[4][2] = 1;
        return layout;
    }

    /**
     * 生成相邻状态（仅移动模式内的块）
     */
    private List<Long> generateNeighbors(long state) {
        List<Long> neighbors = new ArrayList<>();
        // 解码状态，生成所有合法移动，再编码返回
        // ...
        return neighbors;
    }
}

/**
 * 启发式接口
 */
interface Heuristic {
    int estimate(KlotskiState state);
}

四、组合启发式：多个模式数据库的取大策略

单模式数据库的覆盖范围有限。实践中常构建多个不重叠的模式（如”曹操+左侧小兵”、”曹操+右侧小兵”），运行时对多个PDB分别查表，取最大值作为最终启发值。这仍然保证可采纳性，且更接近真实代价。

/**
 * 组合启发式：聚合多个模式数据库，取最大值
 */
public class CombinedHeuristic implements Heuristic {
    private final List<PatternDatabase> databases;

    public CombinedHeuristic(PatternDatabase... dbs) {
        this.databases = Arrays.asList(dbs);
    }

    @Override
    public int estimate(KlotskiState state) {
        int maxH = 0;
        for (PatternDatabase pdb : databases) {
            maxH = Math.max(maxH, pdb.estimate(state));
        }
        return maxH;
    }
}

五、主程序与运行演示

public class KlotskiSolver {

    /**
     * "横刀立马"经典开局布局
     * 1=曹操(2x2), 2~6=五虎将(1x2或2x1), 7~10=小兵(1x1), 0=空格
     */
    public static byte[][] HENG_DAO_LI_MA = {
        {2, 1, 1, 3},
        {2, 1, 1, 3},
        {4, 5, 5, 6},
        {4, 0, 0, 6},
        {7, 8, 9, 10}
    };

    public static void main(String[] args) {
        System.out.println("=== 华容道IDA*求解器 ===\n");

        // 构建模式数据库（只需执行一次，可序列化保存）
        PatternDatabase pdb1 = new PatternDatabase();
        PatternDatabase pdb2 = new PatternDatabase();
        System.out.println("正在构建模式数据库...");
        pdb1.build(); // 曹操+左侧小兵
        pdb2.build(); // 曹操+右侧小兵

        Heuristic heuristic = new CombinedHeuristic(pdb1, pdb2);

        // 创建初始状态
        KlotskiState initial = new KlotskiState(HENG_DAO_LI_MA);
        System.out.println("初始启发值: " + heuristic.estimate(initial));

        // 执行IDA*
        IDAStarSolver solver = new IDAStarSolver(heuristic);
        long start = System.currentTimeMillis();
        List<Move> solution = solver.solve(initial);
        long elapsed = System.currentTimeMillis() - start;

        if (solution != null) {
            System.out.println("\n求解成功！");
            System.out.println("最优步数: " + solution.size());
            System.out.println("总扩展节点: " + solver.getNodesExpanded());
            System.out.println("耗时: " + elapsed + "ms");
            System.out.println("\n移动序列:");
            for (int i = 0; i < solution.size(); i++) {
                System.out.printf("%2d: 方块%d %s%n", i + 1, 
                    solution.get(i).pieceId(), solution.get(i).dir());
            }
        } else {
            System.out.println("无解");
        }
    }
}

六、复杂度分析

七、关键技巧与工程细节

1. 增量阈值更新

IDA外层的阈值更新不是简单加1，而是取本轮搜索中所有超出阈值节点的最小f值*。这保证了每次迭代至少有一个新节点被探索，避免冗余。

2. 移动对称性剪枝

华容道中同一方块向同一方向连续移动两次等价于直接移动两格（如果空间允许），但更关键的是禁止立即回退：如果上一步将方块A向上移动，下一步立即将A向下移动必然导致循环，应在生成阶段直接剪除。

3. 模式数据库的持久化

PDB构建可能需要数分钟到数小时，构建完成后应通过Java序列化或自定义二进制格式保存到磁盘，避免每次求解重复构建。

4. 状态编码优化

使用紧凑的long类型而非字符串或对象作为HashMap键，可显著降低PDB的内存占用。曹操位置（16种）× 小兵位置组合经优化编码后，单个PDB通常只需几十MB内存。

八、扩展方向

1. ** Disjoint Pattern Databases**：将方块划分为互不重叠的组，各组独立建库，运行时启发值相加而非取大，可提供更紧的下界。
2. 动态模式数据库：求解过程中在线学习新的模式代价，逐步提升启发式精度。
3. 双向IDA*：从初始状态和目标状态同时迭代加深搜索，在中间相遇，可进一步降低搜索深度。
4. 并行搜索：IDA*的每次迭代内部可并行化，现代多核CPU可显著加速大规模PDB查询。