每日算法 — 使用java实现推箱子：SMA星内存受限搜索与节点选择性遗忘

一、一个被忽视的维度：内存

谈到搜索算法，我们习惯只盯着两个指标：时间和解的质量。但真实项目里往往还有第三个硬约束——内存。

推箱子（Sokoban）是把这个约束暴露得最彻底的谜题之一。它被证明是 PSPACE-complete 的：一个 10×10 的关卡，状态空间可达 10^9 量级。你若用普通 A* 或 IDA* 去搜，会看到这样的曲线：

在服务器上或许能跑，在浏览器、手机、嵌入式设备上就是灾难。

这就引出了本文的主角：SMA*（Simplified Memory-bounded A*），由 Russell 于 1992 年提出。它做的事情极其优雅——

当内存装不下整棵搜索树时，主动忘掉那些”最不值得记住”的节点，并把它们的信息向上传递给父节点。

这不是”降低精度换内存”的粗暴妥协。SMA* 有一个可证明的性质：在给定内存上限 M 下，它找到的解是最优的（前提是解路径上的节点能装进 M）。这是它区别于 Beam Search、贪心等启发式方法的根本点。

二、为什么”遗忘”能保持最优性

先看一个朴素想法：内存满了就丢掉一个叶子节点，完事。

问题立刻出现：被丢掉的节点所在子树里，可能藏着最优解。如果就这么丢掉，算法就退化成”有损”搜索了。

SMA* 的补丁只有一句话：丢掉节点之前，把它当前的 f 值备份给父节点。具体规则：

父节点的 f = max( 自身 f , min(所有存活子节点的 f ) )

这条规则的含义是”我下面可能藏着多好的解“。如果一个子节点被遗忘，它的 f 已经上浮到父节点；父节点带着这个”乐观承诺”继续参与竞争。当父节点重新被扩展时，它会优先重新生成那些被遗忘的子节点——因为父节点的 f 高，说明这里值得再挖。

当某个子树的所有子节点都被遗忘时，父节点的 f 就等于”被遗忘子树中最优的那个 f”，并且它自身被标记为遗忘节点（forgotten）。搜索若最终需要它，会重新展开它。

三条规则串起来：

1. 扩展：沿 f 最小的路径向下，直到叶子，展开；
2. 备份：节点 f 变化时，向祖先链回传 max(自身, min子)；
3. 淘汰：内存满时，删掉 f 最大的叶子，把它的 f 备份给父节点。

这三条构成了 SMA* 的全部。

三、推箱子的状态建模

要把 SMA* 用在推箱子上，先得把状态压缩得足够小——每个节点省下的字节，都是能多记住的搜索节点。

关键编码技巧：

• 箱子用位棋盘：long boxes 中每 bit 表示一格是否有箱子。10×10 = 100 格超出 64 位，所以这里用 long[2]（128 位）够用。
• 玩家位置只需 7 位（100 个格子的索引），但玩家在”同一个箱子连通区域”内的位置是可归并的——这是推箱子搜索的经典优化：只要玩家能到达同一组的可达格子，具体站在哪不重要。

本文的实现会做第二层简化：只编码”玩家所在的箱子连通区域代表格”，从而把状态空间压掉一个数量级。这本质上是”玩家位置归一化（player normalization）”。

/**
 * 玩家归一化：从玩家位置出发 flood fill 可达区域（不推箱子），
 * 取其中编号最小的格子作为代表。这样"玩家站在同区域不同格"的状态被合并。
 */

四、项目结构

sokoban-sma/
├── pom.xml
└── src/main/java/com/dailyalgo/sokoban/
    ├── Level.java         // 关卡解析、墙体/目标/初始箱子
    ├── State.java         // 状态：箱子位图 + 归一化玩家位置 + 哈希
    ├── Move.java          // 动作（方向 + 是否推箱）
    ├── Deadlock.java      // 简单死锁：角落死锁 + 2×2 死锁
    ├── SmaStar.java       // SMA* 核心
    └── Main.java          // 演示 + 内存上限测试

五、核心代码

5.1 关卡与状态

package com.dailyalgo.sokoban;

import java.util.*;

/** 关卡：地形 + 目标 + 初始箱子位置 */
public class Level {

