每日算法 — 使用java实现IDA星搜索：迭代加深A星求解15数码问题

引言

IDA（Iterative Deepening A）搜索是A算法与迭代加深深度优先搜索（IDDFS）的结合体，兼具A的最优性和IDDFS的内存高效性。对于状态空间巨大但解深度适中的问题（如15数码、24数码等滑块拼图），IDA是实际求解中最有效的算法之一。本文用Java实现IDA算法求解15数码问题，深入讲解启发式函数设计与迭代加深策略。

问题定义：15数码（15-Puzzle）

一个 4×4 的棋盘上有15个数字方块和1个空白格。每次可以将与空白格相邻的数字移入空白格。目标是从初始状态通过最少步数移动到目标状态。

目标状态：

 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15  0

IDA* 算法原理

核心思想

IDA 用深度优先搜索代替A的优先队列，但限制搜索深度为阈值 f_limit。如果某节点的 f = g + h 超过阈值，则记录最小超出值作为下一轮阈值。

f(n) = g(n) + h(n)
- g(n)：从起点到n的实际代价（步数）
- h(n)：从n到目标的估计代价（启发函数）

迭代加深过程

1. 初始阈值 threshold = h(start)
2. 执行深度优先搜索，只扩展 f ≤ threshold 的节点
3. 如果找到解，返回
4. 否则，将 threshold 更新为本次搜索中遇到的最小 f 值（且大于原threshold）
5. 重复步骤2-4

启发式函数：曼哈顿距离

对于每个数字方块，计算其当前位置到目标位置的水平+垂直距离之和。曼哈顿距离是15数码问题的可采纳启发式（admissible heuristic），不会高估实际代价。

h(state) = Σ |当前行 - 目标行| + |当前列 - 目标列|
           对于所有非零数字

Java实现

public class IDAStar15Puzzle {

    private static final int N = 4;           // 棋盘大小
    private static final int NN = N * N;      // 总格子数
    private static final int[] dr = {-1, 1, 0, 0}; // 上、下、左、右
    private static final int[] dc = {0, 0, -1, 1};
    private static final String[] moveNames = {"Up", "Down", "Left", "Right"};

    private int[] board;      // 一维表示棋盘
    private int blankPos;     // 空白格位置
    private int[] goalPos;    // 每个数字的目标位置（一维）
    private int[] path;       // 记录移动路径
    private boolean solved;   // 是否找到解

    public IDAStar15Puzzle(int[] initial) {
        this.board = initial.clone();
        this.goalPos = new int[NN];
        this.path = new int[100]; // 最大搜索深度

        // 预计算每个数字的目标位置
        for (int i = 0; i < NN; i++) {
            goalPos[i] = i; // 数字i的目标位置就是i（0在右下角）
        }

        // 找到空白格位置
        for (int i = 0; i < NN; i++) {
            if (board[i] == 0) {
                blankPos = i;
                break;
            }
        }
    }

    /**
     * 计算曼哈顿距离启发式
     */
    private int manhattanDistance() {
        int dist = 0;
        for (int i = 0; i < NN; i++) {
            if (board[i] != 0) {
                int targetRow = board[i] / N;
                int targetCol = board[i] % N;
                int curRow = i / N;
                int curCol = i % N;
                dist += Math.abs(curRow - targetRow) + Math.abs(curCol - targetCol);
            }
        }
        return dist;
    }

    /**
     * 线性冲突启发式（增强版曼哈顿距离）
     * 如果两个方块在同一行/列，且目标也在同一行/列，但顺序相反，
     * 则至少还需要额外2步来交换它们
     */
    private int linearConflict() {
        int dist = manhattanDistance();

        // 行冲突
        for (int row = 0; row < N; row++) {
            for (int i = 0; i < N; i++) {
                for (int j = i + 1; j < N; j++) {
                    int pos1 = row * N + i;
                    int pos2 = row * N + j;
                    int val1 = board[pos1];
                    int val2 = board[pos2];

                    if (val1 != 0 && val2 != 0 &&
                        val1 / N == row && val2 / N == row &&
                        val1 > val2) {
                        dist += 2;
                    }
                }
            }
        }

        // 列冲突
        for (int col = 0; col < N; col++) {
            for (int i = 0; i < N; i++) {
                for (int j = i + 1; j < N; j++) {
                    int pos1 = i * N + col;
                    int pos2 = j * N + col;
                    int val1 = board[pos1];
                    int val2 = board[pos2];

                    if (val1 != 0 && val2 != 0 &&
                        val1 % N == col && val2 % N == col &&
                        val1 > val2) {
                        dist += 2;
                    }
                }
            }
        }

        return dist;
    }

