每日算法 — 使用java实现推箱子：束搜索与启发式状态评估

一、推箱子的搜索困境

推箱子（Sokoban）的规则人人都懂：小人只能推、不能拉，把每个箱子推到目标点上。但它的复杂度是 PSPACE 完全的——不是 NP，是 PSPACE。这一点决定了推箱子不能用「穷举找到一个解」的思路来做，因为状态空间会随箱子数指数爆炸。

举一个具体数字：7×7 的地图里放 4 个箱子，仅「箱子位置组合」就有 C(25,4) ≈ 12650 种，再乘上小人位置的 25 种、以及箱子排列顺序带来的区分，实际可达状态数量级在 10⁵~10⁶。8 个箱子时会跳到 10⁹ 以上。而 A 在这种问题上会遇到更糟的麻烦：启发式（箱子到目标的曼哈顿距离之和）严重低估真实代价*，因为箱子之间会互相挡道，导致 open 表被大量同分状态撑爆，内存先于时间耗尽。

束搜索（Beam Search）是针对这类问题的实用折中：每层只保留评分最好的 k 个节点。它把内存从「指数」压到「O(k × 深度)」，代价是放弃完备性——可能错过最优解，甚至可能找不到解。对于推箱子这类「有解就行」的游戏，这个交换非常划算。

二、束搜索的结构

标准束搜索流程：

1. 初始状态入束；
2. 每轮对束中每个状态生成所有合法后继；
3. 对所有后继按评分函数排序，取前 k 个作为下一层的束；
4. 直到某个状态满足目标条件，或超过最大深度。

关键设计点有三个：

评分函数。推箱子需要区分「已就位的箱子」和「还能动的箱子」。一个实用的评分是：

score = 1000 × 已就位箱子数
      - 3 × 未就位箱子到最近目标的距离之和
      - 0.1 × 小人到最近箱子的距离
      - 5 × 已走步数

权重分配的逻辑：就位箱子最有价值（直接推动目标达成）；距离项引导方向；小人距离项防止「箱子推对了但人跑不过去」的空转；步数项压制绕路。

去重。束搜索会重复展开同一状态。用状态哈希维护一个全局访问集，避免束内出现重复节点。这一步能显著提高 k 的有效利用率。

死锁检测。这是推箱子特有的、性价比最高的剪枝：

• 角落死锁：箱子被推到「两面墙夹住」的位置，且该位置不是目标点，则立即判死。判据是 (上或下是墙) 且 (左或右是墙)。
• 2×2 方块死锁：任意 2×2 区域全部被墙或箱子占满，且其中有箱子未就位，则整块无法移动，判死。
• 冻结死锁：箱子沿墙排列且无法再被推动，整组判死（实现复杂，本文从简）。

死锁检测放在生成后继时立刻执行，比放在评分阶段更省算力——被剪掉的分支不会进入排序，也就不会浪费一个束名额。

三、完整 Java 实现

3.1 地图与状态表示

import java.util.*;

/** 推箱子局面：小人位置 + 箱子位图（用 long 编码，支持 <=64 格） */
final class State {
    final int player;
    final long boxes;
    final int moves;
    final State parent;
    final char move;          // 产生本状态的动作 'U','D','L','R'

    State(int player, long boxes, int moves, State parent, char move) {
        this.player = player; this.boxes = boxes;
        this.moves = moves; this.parent = parent; this.move = move;
    }

    /** 状态指纹：只有 (player, boxes) 影响未来，moves/parent 不参与去重 */
    long key() { return boxes * 1000L + player; }
}

用 long 的位图表示箱子有个硬约束：格子数不能超过 64。本文示例地图 8×7=56 格刚好够用；更大的地图需要换成 BitSet 或 long[] 分段，key() 也要相应改成字符串或哈希值。

3.2 地图与规则

/** 静态地图：墙、目标、地面 */
final class Board {
    final int w, h;
    final boolean[] wall, goal;
    final int[] goalList;