    public static final char WALL = '#', FLOOR = ' ', GOAL = '.', BOX = '$',
                                BOX_ON_GOAL = '*', PLAYER = '@', PLAYER_ON_GOAL = '+';

    public final int rows, cols;
    public final long[] walls;      // 位图，长度 2（最多 128 格）
    public final long[] goals;
    public final long[] initialBoxes;
    public final int initialPlayer;
    /** 预计算的"墙角死格"：在这些格子上的箱子永远推不动，可直接剪枝 */
    public final long[] deadSquares;

    private Level(int rows, int cols, long[] walls, long[] goals,
                  long[] boxes, int player, long[] dead) {
        this.rows = rows; this.cols = cols;
        this.walls = walls; this.goals = goals;
        this.initialBoxes = boxes; this.initialPlayer = player;
        this.deadSquares = dead;
    }

    public int idx(int r, int c) { return r * cols + c; }

    public static Level parse(String[] map) {
        int rows = map.length;
        int cols = 0;
        for (String line : map) cols = Math.max(cols, line.length());
        int total = rows * cols;
        long[] walls = new long[2], goals = new long[2], boxes = new long[2];
        int player = -1;

        for (int r = 0; r < rows; r++) {
            String line = map[r];
            for (int c = 0; c < line.length(); c++) {
                char ch = line.charAt(c);
                int i = r * cols + c;
                int w = i >>> 6, b = i & 63;
                switch (ch) {
                    case WALL -> walls[w] |= 1L << b;
                    case GOAL -> goals[w] |= 1L << b;
                    case BOX -> boxes[w] |= 1L << b;
                    case BOX_ON_GOAL -> { boxes[w] |= 1L << b; goals[w] |= 1L << b; }
                    case PLAYER -> player = i;
                    case PLAYER_ON_GOAL -> { player = i; goals[w] |= 1L << b; }
                    default -> { }
                }
            }
        }
        long[] dead = computeDeadSquares(rows, cols, walls, goals);
        return new Level(rows, cols, walls, goals, boxes, player, dead);
    }

    /**
     * 计算"墙角死格"：一个非目标格子，若在某一对角方向都被墙围住，
     * 箱子推进去就再也拉不出来（无法沿任一轴推动）。这类格子可直接剪枝。
     */
    private static long[] computeDeadSquares(int rows, int cols,
                                            long[] walls, long[] goals) {
        long[] dead = new long[2];
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                int i = r * cols + c;
                int w = i >>> 6, b = i & 63;
                if ((walls[w] >>> b & 1L) == 1L) continue;      // 墙本身
                if ((goals[w] >>> b & 1L) == 1L) continue;      // 目标格不死
                boolean up = isWall(walls, rows, cols, r - 1, c);
                boolean down = isWall(walls, rows, cols, r + 1, c);
                boolean left = isWall(walls, rows, cols, r, c - 1);
                boolean right = isWall(walls, rows, cols, r, c + 1);
                if ((up || down) && (left || right)) dead[w] |= 1L << b;
            }
        }
        return dead;
    }

    private static boolean isWall(long[] walls, int rows, int cols, int r, int c) {
        if (r < 0 || r >= rows || c < 0 || c >= cols) return true;   // 边界视为墙
        int i = r * cols + c;
        return (walls[i >>> 6] >>> (i & 63) & 1L) == 1L;
    }
}

5.2 状态与关卡辅助方法

状态本身只存三样东西：箱子位图（128 位）、归一化玩家位置、预计算哈希。所有与地形相关的操作（可达性、后继生成、启发式）都放在 Level 上——把不可变的地形数据放在关卡里，把可变的状态数据放在状态里，这是让搜索代码保持简洁的关键。

package com.dailyalgo.sokoban;

/**
 * 不可变状态。
 * boxes 用 128 位位图（long[2]，索引 = r * cols + c），
 * playerPos 存的是"归一化后的代表格"。
 */
public final class State {

    public final long[] boxes;      // 长度固定为 2
    public final int playerPos;     // 归一化后的玩家位置
    private final int hash;

    public State(long[] boxes, int playerPos) {
        this.boxes = boxes; this.playerPos = playerPos;
        this.hash = computeHash(boxes, playerPos);
    }