    /**
     * 可解性判断：计算逆序对数
     * 对于N×N拼图，当N为奇数时逆序对数必须为偶数；
     * 当N为偶数时，逆序对数奇偶性与空白格从底部数的行号相关
     */
    public boolean isSolvable() {
        int inversions = 0;
        for (int i = 0; i < NN; i++) {
            if (board[i] == 0) continue;
            for (int j = i + 1; j < NN; j++) {
                if (board[j] != 0 && board[i] > board[j]) {
                    inversions++;
                }
            }
        }

        int blankRowFromBottom = N - (blankPos / N);

        if (N % 2 == 1) {
            return inversions % 2 == 0;
        } else {
            return (inversions + blankRowFromBottom) % 2 == 1;
        }
    }

    /**
     * IDA* 核心搜索
     */
    public boolean solve() {
        if (!isSolvable()) {
            System.out.println("该状态无解！");
            return false;
        }

        int threshold = linearConflict();
        System.out.println("初始启发值: " + threshold);

        while (!solved && threshold < Integer.MAX_VALUE / 2) {
            int newThreshold = search(0, threshold, -1);
            if (solved) {
                return true;
            }
            threshold = newThreshold;
            System.out.println("提升阈值到: " + threshold);
        }

        return false;
    }

    /**
     * 深度优先搜索，返回下一个阈值
     * @param g 当前深度
     * @param threshold 当前阈值
     * @param lastMove 上一步移动的反方向（避免立即回退）
     * @return 如果找到解返回0；否则返回下一个最小阈值
     */
    private int search(int g, int threshold, int lastMove) {
        int f = g + linearConflict();

        if (f > threshold) {
            return f; // 超出阈值，返回当前f值作为候选新阈值
        }

        // 检查是否到达目标状态
        if (linearConflict() == 0) {
            solved = true;
            System.out.println("找到解！步数: " + g);
            printPath(g);
            return 0;
        }

        int minNextThreshold = Integer.MAX_VALUE;
        int blankRow = blankPos / N;
        int blankCol = blankPos % N;

        for (int dir = 0; dir < 4; dir++) {
            // 避免立即回退上一步
            if (lastMove != -1 && dir == (lastMove ^ 1)) {
                continue;
            }

            int newRow = blankRow + dr[dir];
            int newCol = blankCol + dc[dir];

            // 边界检查
            if (newRow < 0 || newRow >= N || newCol < 0 || newCol >= N) {
                continue;
            }

            int newPos = newRow * N + newCol;

            // 执行移动：交换空白格和相邻数字
            swap(blankPos, newPos);
            blankPos = newPos;
            path[g] = dir;

            int result = search(g + 1, threshold, dir);

            if (solved) {
                return 0;
            }

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

            // 回溯
            blankPos = blankRow * N + blankCol;
            swap(blankPos, newPos);
        }

        return minNextThreshold;
    }

    private void swap(int i, int j) {
        int temp = board[i];
        board[i] = board[j];
        board[j] = temp;
    }

    private void printPath(int steps) {
        System.out.print("移动序列: ");
        for (int i = 0; i < steps; i++) {
            System.out.print(moveNames[path[i]] + " ");
        }
        System.out.println();
    }

    public void printBoard() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.printf("%3d", board[i * N + j]);
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        // 一个中等难度的15数码实例（需要约30步）
        int[] initial = {
             1,  2,  3,  4,
             5,  6,  7,  8,
             9, 10,  0, 12,
            13, 14, 11, 15
        };

        System.out.println("初始状态:");
        IDAStar15Puzzle puzzle = new IDAStar15Puzzle(initial);
        puzzle.printBoard();

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

        System.out.println("求解结果: " + (solved ? "成功" : "失败"));
        System.out.println("耗时: " + (end - start) + " ms");
    }
}

启发式函数对比

复杂度分析

扩展应用

1. 8数码/24数码/48数码：相同的IDA*框架，仅改变棋盘大小
2. 魔方求解：Kociemba算法本质也是IDA*的扩展
3. ** Sokoban（推箱子）**：结合宏观移动（macro moves）减少分支因子
4. 路径规划：在网格地图中寻找最短路径
5. 游戏AI：实时策略游戏中的单位移动和寻路

总结

IDA搜索算法是状态空间搜索的利器，它将A的最优性与深度优先搜索的内存效率完美结合。对于15数码这类NP-hard拼图问题，IDA配合精心设计的启发式函数（如曼哈顿距离+线性冲突）能够在极短时间内求解。理解IDA的核心思想——迭代加深与阈值控制——不仅对拼图问题有帮助，也是学习更高级搜索算法（如RBFS、SMA*）的重要基础。