每日算法 — 使用java实现数字华容道：IDA*迭代深化与线性冲突启发式

引言

数字华容道（15-Puzzle）是经典的滑块拼图游戏。由于其状态空间高达 $16! \approx 2 \times 10^{13}$，盲目搜索无法求解。IDA（Iterative Deepening A）算法以极低的内存开销和完备的最优性保证成为解决该问题的首选方案。本文使用Java实现IDA，并引入线性冲突（Linear Conflict）*启发式，让估计值更接近真实代价，大幅减少搜索节点数。

算法核心思想

为什么选IDA*？

IDA结合了两者的优点：迭代加深保证内存 $O(d)$，A的f值剪枝保证效率。

启发式函数设计

曼哈顿距离（Manhattan Distance）

$$h_1 = \sum_{i} |r_i – r_{goal}| + |c_i – c_{goal}|$$

线性冲突（Linear Conflict）

当两个方块在同一行/列，且目标位置也在同一行/列，但它们的目标顺序相反时，产生线性冲突。每对冲突至少增加2步代价：

$$h_2 = h_1 + 2 \times (\text{行冲突数} + \text{列冲突数})$$

线性冲突保证启发式可采纳（admissible）且一致性（consistent）。

可解性判定

对于 $N \times N$ 拼图，状态可解的充要条件：
– 若网格宽度为奇数：逆序对数为偶数
– 若网格宽度为偶数：逆序对数的奇偶性与空格所在行（从底部数）的奇偶性相反

Java实现

核心状态表示

import java.util.*;

public class IDAStar15Puzzle {
    static final int N = 4;          // 4x4 拼图
    static final int SIZE = N * N;
    static final int[] GOAL = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0};

    // 预计算每个数字的目标位置
    static final int[][] GOAL_POS = new int[SIZE][2];
    static {
        for (int i = 0; i < SIZE; i++) {
            if (GOAL[i] == 0) continue;
            GOAL_POS[GOAL[i]][0] = i / N; // row
            GOAL_POS[GOAL[i]][1] = i % N; // col
        }
    }

    // 方向：上、下、左、右
    static final int[] DR = {-1, 1, 0, 0};
    static final int[] DC = {0, 0, -1, 1};
    static final String[] DIR_NAME = {"U", "D", "L", "R"};

    int[] board;       // 当前状态
    int blankRow, blankCol;
    int nodesExpanded; // 统计搜索节点数
    String solution;   // 解路径

    public IDAStar15Puzzle(int[] initial) {
        this.board = initial.clone();
        for (int i = 0; i < SIZE; i++) {
            if (initial[i] == 0) {
                blankRow = i / N;
                blankCol = i % N;
            }
        }
    }

可解性检测

    /**
     * 检测拼图是否可解
     */
    boolean isSolvable() {
        int inversions = 0;
        for (int i = 0; i < SIZE; i++) {
            if (board[i] == 0) continue;
            for (int j = i + 1; j < SIZE; j++) {
                if (board[j] != 0 && board[i] > board[j]) {
                    inversions++;
                }
            }
        }

        // 4x4拼图：宽度为偶数
        // 可解条件：逆序数奇偶性与空格从底部数行号奇偶性相反
        int blankRowFromBottom = N - blankRow;
        return (inversions % 2) != (blankRowFromBottom % 2);
    }

启发式函数

    /**
     * 计算曼哈顿距离
     */
    int manhattanDistance(int[] state) {
        int dist = 0;
        for (int i = 0; i < SIZE; i++) {
            int val = state[i];
            if (val == 0) continue;
            int goalR = GOAL_POS[val][0];
            int goalC = GOAL_POS[val][1];
            int curR = i / N;
            int curC = i % N;
            dist += Math.abs(curR - goalR) + Math.abs(curC - goalC);
        }
        return dist;
    }

    /**
     * 计算线性冲突附加代价
     * 线性冲突：同一行/列中两个方块目标也在同行/列但顺序相反
     */
    int linearConflict(int[] state) {
        int conflicts = 0;

        // 行冲突
        for (int r = 0; r < N; r++) {
            for (int c1 = 0; c1 < N; c1++) {
                int val1 = state[r * N + c1];
                if (val1 == 0) continue;
                int goalR1 = GOAL_POS[val1][0];
                if (goalR1 != r) continue; // 不在目标行

                for (int c2 = c1 + 1; c2 < N; c2++) {
                    int val2 = state[r * N + c2];
                    if (val2 == 0) continue;
                    int goalR2 = GOAL_POS[val2][0];
                    int goalC2 = GOAL_POS[val2][1];
                    if (goalR2 != r) continue;
                    // 两者目标都在同一行，检查列顺序
                    if (GOAL_POS[val1][1] > goalC2) {
                        conflicts++;
                    }
                }
            }
        }

        // 列冲突
        for (int c = 0; c < N; c++) {
            for (int r1 = 0; r1 < N; r1++) {
                int val1 = state[r1 * N + c];
                if (val1 == 0) continue;
                int goalC1 = GOAL_POS[val1][1];
                if (goalC1 != c) continue;

                for (int r2 = r1 + 1; r2 < N; r2++) {
                    int val2 = state[r2 * N + c];
                    if (val2 == 0) continue;
                    int goalC2 = GOAL_POS[val2][1];
                    int goalR2 = GOAL_POS[val2][0];
                    if (goalC2 != c) continue;
                    if (GOAL_POS[val1][0] > goalR2) {
                        conflicts++;
                    }
                }
            }
        }

        return conflicts * 2; // 每对冲突至少额外2步
    }

    /**
     * 总启发式 = 曼哈顿距离 + 线性冲突
     */
    int heuristic(int[] state) {
        return manhattanDistance(state) + linearConflict(state);
    }