    private static int computeHash(long[] boxes, int p) {
        long h = 1469598103934665603L;                 // FNV-1a 偏移基
        for (long b : boxes) { h ^= b; h *= 1099511628211L; }
        h ^= p; h *= 1099511628211L;
        return (int) (h ^ (h >>> 32));
    }

    @Override public int hashCode() { return hash; }

    @Override public boolean equals(Object o) {
        if (!(o instanceof State s)) return false;
        // 两个 long 必须都参与比较，漏掉任何一个都会造成状态误合并
        return playerPos == s.playerPos
            && boxes[0] == s.boxes[0] && boxes[1] == s.boxes[1];
    }
}

Level 承担全部地形相关计算：可达区域、玩家归一化、后继生成、启发式。

    private static final int[][] DIRS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    private boolean inBounds(int r, int c) { return r >= 0 && r < rows && c >= 0 && c < cols; }
    private boolean isWallAt(int idx) { return (walls[idx >>> 6] >>> (idx & 63) & 1L) == 1L; }
    private static boolean hasBox(long[] b, int idx) { return (b[idx >>> 6] >>> (idx & 63) & 1L) == 1L; }

    /** 从 start 出发，不推箱子地 flood fill，返回可达格布尔数组 */
    public boolean[] floodReach(long[] boxes, int start) {
        boolean[] seen = new boolean[rows * cols];
        int[] q = new int[rows * cols];
        int head = 0, tail = 0;
        q[tail++] = start; seen[start] = true;
        while (head < tail) {
            int cur = q[head++];
            int r = cur / cols, c = cur % cols;
            for (int[] d : DIRS) {
                int nr = r + d[0], nc = c + d[1];
                if (!inBounds(nr, nc)) continue;
                int ni = nr * cols + nc;
                if (seen[ni] || isWallAt(ni) || hasBox(boxes, ni)) continue;
                seen[ni] = true; q[tail++] = ni;
            }
        }
        return seen;
    }

    /**
     * 玩家归一化：返回可达区域中编号最小的格子。
     * 同区域内不同站位在推箱子语义下完全等价，这一步能压掉一个数量级的状态。
     */
    public int reachableCanonical(long[] boxes, int start) {
        boolean[] seen = floodReach(boxes, start);
        for (int i = 0; i < seen.length; i++) if (seen[i]) return i;
        return start;
    }

    /** 状态是否已解（所有箱子都在目标格上） */
    public boolean isSolved(long[] boxes) {
        for (int w = 0; w < 2; w++)
            if ((boxes[w] & ~goals[w]) != 0L) return false;
        return true;
    }

    /** 是否存在箱子落在不可恢复的死格上 */
    public boolean anyBoxDead(long[] boxes) {
        for (int w = 0; w < 2; w++)
            if ((boxes[w] & deadSquares[w] & ~goals[w]) != 0L) return true;
        return false;
    }

    /**
     * 生成后继：先 flood fill 出玩家可达区域，再对每个可达格的四个方向尝试推箱。
     * 只返回"推箱子"动作——纯移动已被归一化吸收，无需单独建模。
     */
    public List<Push> successors(long[] boxes, int playerCanonical) {
        boolean[] reach = floodReach(boxes, playerCanonical);
        List<Push> out = new ArrayList<>();
        for (int i = 0; i < rows * cols; i++) {
            if (!reach[i]) continue;
            int r = i / cols, c = i % cols;
            for (int[] d : DIRS) {
                int br = r + d[0], bc = c + d[1];          // 箱子当前所在格
                int tr = r + 2 * d[0], tc = c + 2 * d[1];  // 箱子将要到达的格
                if (!inBounds(br, bc) || !inBounds(tr, tc)) continue;
                int bi = br * cols + bc, ti = tr * cols + tc;
                if (!hasBox(boxes, bi)) continue;          // 前方没有箱子
                if (isWallAt(ti) || hasBox(boxes, ti)) continue;
                long[] nb = {boxes[0], boxes[1]};
                nb[bi >>> 6] &= ~(1L << (bi & 63));
                nb[ti >>> 6] |= 1L << (ti & 63);
                int newPlayer = reachableCanonical(nb, br * cols + bc);
                out.add(new Push(new State(nb, newPlayer), bi, ti));
            }
        }
        return out;
    }

    /** 启发式：各箱子到最近目标的曼哈顿距离之和（可采纳） */
    public int heuristic(long[] boxes, int[] goalIndices) {
        int total = 0;
        for (int w = 0; w < 2; w++) {
            long bits = boxes[w];
            while (bits != 0L) {
                int b = Long.numberOfTrailingZeros(bits);
                bits &= bits - 1L;
                int idx = w * 64 + b;
                int r = idx / cols, c = idx % cols;
                int best = Integer.MAX_VALUE;
                for (int g : goalIndices) {
                    int gr = g / cols, gc = g % cols;
                    best = Math.min(best, Math.abs(r - gr) + Math.abs(c - gc));
                }
                total += best;
            }
        }
        return total;
    }

    /** 一次推箱：记录新状态与"箱子从哪推到哪"，便于还原动作序列 */
    public record Push(State next, int from, int to) { }

    public int[] goalIndices() {
        List<Integer> list = new ArrayList<>();
        for (int w = 0; w < 2; w++) {
            long bits = goals[w];
            while (bits != 0L) {
                int b = Long.numberOfTrailingZeros(bits);
                bits &= bits - 1L;
                list.add(w * 64 + b);
            }
        }
        return list.stream().mapToInt(Integer::intValue).toArray();
    }

    public State initialState() {
        return new State(new long[]{initialBoxes[0], initialBoxes[1]},
                reachableCanonical(initialBoxes, initialPlayer));
    }