    Board(String[] rows) {
        this.h = rows.length;
        this.w = rows[0].length();
        wall = new boolean[w * h];
        goal = new boolean[w * h];
        List<Integer> gl = new ArrayList<>();
        for (int r = 0; r < h; r++) {
            for (int c = 0; c < w; c++) {
                char ch = rows[r].charAt(c);
                int idx = r * w + c;
                if (ch == '#') wall[idx] = true;
                if (ch == '.' || ch == '*' || ch == '+') { goal[idx] = true; gl.add(idx); }
            }
        }
        this.goalList = gl.stream().mapToInt(Integer::intValue).toArray();
    }

    /** 从 from 沿 dr,dc 走一格的坐标，越界返回 -1 */
    int step(int from, int dr, int dc) {
        int r = from / w + dr, c = from % w + dc;
        if (r < 0 || r >= h || c < 0 || c >= w) return -1;
        return r * w + c;
    }

    boolean isWall(int p) { return p < 0 || p >= w * h || wall[p]; }
}

3.3 死锁检测

/** 死锁检测：角落死锁 + 2x2 方块死锁 */
final class Deadlock {
    final Board b;

    Deadlock(Board b) { this.b = b; }

    /** 箱子在 p 是否处于死锁 */
    boolean isDead(int p, long boxes) {
        if (b.goal[p]) return false;                     // 在目标上不算死

        // 角落死锁：(上或下是墙) 且 (左或右是墙)
        boolean u = b.isWall(b.step(p, -1, 0)), d = b.isWall(b.step(p, 1, 0));
        boolean l = b.isWall(b.step(p, 0, -1)), r = b.isWall(b.step(p, 0, 1));
        if ((u || d) && (l || r)) return true;

        // 2x2 方块死锁：p 参与的四个 2x2 区域逐一检查
        for (int dr = -1; dr <= 0; dr++)
            for (int dc = -1; dc <= 0; dc++)
                if (check2x2(p, dr, dc, boxes)) return true;
        return false;
    }

    /** 检查以 (p 偏移 dr,dc) 为左上角的 2x2 是否全被墙/箱子占满且含未就位箱子 */
    boolean check2x2(int p, int dr, int dc, long boxes) {
        int r0 = p / b.w + dr, c0 = p % b.w + dc;
        boolean hasBoxNotOnGoal = false;
        for (int r = r0; r <= r0 + 1; r++) {
            for (int c = c0; c <= c0 + 1; c++) {
                if (r < 0 || r >= b.h || c < 0 || c >= b.w) return false;
                int idx = r * b.w + c;
                boolean isBox = ((boxes >>> idx) & 1L) != 0;
                if (!b.wall[idx] && !isBox) return false;      // 有空格 -> 不是死锁
                if (isBox && !b.goal[idx]) hasBoxNotOnGoal = true;
            }
        }
        return hasBoxNotOnGoal;
    }
}

3.4 束搜索求解器

/** 束搜索求解器：每层保留评分最优的 k 个状态 */
public class SokobanBeam {
    final Board b;
    final Deadlock dead;
    final int beamWidth;
    final State initial;
    int expanded = 0, generated = 0;

    static final int[][] DIRS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    static final char[] DIR_CH = {'U', 'D', 'L', 'R'};

    SokobanBeam(Board b, State initial, int beamWidth) {
        this.b = b; this.dead = new Deadlock(b);
        this.initial = initial; this.beamWidth = beamWidth;
    }

