每日算法 — 使用java实现推箱子：禁忌搜索与局部最优规避策略

引言

推箱子（Sokoban）是经典的NP-hard益智游戏，玩家控制角色将箱子推到指定目标位置。尽管BFS、A和IDA等算法已在该领域广泛应用，但当问题规模增大时，这些精确算法往往面临状态空间爆炸的困境。本文将用Java实现基于禁忌搜索（Tabu Search）的推箱子求解器，讲解如何通过局部搜索与记忆机制规避局部最优，在可接受时间内获得高质量近似解。

问题分析

推箱子的NP-hard特性

• 状态空间随箱子和空格数量指数增长
• 存在大量”死锁”状态（箱子无法到达任何目标）
• 传统精确算法在复杂关卡（超过20个箱子）时往往超时

禁忌搜索的优势

禁忌搜索是一种元启发式算法，核心思想：
1. 从初始解出发进行局部邻域搜索
2. 维护一个”禁忌表”记录近期访问过的解或移动
3. 允许暂时接受劣解，以跳出局部最优
4. 通过多样化策略和集中化策略平衡探索与利用

核心算法设计

状态表示

• 玩家位置 (px, py)
• 每个箱子的位置集合
• 静态地图：墙、目标点、空地

邻域操作

从当前玩家位置出发，执行一次有效推箱动作，得到新状态。

评估函数

综合考虑以下因素：
– 每个箱子到最近目标点的曼哈顿距离之和
– 已到达目标的箱子数量（奖励）
– 死锁惩罚（箱子贴墙且无目标）
– 步数惩罚

禁忌表设计

记录近期执行过的”推箱动作”（箱子ID + 推动方向），在一定迭代次数内禁止重复执行相同的推动动作。

完整Java实现

package sokoban.tabu;

import java.util.*;

/**
 * 推箱子 - 禁忌搜索与局部最优规避求解器
 * 
 * 核心功能：
 * 1. 推箱子游戏的状态建模与快速哈希
 * 2. 基于曼哈顿距离与死锁检测的启发式评估
 * 3. 禁忌搜索邻域生成与禁忌表管理
 * 4. 自适应迭代策略与多样化重启机制
 */
public class SokobanTabuSearch {

    // 地图元素
    public static final char WALL = '#';
    public static final char EMPTY = ' ';
    public static final char TARGET = '.';
    public static final char BOX = '$';
    public static final char BOX_ON_TARGET = '*';
    public static final char PLAYER = '@';
    public static final char PLAYER_ON_TARGET = '+';

    // 方向
    private static final int[][] DIRS = {{-1,0},{1,0},{0,-1},{0,1}};
    private static final String[] DIR_NAMES = {"UP","DOWN","LEFT","RIGHT"};

    /**
     * 游戏状态（不可变，便于哈希）
     */
    public static class State {
        public final int playerRow, playerCol;
        public final Set<Long> boxPositions; // 用long编码位置: row * 1000 + col
        public final State parent;
        public final String move; // 到达此状态的移动描述
        public final int depth;