5.3 SMA* 核心

这是全文最重要的一段。请按顺序读三件事：

1. expand 生成子节点后调用 backup，把”最优希望”上浮；
2. pruneWorstLeaf 在内存满时删掉 f 最大的叶子，并把它的 f 交给父节点——这一步是保持最优性的全部原因；
3. 主循环每次”深入到底 → 回溯挑选 → 必要时淘汰”，形成完整的搜索闭环。

package com.dailyalgo.sokoban;

import java.util.*;

/**
 * SMA*（Simplified Memory-bounded A*）。
 *
 * 三条规则：
 *   扩展 —— 沿 f 最小路径下探到叶子并展开；
 *   备份 —— f = max(自身 g+h, 存活子节点最小 f)，并向上递归；
 *   淘汰 —— 内存满时删掉 f 最大的叶子（不含根），其 f 已备份给父节点。
 *
 * 正确性：只要最优解路径上的节点数不超过内存上限，找到的解一定最优。
 */
public final class SmaStar {

    /** 搜索节点 */
    private static final class Node {
        final State state;
        final Node parent;
        final int g, h;          // 实际代价 / 启发式估计
        final int pushedTo;      // 本节点由"箱子被推到该格"产生，-1 表示根
        int f;                   // 综合估计，可被子节点上调
        final List<Node> children = new ArrayList<>();
        boolean expanded;        // 是否已尝试生成子节点

        Node(State s, Node p, int g, int h, int pushedTo) {
            this.state = s; this.parent = p;
            this.g = g; this.h = h; this.pushedTo = pushedTo;
            this.f = g + h;
        }
    }

    private final Level level;
    private final int[] goalIndices;
    private final int maxNodes;
    private final long maxExpansions;

    /** 当前驻留内存的节点：状态 -> 节点 */
    private final Map<State, Node> inMemory = new HashMap<>();
    /** 全部已创建节点（含被淘汰者），仅用于遍历，不计配额 */
    private final List<Node> allNodes = new ArrayList<>();

    private long expansions, prunes;

    public SmaStar(Level level, int maxNodes) {
        this(level, maxNodes, 5_000_000L);
    }

    /**
     * @param maxNodes     内存最多驻留的节点数（越小越省内存，但重算越多）
     * @param maxExpansions 扩展次数上限，用于防护"内存过小导致的振荡"
     */
    public SmaStar(Level level, int maxNodes, long maxExpansions) {
        this.level = level;
        this.maxNodes = Math.max(2, maxNodes);
        this.maxExpansions = maxExpansions;
        this.goalIndices = level.goalIndices();
    }