    /** 生成 state 的所有合法后继（含死锁剔除） */
    List<State> successors(State s) {
        List<State> out = new ArrayList<>(4);
        for (int i = 0; i < 4; i++) {
            int np = b.step(s.player, DIRS[i][0], DIRS[i][1]);
            if (np < 0 || b.isWall(np)) continue;                 // 撞墙

            boolean npHasBox = ((s.boxes >>> np) & 1L) != 0;
            long nb = s.boxes;

            if (npHasBox) {
                // 推箱子：箱子后方必须空
                int bp = b.step(np, DIRS[i][0], DIRS[i][1]);
                if (bp < 0 || b.isWall(bp)) continue;
                if (((s.boxes >>> bp) & 1L) != 0) continue;        // 后方还有箱子
                nb = (s.boxes & ~(1L << np)) | (1L << bp);
                if (dead.isDead(bp, nb)) continue;                 // 死锁剪枝
            }
            out.add(new State(np, nb, s.moves + 1, s, DIR_CH[i]));
        }
        return out;
    }

    /** 评分：越大越好 */
    double score(State s) {
        int onGoal = 0;
        double distSum = 0;
        for (int p = 0; p < b.w * b.h; p++) {
            if (((s.boxes >>> p) & 1L) == 0) continue;
            if (b.goal[p]) { onGoal++; continue; }
            distSum += nearestGoalDist(p);
        }
        return 1000.0 * onGoal
             - 3.0 * distSum
             - 0.1 * nearestBoxDist(s)
             - 5.0 * s.moves;
    }

    /** 某格到最近目标点的曼哈顿距离 */
    double nearestGoalDist(int p) {
        int best = Integer.MAX_VALUE;
        int r = p / b.w, c = p % b.w;
        for (int g : b.goalList) {
            int gr = g / b.w, gc = g % b.w;
            best = Math.min(best, Math.abs(r - gr) + Math.abs(c - gc));
        }
        return best == Integer.MAX_VALUE ? 0 : best;
    }

    /** 小人到最近箱子的曼哈顿距离（防止人跑不过去） */
    double nearestBoxDist(State s) {
        int pr = s.player / b.w, pc = s.player % b.w;
        int best = Integer.MAX_VALUE;
        for (int p = 0; p < b.w * b.h; p++) {
            if (((s.boxes >>> p) & 1L) == 0) continue;
            best = Math.min(best, Math.abs(pr - p / b.w) + Math.abs(pc - p % b.w));
        }
        return best == Integer.MAX_VALUE ? 0 : best;
    }

    /** 每个目标点是否都有箱子（即全部就位） */
    boolean isSolved(State s) {
        long rest = s.boxes;
        for (int g : b.goalList) rest &= ~(1L << g);
        return rest == 0;
    }

    /** 主循环：逐层扩展 + 截断 */
    State solve(int maxDepth) {
        List<State> beam = new ArrayList<>();
        beam.add(initial);
        Set<Long> visited = new HashSet<>();
        visited.add(initial.key());

        for (int depth = 0; depth < maxDepth; depth++) {
            List<State> next = new ArrayList<>();
            for (State s : beam) {
                expanded++;
                if (isSolved(s)) return s;
                for (State ns : successors(s)) {
                    if (visited.add(ns.key())) { generated++; next.add(ns); }   // 全局去重
                }
            }
            if (next.isEmpty()) break;                       // 束枯竭 -> 判失败

            // 按评分降序，截断到 beamWidth
            next.sort((a, bb) -> Double.compare(score(bb), score(a)));
            if (next.size() > beamWidth) next = new ArrayList<>(next.subList(0, beamWidth));
            beam = next;
        }
        for (State s : beam) if (isSolved(s)) return s;      // 最后一层再查一次
        return null;
    }

    /** 回溯出动作序列 */
    static String path(State s) {
        StringBuilder sb = new StringBuilder();
        while (s.parent != null) { sb.append(s.move); s = s.parent; }
        return sb.reverse().toString();
    }
}

3.5 跑一个 4 箱关卡

########
#  . . #
#  $ $ #
#  @   #
#  $ $ #
#  . . #
########

# 墙、. 目标、$ 箱子、@ 小人。4 个箱子、4 个目标，BFS 穷举得到的最优解为 9 步。