        public State(int pr, int pc, Set<Long> boxes, State parent, String move, int depth) {
            this.playerRow = pr;
            this.playerCol = pc;
            this.boxPositions = Collections.unmodifiableSet(new HashSet<>(boxes));
            this.parent = parent;
            this.move = move;
            this.depth = depth;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof State)) return false;
            State s = (State) o;
            return playerRow == s.playerRow && playerCol == s.playerCol
                && boxPositions.equals(s.boxPositions);
        }

        @Override
        public int hashCode() {
            return Objects.hash(playerRow, playerCol, boxPositions);
        }
    }

    /**
     * 一次推箱动作
     */
    public static class Push {
        public final long boxPos;       // 箱子的位置编码
        public final int dir;           // 推动方向索引
        public final int boxRow, boxCol; // 箱子坐标
        public final int newRow, newCol; // 箱子新坐标

        public Push(long boxPos, int dir, int br, int bc, int nr, int nc) {
            this.boxPos = boxPos;
            this.dir = dir;
            this.boxRow = br;
            this.boxCol = bc;
            this.newRow = nr;
            this.newCol = nc;
        }

        /**
         * 禁忌表键：箱子原始位置 + 方向
         */
        public String tabuKey() {
            return boxRow + "," + boxCol + "_" + DIR_NAMES[dir];
        }
    }

    private final char[][] grid;
    private final int rows, cols;
    private final Set<Long> targetPositions;
    private final int totalTargets;

    public SokobanTabuSearch(char[][] grid) {
        this.grid = grid;
        this.rows = grid.length;
        this.cols = grid[0].length;
        this.targetPositions = new HashSet<>();

        // 收集所有目标点位置
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == TARGET || grid[r][c] == PLAYER_ON_TARGET
                    || grid[r][c] == BOX_ON_TARGET) {
                    targetPositions.add(encode(r, c));
                }
            }
        }
        this.totalTargets = targetPositions.size();
    }

    private static long encode(int r, int c) {
        return (long) r * 1000L + c;
    }

    private static int[] decode(long pos) {
        return new int[]{(int)(pos / 1000), (int)(pos % 1000)};
    }

    /**
     * 从地图解析初始状态
     */
    public State parseInitialState() {
        Set<Long> boxes = new HashSet<>();
        int pr = -1, pc = -1;

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                char ch = grid[r][c];
                if (ch == BOX || ch == BOX_ON_TARGET) {
                    boxes.add(encode(r, c));
                }
                if (ch == PLAYER || ch == PLAYER_ON_TARGET) {
                    pr = r;
                    pc = c;
                }
            }
        }
        return new State(pr, pc, boxes, null, null, 0);
    }

    /**
     * 启发式评估函数
     * 
     * 值越小越好。综合考虑：
     * - 箱子到目标的最小距离和
     * - 死锁惩罚
     * - 步数代价
     */
    public int evaluate(State state) {
        int distanceSum = 0;
        int onTarget = 0;
        int deadlockPenalty = 0;

        for (long boxPos : state.boxPositions) {
            int[] pos = decode(boxPos);
            int br = pos[0], bc = pos[1];

            // 已到达目标
            if (targetPositions.contains(boxPos)) {
                onTarget++;
                continue;
            }

            // 计算到最近目标的曼哈顿距离
            int minDist = Integer.MAX_VALUE;
            for (long targetPos : targetPositions) {
                int[] tp = decode(targetPos);
                int dist = Math.abs(br - tp[0]) + Math.abs(bc - tp[1]);
                minDist = Math.min(minDist, dist);
            }
            distanceSum += minDist;

            // 死锁检测：箱子贴墙且不在目标上
            if (isCornerDeadlock(br, bc, state)) {
                deadlockPenalty += 10000;
            }
        }

        // 未覆盖的目标惩罚
        int uncoveredTargets = totalTargets - onTarget;

        return distanceSum * 10 + uncoveredTargets * 500 + deadlockPenalty + state.depth;
    }

    /**
     * 角死锁检测：箱子位于角落且角落不是目标点
     */
    private boolean isCornerDeadlock(int br, int bc, State state) {
        if (targetPositions.contains(encode(br, bc))) return false;

        boolean upWall = isWall(br - 1, bc);
        boolean downWall = isWall(br + 1, bc);
        boolean leftWall = isWall(br, bc - 1);
        boolean rightWall = isWall(br, bc + 1);

        // 箱子卡在角落：上下有墙且左右至少一侧有墙，或左右有墙且上下至少一侧有墙
        return (upWall && (leftWall || rightWall)) || (downWall && (leftWall || rightWall));
    }

    private boolean isWall(int r, int c) {
        return r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] == WALL;
    }

    /**
     * 判断某个位置是否可通行（不是墙，且没有箱子）
     */
    private boolean isFree(int r, int c, State state) {
        return !isWall(r, c) && !state.boxPositions.contains(encode(r, c));
    }

    /**
     * 生成当前状态的所有合法推箱邻域
     */
    public List<Push> generatePushes(State state) {
        List<Push> pushes = new ArrayList<>();

        for (long boxPos : state.boxPositions) {
            int[] pos = decode(boxPos);
            int br = pos[0], bc = pos[1];

            for (int d = 0; d < 4; d++) {
                int dr = DIRS[d][0], dc = DIRS[d][1];
                // 玩家需要在箱子的反方向
                int playerNeedR = br - dr;
                int playerNeedC = bc - dc;
                // 箱子被推动后的新位置
                int newR = br + dr;
                int newC = bc + dc;

                // 检查：玩家能否站到推动位置，且箱子新位置有效
                if (isFree(playerNeedR, playerNeedC, state)
                    && !isWall(newR, newC)
                    && !state.boxPositions.contains(encode(newR, newC))) {
                    pushes.add(new Push(boxPos, d, br, bc, newR, newC));
                }
            }
        }

        return pushes;
    }

    /**
     * 应用推箱动作，生成新状态
     */
    public State applyPush(State state, Push push) {
        Set<Long> newBoxes = new HashSet<>(state.boxPositions);
        newBoxes.remove(push.boxPos);
        newBoxes.add(encode(push.newRow, push.newCol));

        // 玩家移动到箱子原来的位置
        int newPlayerR = push.boxRow;
        int newPlayerC = push.boxCol;

        String moveDesc = String.format("Push box at (%d,%d) %s",
            push.boxRow, push.boxCol, DIR_NAMES[push.dir]);

        return new State(newPlayerR, newPlayerC, newBoxes, state, moveDesc, state.depth + 1);
    }

    /**
     * 检查是否达到目标状态
     */
    public boolean isGoal(State state) {
        return state.boxPositions.equals(targetPositions);
    }

    /**
     * 禁忌搜索主算法
     * 
     * @param initial       初始状态
     * @param maxIter       最大迭代次数
     * @param tabuTenure    禁忌长度（迭代次数）
     * @return 找到的最佳状态
     */
    public State tabuSearch(State initial, int maxIter, int tabuTenure) {
        State bestState = initial;
        int bestEval = evaluate(initial);

        State current = initial;
        int currentEval = bestEval;

        // 禁忌表：记录最近被禁止的动作及其剩余禁忌长度
        Map<String, Integer> tabuList = new HashMap<>();

        // 多样化重启计数
        int noImproveCount = 0;
        final int RESTART_THRESHOLD = 500;

        for (int iter = 0; iter < maxIter; iter++) {
            // 衰减禁忌表
            tabuList.replaceAll((k, v) -> v - 1);
            tabuList.values().removeIf(v -> v <= 0);

            List<Push> pushes = generatePushes(current);
            if (pushes.isEmpty()) {
                // 无合法移动，强制重启
                current = initial;
                currentEval = evaluate(initial);
                noImproveCount = 0;
                continue;
            }

            // 评估所有邻域
            Push bestPush = null;
            State bestNeighbor = null;
            int bestNeighborEval = Integer.MAX_VALUE;

            for (Push push : pushes) {
                State neighbor = applyPush(current, push);
                int eval = evaluate(neighbor);
                String key = push.tabuKey();

                boolean isTabu = tabuList.containsKey(key);
                boolean aspiration = eval < bestEval; // 藐视准则：优于历史最佳则突破禁忌

                if ((!isTabu || aspiration) && eval < bestNeighborEval) {
                    bestNeighborEval = eval;
                    bestNeighbor = neighbor;
                    bestPush = push;
                }
            }

            if (bestNeighbor == null) {
                // 所有邻域都被禁忌且不满足藐视准则，随机选一个非禁忌移动
                for (Push push : pushes) {
                    if (!tabuList.containsKey(push.tabuKey())) {
                        bestNeighbor = applyPush(current, push);
                        bestPush = push;
                        break;
                    }
                }
                if (bestNeighbor == null) {
                    current = initial;
                    continue;
                }
            }

            // 更新当前状态
            current = bestNeighbor;
            currentEval = bestNeighborEval;

            // 加入禁忌表
            if (bestPush != null) {
                tabuList.put(bestPush.tabuKey(), tabuTenure);
            }

            // 更新历史最佳
            if (currentEval < bestEval) {
                bestState = current;
                bestEval = currentEval;
                noImproveCount = 0;

                // 检查是否达到目标
                if (isGoal(bestState)) {
                    System.out.println("找到目标解！迭代次数: " + iter);
                    return bestState;
                }
            } else {
                noImproveCount++;
            }

            // 多样化重启：长期无改进时，随机扰动当前解
            if (noImproveCount >= RESTART_THRESHOLD) {
                current = perturbState(current);
                currentEval = evaluate(current);
                noImproveCount = 0;
                tabuList.clear();
            }
        }

        return bestState;
    }

    /**
     * 扰动操作：随机执行若干次推箱，跳出局部最优
     */
    private State perturbState(State state) {
        State perturbed = state;
        Random rand = new Random();
        for (int i = 0; i < 5; i++) {
            List<Push> pushes = generatePushes(perturbed);
            if (pushes.isEmpty()) break;
            perturbed = applyPush(perturbed, pushes.get(rand.nextInt(pushes.size())));
        }
        return perturbed;
    }

    /**
     * 回溯获取移动路径
     */
    public List<String> extractPath(State goal) {
        List<String> path = new ArrayList<>();
        State cur = goal;
        while (cur.parent != null) {
            path.add(cur.move);
            cur = cur.parent;
        }
        Collections.reverse(path);
        return path;
    }

    // ==================== 测试入口 ====================
    public static void main(String[] args) {
        // 经典推箱子关卡 (XSB格式简化)
        char[][] level = {
            "########".toCharArray(),
            "#......#".toCharArray(),
            "#.@.$..#".toCharArray(),
            "#..$...#".toCharArray(),
            "#...$..#".toCharArray(),
            "#......#".toCharArray(),
            "#..###.#".toCharArray(),
            "#......#".toCharArray(),
            "########".toCharArray()
        };
        // 将三个目标点放在地图中
        level[1][1] = TARGET;
        level[1][2] = TARGET;
        level[1][3] = TARGET;

        System.out.println("===== 推箱子 禁忌搜索求解 =====\n");
        SokobanTabuSearch solver = new SokobanTabuSearch(level);
        State initial = solver.parseInitialState();

        System.out.printf("初始评估值: %d%n", solver.evaluate(initial));
        System.out.printf("目标点数量: %d%n\n", solver.totalTargets);

        long start = System.currentTimeMillis();
        State best = solver.tabuSearch(initial, 10000, 15);
        long elapsed = System.currentTimeMillis() - start;

        System.out.printf("\n搜索耗时: %dms%n", elapsed);
        System.out.printf("最终评估值: %d%n", solver.evaluate(best));
        System.out.printf("是否达成目标: %s%n", solver.isGoal(best) ? "是" : "否");
        System.out.printf("搜索深度: %d%n", best.depth);

        if (solver.isGoal(best)) {
            List<String> path = solver.extractPath(best);
            System.out.println("\n===== 推箱步骤 =====");
            for (int i = 0; i < path.size(); i++) {
                System.out.printf("%3d. %s%n", i + 1, path.get(i));
            }
        }
    }
}