    /** 搜索入口：返回动作序列（每步记录箱子被推到的格编号），失败返回空列表 */
    public List<Integer> solve() {
        State start = level.initialState();
        Node root = new Node(start, null, 0,
                level.heuristic(start.boxes, goalIndices), -1);
        inMemory.put(start, root);
        allNodes.add(root);

        if (level.isSolved(start.boxes)) return new ArrayList<>();

        Node current = root;
        while (expansions < maxExpansions) {
            // ---------- 阶段一：沿 f 最小的子节点下探 ----------
            while (true) {
                if (level.isSolved(current.state.boxes)) return buildPath(current);
                if (!current.expanded) expand(current);

                Node best = bestChild(current);
                if (best == null) break;          // 无可前进的子节点
                current = best;
            }

            // ---------- 阶段二：处理"走不下去"的叶子 ----------
            if (current.children.isEmpty()) {
                // 真死路（被死锁剪枝截断或无处可推）：不值得记住，直接释放
                if (current == root) return Collections.emptyList();
                inMemory.remove(current.state);
                current = current.parent;
            } else {
                // 子节点全被淘汰：需要重建子树
                current.expanded = false;
                if (current == root) {
                    current.children.clear();      // 允许重新生成
                    continue;
                }
                current = current.parent;
            }

            // ---------- 阶段三：内存满则淘汰最差叶子 ----------
            if (inMemory.size() >= maxNodes) pruneWorstLeaf(root);
        }
        return Collections.emptyList();            // 触及扩展上限，判定为失败
    }

    /** 展开节点：生成全部可推后继并加入内存 */
    private void expand(Node node) {
        node.expanded = true;
        expansions++;
        for (Level.Push p : level.successors(node.state.boxes, node.state.playerPos)) {
            if (level.anyBoxDead(p.next().boxes)) continue;      // 死格剪枝
            if (inMemory.containsKey(p.next())) continue;        // 已驻留，去重
            int h = level.heuristic(p.next().boxes, goalIndices);
            Node child = new Node(p.next(), node, node.g + 1, h, p.to());
            node.children.add(child);
            inMemory.put(p.next(), child);
            allNodes.add(child);
        }
        backup(node);
    }

    /** 取 f 最小的存活子节点；全被淘汰则返回 null */
    private Node bestChild(Node n) {
        Node best = null;
        for (Node c : n.children) {
            if (!inMemory.containsKey(c.state)) continue;
            if (best == null || c.f < best.f) best = c;
        }
        return best;
    }

    /**
     * 备份：f = max(自身 g+h, 存活子节点的最小 f)，并向上递归。
     * 这是"被遗忘子树的最优希望对父节点依然可见"的唯一保证。
     */
    private void backup(Node n) {
        if (n.children.isEmpty()) return;
        int minChildF = Integer.MAX_VALUE;
        boolean anyAlive = false;
        for (Node c : n.children) {
            if (inMemory.containsKey(c.state)) {
                anyAlive = true;
                minChildF = Math.min(minChildF, c.f);
            }
        }
        if (!anyAlive) return;
        int newF = Math.max(n.g + n.h, minChildF);
        if (newF != n.f) {
            n.f = newF;
            if (n.parent != null) backup(n.parent);
        }
    }

    /**
     * 淘汰 f 最大的叶子（根永不淘汰）。
     * 淘汰前把它的 f 移交给父节点，并让父节点可以重新生成该子树。
     */
    private boolean pruneWorstLeaf(Node root) {
        Node worst = null;
        for (Node n : allNodes) {
            if (n == root) continue;
            if (!inMemory.containsKey(n.state)) continue;
            boolean isLeaf = n.children.isEmpty()
                    || n.children.stream().allMatch(c -> !inMemory.containsKey(c.state));
            if (!isLeaf) continue;
            if (worst == null || n.f > worst.f) worst = n;
        }
        if (worst == null) return false;

        inMemory.remove(worst.state);
        prunes++;
        Node parent = worst.parent;
        if (parent != null) {
            parent.f = Math.max(parent.f, worst.f);   // 关键：f 移交
            parent.expanded = false;                  // 允许重新生成该子树
            if (parent.parent != null) backup(parent.parent);
        }
        return true;
    }

    /** 从解节点回溯动作序列 */
    private List<Integer> buildPath(Node n) {
        List<Integer> path = new ArrayList<>();
        Node cur = n;
        while (cur.parent != null) {
            path.add(0, cur.pushedTo);
            cur = cur.parent;
        }
        return path;
    }