public class SokobanDemo {
    public static void main(String[] args) {
        String[] rows = {
            "########",
            "#  . . #",
            "#  $ $ #",
            "#  @   #",
            "#  $ $ #",
            "#  . . #",
            "########"
        };
        Board b = new Board(rows);

        int player = -1;
        long boxes = 0;
        for (int r = 0; r < rows.length; r++) {
            for (int c = 0; c < rows[r].length(); c++) {
                char ch = rows[r].charAt(c);
                int idx = r * b.w + c;
                if (ch == '@' || ch == '+') player = idx;
                if (ch == '$' || ch == '*') boxes |= (1L << idx);
            }
        }

        State init = new State(player, boxes, 0, null, ' ');
        SokobanBeam solver = new SokobanBeam(b, init, 20);
        State sol = solver.solve(80);

        if (sol == null) {
            System.out.println("未找到解（束宽 20）");
        } else {
            System.out.println("解长度 = " + sol.moves);
            System.out.println("动作序列 = " + SokobanBeam.path(sol));
            System.out.println("扩展节点 = " + solver.expanded
                    + "，生成节点 = " + solver.generated);
        }
    }
}

四、束宽如何影响结果（实测）

对上面这个关卡（最优 9 步），把束宽 k 从 1 扫到 1000，实测结果如下：

这张表说明两件事：

1. k=1 会失败。贪心每步只走评分最高的那条路，一旦进入「箱子挡住箱子」的死胡同就再也出不来——而束搜索的容错正是来自「保留多条走廊」。
2. k 超过某个阈值后纯属浪费。这里 k=5 就已命中最优解，k=200 多花 20 倍算力买不到任何改进。束宽的合理取值通常取决于关卡难度，不是越大越好。

更重要的是束搜索的不完备性：如果最优解需要「先把箱子推远、再绕回来」这种短期评分下降的操作，束搜索很可能在中间层就把它剪掉了。这是评分函数设计的核心矛盾——局部最优评分不等于全局最优路径。

五、复杂度分析

• 时间：每层扩展 O(k × 4) 个状态，每个状态的评分需 O(W·H + B×G)，其中 W、H 是地图宽高，B 是箱子数，G 是目标数。总复杂度 O(D × k × (W·H + B·G))，D 为搜索深度。对 8×7、k=20、D=80，量级在 10⁴ 以内，毫秒级完成。
• 空间：束本身 O(k)，visited 集 O(D × k)。相比 BFS 的 O(状态空间总数)，这是数量级的节省——这正是束搜索存在的理由。
• 对比 A：A 在推箱子上的主要问题是 open 表膨胀，且曼哈顿启发式在有墙地图上会低估代价（不满足一致性），实际迭代次数远超理论值。束搜索牺牲最优性换取可预测的内存上限，工程上更容易部署。

六、可继续改进的方向

1. 用 BFS 距离场替代曼哈顿距离。地图里有墙时曼哈顿距离会严重低估，用预计算的「每格到最近目标的最短路长度」查表（一次多源 BFS，O(W·H)）能显著提升评分质量。
2. 推箱子专用启发式 PPDB。把箱子两两配对，预计算每对箱子到每对目标的最小推动次数，作为加强下界——这是顶级 Sokoban 求解器的核心武器。
3. 反向搜索。从目标状态反向搜索（箱子被「拉」），可以有效减少无效分支，也便于做对称性判重。
4. 束搜索 + 随机重启。用不同随机种子扰动后继生成顺序（或对评分加小噪声），多次短束搜索往往能找到更好解，且总开销远低于单次大束宽。

七、小结

推箱子是理解「搜索完备性 vs 可行性」的绝佳载体。当状态空间大到穷举无望时，放弃最优性保证、换一个可预测的资源上界，是工程上的常规操作。束搜索的价值不在于它聪明，而在于它诚实：它明确告诉你「我只在 k 条走廊里找」，然后用评分函数和死锁剪枝把这几条走廊选得足够好。