IDA*核心搜索

    /**
     * IDA*主入口
     */
    boolean solve() {
        if (!isSolvable()) {
            System.out.println("该拼图不可解!");
            return false;
        }

        int threshold = heuristic(board);
        nodesExpanded = 0;

        while (true) {
            int nextThreshold = Integer.MAX_VALUE;
            int result = search(board, blankRow, blankCol, 0, threshold, -1, "");

            if (result == -1) { // 找到解
                System.out.println("找到最优解! 长度: " + solution.length() + 
                                 ", 扩展节点: " + nodesExpanded);
                return true;
            }
            if (result == Integer.MAX_VALUE) {
                System.out.println("搜索失败");
                return false;
            }
            threshold = result;
            System.out.println("提升阈值至: " + threshold);
        }
    }

    /**
     * 深度优先搜索，f值超过threshold时剪枝并返回最小超出的f值
     * @param prevDir 上一步的方向索引，避免回退
     * @return -1表示找到解，其他值表示下一轮阈值
     */
    int search(int[] state, int br, int bc, int g, int threshold, int prevDir, String path) {
        int f = g + heuristic(state);
        if (f > threshold) return f;
        if (isGoal(state)) {
            solution = path;
            return -1;
        }

        nodesExpanded++;
        int minExceed = Integer.MAX_VALUE;

        for (int dir = 0; dir < 4; dir++) {
            // 避免立即回退
            if (prevDir != -1 && isOpposite(dir, prevDir)) continue;

            int nr = br + DR[dir];
            int nc = bc + DC[dir];
            if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;

            // 执行移动：空格与目标位置交换
            int[] newState = state.clone();
            int oldIdx = br * N + bc;
            int newIdx = nr * N + nc;
            newState[oldIdx] = newState[newIdx];
            newState[newIdx] = 0;

            int result = search(newState, nr, nc, g + 1, threshold, dir, path + DIR_NAME[dir]);

            if (result == -1) return -1; // 找到解，向上传播
            if (result < minExceed) minExceed = result;
        }

        return minExceed;
    }

    boolean isOpposite(int d1, int d2) {
        return (d1 == 0 && d2 == 1) || (d1 == 1 && d2 == 0) ||
               (d1 == 2 && d2 == 3) || (d1 == 3 && d2 == 2);
    }

    boolean isGoal(int[] state) {
        return Arrays.equals(state, GOAL);
    }

运行演示与测试

    /**
     * 生成随机可解状态（通过从目标状态随机移动）
     */
    static int[] generateRandomState(int moves) {
        int[] state = GOAL.clone();
        int br = N - 1, bc = N - 1;
        Random rand = new Random();
        int prevDir = -1;

        for (int i = 0; i < moves; i++) {
            List<Integer> valid = new ArrayList<>();
            for (int d = 0; d < 4; d++) {
                if (prevDir != -1 && ((d == 0 && prevDir == 1) || (d == 1 && prevDir == 0) ||
                    (d == 2 && prevDir == 3) || (d == 3 && prevDir == 2))) continue;
                int nr = br + DR[d];
                int nc = bc + DC[d];
                if (nr >= 0 && nr < N && nc >= 0 && nc < N) valid.add(d);
            }
            int dir = valid.get(rand.nextInt(valid.size()));
            int oldIdx = br * N + bc;
            int newIdx = (br + DR[dir]) * N + (bc + DC[dir]);
            state[oldIdx] = state[newIdx];
            state[newIdx] = 0;
            br += DR[dir];
            bc += DC[dir];
            prevDir = dir;
        }
        return state;
    }

    void printState(int[] state) {
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                int v = state[r * N + c];
                System.out.printf(v == 0 ? "   " : "%2d ", v);
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        // 生成一个通过50步随机移动打乱的状态
        int[] initial = generateRandomState(50);

        IDAStar15Puzzle puzzle = new IDAStar15Puzzle(initial);
        System.out.println("初始状态:");
        puzzle.printState(initial);
        System.out.println("曼哈顿距离: " + puzzle.manhattanDistance(initial));
        System.out.println("线性冲突: " + puzzle.linearConflict(initial));
        System.out.println("总启发式: " + puzzle.heuristic(initial));
        System.out.println("可解性: " + puzzle.isSolvable());
        System.out.println();

        long start = System.currentTimeMillis();
        boolean solved = puzzle.solve();
        long end = System.currentTimeMillis();

        if (solved) {
            System.out.println("解路径: " + puzzle.solution);
            System.out.println("耗时: " + (end - start) + "ms");
        }
    }

复杂度分析

实验数据表明，相比纯曼哈顿距离，线性冲突启发式可减少 50%~70% 的搜索节点。

总结

本文实现了完整的数字华容道求解器，核心贡献包括：
1. IDA*框架：以 $O(d)$ 内存找到最优解
2. 线性冲突启发式：在不破坏可采纳性的前提下显著提升剪枝效率
3. 可解性预判定：避免在不可解实例上浪费计算资源

读者可进一步探索模式数据库（Pattern Database）启发式——通过预计算子问题的精确代价，将15-Puzzle的平均求解时间压缩到毫秒级。模式数据库与IDA*的结合是当前该问题的最优解法。