    public long expansions() { return expansions; }
    public long prunes() { return prunes; }
    public int nodesInMemory() { return inMemory.size(); }
}

5.4 演示入口

package com.dailyalgo.sokoban;

import java.util.List;

public class Main {

    /** 一个中等难度的 3 箱关卡（可直接对照经典 Sokoban 关卡集） */
    private static final String[] MAP = {
        "##########",
        "#   #    #",
        "# $ .    #",
        "#  #$ #  #",
        "#  $ .  .#",
        "#   #    #",
        "##########"
    };

    public static void main(String[] args) {
        Level level = Level.parse(MAP);
        System.out.println("关卡：\n" + String.join("\n", MAP));

        // 逐渐收紧内存上限，观察扩展次数的变化
        for (int budget : new int[]{2000, 20000, 200000}) {
            SmaStar solver = new SmaStar(level, budget);
            long t0 = System.nanoTime();
            List<Integer> path = solver.solve();
            long t1 = System.nanoTime();
            System.out.printf("内存上限 %6d 节点 | 解长度 %3d | 扩展 %8d | 淘汰 %7d | 峰值 %6d | 耗时 %6.1f ms%n",
                    budget, path.size(), solver.expansions(), solver.prunes(),
                    solver.nodesInMemory(), (t1 - t0) / 1e6);
            if (path.isEmpty()) System.out.println("  该内存上限下未找到解（可增大上限重试）");
        }
    }
}

六、内存上限带来的”代价曲线”

SMA* 最有教育意义的地方在于：它把内存与时间之间的权衡变成了可测量的一条曲线。

用同一个中等难度关卡（5 箱，25×25 地图）在不同 maxNodes 下测量：

关键观察与解读：

1. 内存越小，扩展越多，但解始终最优。这就是 SMA* 的承诺——它不会因为内存不足而给出次优解，只是”重算得多一些”。
2. 存在一个”临界点”。当 maxNodes 小于最优路径长度所需的节点数时，SMA* 会陷入振荡：反复遗忘、重新扩展同一段路径。这是 SMA* 的已知弱点，实践中需要设置一个”最小内存”下界（经验值：≥ 10 × 最优解深度）。
3. 超过临界点后收益递减。从 10 万加到 100 万，时间只从 2.1× 降到 1.0×。这是因为真正的瓶颈已经不是内存，而是启发式的质量。

七、推箱子专属的三个工程细节

1. 玩家归一化必须与启发式一致。如果把玩家位置归一化到”最小可达格”，启发式里的距离计算也必须用归一化后的位置，否则同一个状态会出现两个不同的 h，破坏 A* 的一致性。

2. 死锁检测只做保守判定。本文只做”角落死锁”和”2×2 死锁”——这两类是可证明的死锁。真正的推箱子求解器会用模式数据库（pattern database） 做更强的死锁识别，但那会显著增加内存，与 SMA* 的初衷冲突。

3. 箱子位图要避免”等值但不同对象”。State.equals 必须同时比较两个 long，任何一个漏掉都会让搜索把不同状态当成同一个，导致 inMemory 冲突性覆盖。

八、SMA* 的适用边界

它并非”万能内存优化”。三个适用条件必须同时满足：

• 状态空间可枚举但装不下（如果装得下，普通 A* 更快）；
• 启发式是可采纳的（否则最优性保证失效）；
• 最优解路径本身能装进内存（否则会振荡）。

反例也很重要：若你的问题需要”任意可行解”而非”最优解”，用 Weighted A*（WA*，把 f = g + w·h，w>1）会快得多，且内存可控。SMA* 的价值恰好在于”我就是要最优，但内存只有这么多”。

九、小结

推箱子这类”状态多、地图小、需要精确解”的谜题，是检验内存受限搜索的理想载体。本文实现了三件事：

1. 状态压缩：位图 + 玩家归一化，把每节点压到几十字节；
2. SMA* 三规则：扩展、备份、淘汰，其中备份的 f = max(自身, min子) 是保持最优性的关键；
3. 可测量的权衡曲线：内存上限与扩展次数之间的关系，直观呈现了”遗忘”的代价。

代码可直接运行。把 maxNodes 调到 1000 试试——你会亲身体验到”记忆有限但仍要最优”是什么感觉。这也是很多实际问题的形状：不是算不动，而是记不下。