算法原理深入

禁忌搜索的核心机制

1. 禁忌表（Tabu List）
2. 记录近期执行过的移动（箱子+方向）
3. 防止算法在短期内在相同区域来回震荡

4. 禁忌长度（Tenure）决定记忆深度，通常设为 √N 或固定经验值

5. 藐视准则（Aspiration Criteria）

6. 如果某个被禁忌的移动能产生优于历史最佳的解，则允许执行

7. 这是禁忌搜索跳出局部最优的关键

8. 多样化策略（Diversification）

9. 长期无改进时，对当前解进行随机扰动

10. 重置禁忌表，探索新的区域

11. 集中化策略（Intensification）

12. 在优质解附近加强搜索
13. 本文通过评估函数引导，优先选择距离目标更近的移动

评估函数设计

推箱子的评估函数至关重要。本文采用多层设计：

与精确算法的对比

扩展优化

1. 更精细的死锁检测：检测”墙边双箱死锁”、”房间死锁”等复杂模式
2. 目标分配优化：使用匈牙利算法为箱子分配目标点，而非简单的最近目标
3. 并行禁忌搜索：多线程运行多个禁忌搜索实例，共享最佳解信息
4. 学习评估函数：通过强化学习训练更精确的评估网络

总结

本文用Java实现了基于禁忌搜索的推箱子求解器，展示了：
– 推箱子状态的高效表示与哈希
– 死锁检测与启发式评估函数设计
– 禁忌搜索的核心机制：禁忌表、藐视准则、多样化重启
– 元启发式算法在NP-hard组合优化问题中的应用

禁忌搜索作为局部搜索的增强版本，在调度问题、路径规划、资源分配等领域均有出色表现。理解其”记忆-规避-突破”的思想，对解决实际工程中的复杂优化问题具有重要价值。