每日算法 — 使用java实现贪吃蛇：Dinic最小割逃生通道判定与Menger定理

贪吃蛇 AI 最难的部分不是”怎么吃到食物”，而是”吃到之后怎么不被自己困死”。绝大多数启发式（曼哈顿距离、贪心、甚至 A*）都会在蛇身变长后陷入死局：蛇头钻进一个封闭的小空间，把食物吃掉，然后无路可走。问题的本质不是”路有多长”，而是“通道有多宽”——一条只有 1 格宽的走廊，蛇身一旦挤进去，出口就被自己的身体堵死了。

这个”通道宽度”恰好有一个严格的数学刻画：最大流最小割定理 + Menger 定理。本文用 Dinic 最大流把”蛇头到目标之间有多少条互不相交的独立通道”算出来，并据此做出既能吃到食物、又不把自己困死的决策。

一、为什么是”独立通道数”，而不是”可达格数”

BFS 只能回答”可达/不可达”这种二值问题。对贪吃蛇来说，需要量化的关键指标是冗余度：

• 如果蛇头到尾巴之间有 3 条互不相交的路径，那么走错一条不会致命；
• 如果只有 1 条，那么这条路径上的任意一格就是咽喉（articulation），蛇身一旦占据它，尾巴就彻底断联。

Menger 定理给出了这个量与图割之间的等价关系：

最大流（顶点容量为 1 的网络）= 内部顶点不相交路径的最大条数 = 最小顶点割的大小。

也就是说，只要建一张”每格容量 1″的流网络，跑一次最大流，得到的数字就是独立逃生通道数；而最小割对应的那些格子，正是必须守住的咽喉格。这比”可达格数”信息量大得多。

二、建图：顶点容量 1 的标准技巧

棋盘 R × C，0 空 1 障碍。把每个空闲格拆成 in 与 out 两个节点：

限制全部施加在”格子内部”的边上，因此每条流路径互相不许共享格子——这正是”顶点不相交”的定义。求一次 maxFlow(S,T) 即得通道数。

三、完整实现

import java.util.*;

/**
 * 贪吃蛇 AI：用 Dinic 最大流 / 最小割计算"独立逃生通道数"。
 * 棋盘 0 = 空地，1 = 障碍（蛇身 / 墙壁）。
 */
public class SnakeFlowAI {

    static final int[] DR = {-1, 1, 0, 0};
    static final int[] DC = {0, 0, -1, 1};
    static final int INF = 1_000_000;      // 代表"无穷"容量的边

    private final int rows, cols, cells, nodes;
    private final int source, sink;
    private final Dinic dinic;

    public SnakeFlowAI(int rows, int cols) {
        this.rows = rows;
        this.cols = cols;
        this.cells = rows * cols;
        this.nodes = 2 * cells + 2;
        this.source = 2 * cells;
        this.sink = 2 * cells + 1;
        this.dinic = new Dinic(nodes);
    }

    private int in(int r, int c)  { return r * cols + c; }
    private int out(int r, int c) { return cells + r * cols + c; }

    /**
     * 计算蛇头与目标格之间的最大互不相交通道数（= 最小顶点割大小）。
     *
     * @param grid  0 空地 / 1 障碍（不含蛇头所在格）
     * @param hr    蛇头行
     * @param hc    蛇头列
     * @param tr    目标行
     * @param tc    目标列
     * @return 独立通道条数；返回 0 表示完全不连通
     */
    public int escapeRoutes(int[][] grid, int hr, int hc, int tr, int tc) {
        if (hr == tr && hc == tc) return 4;            // 已经在目标格上
        dinic.reset();

        // 目标格虽然可能正被蛇身占据（例如尾巴），但它即将腾空，按可通行处理
        int saved = grid[tr][tc];
        grid[tr][tc] = 0;

        // 1. 顶点容量：每格最多被一条路径占用
        for (int r = 0; r < rows; r++)
            for (int c = 0; c < cols; c++)
                if (grid[r][c] == 0)
                    dinic.addEdge(in(r, c), out(r, c), 1);

        // 2. 邻接边容量无穷：格子之间不限制路径数量
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] != 0) continue;
                for (int d = 0; d < 4; d++) {
                    int nr = r + DR[d], nc = c + DC[d];
                    if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
                    if (grid[nr][nc] != 0) continue;
                    dinic.addEdge(out(r, c), in(nr, nc), INF);
                }
            }
        }

        // 3. 源与汇
        dinic.addEdge(source, out(hr, hc), INF);
        dinic.addEdge(in(tr, tc), sink, INF);

        int flow = dinic.maxFlow(source, sink);
        grid[tr][tc] = saved;                          // 恢复棋盘
        return flow;
    }

    /**
     * 决策：在 4 个合法方向中挑一步，同时满足两个条件
     *   ① 走完之后蛇头到尾巴仍至少 2 条独立通道（不被自己堵死）
     *   ② 走完之后到食物的通道数 ≥ 1（食物仍可达）
     * 双条件都满足时，用"到食物的最短距离"做最终排序。
     */
    public int decide(int[][] grid, int hr, int hc, int tr, int tc,
                      int fr, int fc) {
        int bestDir = -1;
        int bestScore = Integer.MAX_VALUE;
        boolean foundSafe = false;

        for (int d = 0; d < 4; d++) {
            int nr = hr + DR[d], nc = hc + DC[d];
            if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
            if (grid[nr][nc] != 0) continue;           // 撞墙 / 撞蛇身

            grid[hr][hc] = 1;                          // 原头格变成身体
            int toTail = escapeRoutes(grid, nr, nc, tr, tc);
            int toFood = escapeRoutes(grid, nr, nc, fr, fc);
            int dist = bfsDist(grid, nr, nc, fr, fc);
            grid[hr][hc] = 0;                          // 回滚

            boolean safe = toTail >= 2 && toFood >= 1;
            int score = (toTail >= 2 ? 0 : 100) + (toFood >= 1 ? 0 : 50) + dist;

            if (safe && !foundSafe) {
                foundSafe = true; bestScore = score; bestDir = d;
            } else if (safe == foundSafe && score < bestScore) {
                bestScore = score; bestDir = d;
            }
        }
        return bestDir;                                // -1 表示四面皆险，需降级策略
    }

    /** 普通 BFS 最短距离，用于在同为安全候选时做优选 */
    private int bfsDist(int[][] grid, int sr, int sc, int tr, int tc) {
        if (grid[tr][tc] != 0) return INF;
        int[][] dist = new int[rows][cols];
        for (int[] row : dist) Arrays.fill(row, -1);
        Deque<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{sr, sc}); dist[sr][sc] = 0;
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            if (cur[0] == tr && cur[1] == tc) return dist[tr][tc];
            for (int d = 0; d < 4; d++) {
                int nr = cur[0] + DR[d], nc = cur[1] + DC[d];
                if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
                if (grid[nr][nc] != 0 || dist[nr][nc] != -1) continue;
                dist[nr][nc] = dist[cur[0]][cur[1]] + 1;
                q.offer(new int[]{nr, nc});
            }
        }
        return INF;
    }

    /** Dinic 最大流：BFS 分层 + DFS 阻塞流 + 当前弧优化 */
    static class Dinic {
        private final int n;
        private final List<int[]> edges = new ArrayList<>();  // {to, cap, revIndex}
        private final List<List<Integer>> g;

        Dinic(int n) {
            this.n = n;
            g = new ArrayList<>(n);
            for (int i = 0; i < n; i++) g.add(new ArrayList<>());
        }

        void reset() {
            edges.clear();
            for (List<Integer> l : g) l.clear();
        }

        void addEdge(int u, int v, int cap) {
            g.get(u).add(edges.size());
            edges.add(new int[]{v, cap, edges.size() + 1});
            g.get(v).add(edges.size());
            edges.add(new int[]{u, 0, edges.size() - 1});
        }

        private int[] level, iter;

        private boolean bfs(int s, int t) {
            level = new int[n];
            Arrays.fill(level, -1);
            Deque<Integer> q = new ArrayDeque<>();
            q.offer(s); level[s] = 0;
            while (!q.isEmpty()) {
                int u = q.poll();
                for (int id : g.get(u)) {
                    int[] e = edges.get(id);
                    if (e[1] > 0 && level[e[0]] < 0) {
                        level[e[0]] = level[u] + 1;
                        q.offer(e[0]);
                    }
                }
            }
            return level[t] >= 0;
        }

        private int dfs(int u, int t, int f) {
            if (u == t) return f;
            for (; iter[u] < g.get(u).size(); iter[u]++) {
                int id = g.get(u).get(iter[u]);
                int[] e = edges.get(id);
                if (e[1] > 0 && level[e[0]] == level[u] + 1) {
                    int d = dfs(e[0], t, Math.min(f, e[1]));
                    if (d > 0) {
                        e[1] -= d;
                        edges.get(e[2])[1] += d;     // 反向边增容
                        return d;
                    }
                }
            }
            return 0;
        }

        int maxFlow(int s, int t) {
            int flow = 0;
            while (bfs(s, t)) {
                iter = new int[n];
                int f;
                while ((f = dfs(s, t, INF)) > 0) flow += f;
            }
            return flow;
        }

        /** 残量网络上从源点是否可达（用于提取最小割的 from 侧） */
        boolean reachable(int v) {
            return level != null && v < level.length && level[v] >= 0;
        }
    }

    /** 从残量网络提取最小割：割边的 from 侧即"关键格"集合 */
    public List<int[]> criticalCells(int[][] grid, int hr, int hc, int tr, int tc) {
        escapeRoutes(grid, hr, hc, tr, tc);            // 先把最大流跑满
        // 此时 level 数组中"可达侧"标记了割的 from 侧
        List<int[]> res = new ArrayList<>();
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] != 0) continue;
                // 可达侧截至 in 点、但 out 点未达 → 该格自身即割点
                if (dinic.reachable(in(r, c)) && !dinic.reachable(out(r, c)))
                    res.add(new int[]{r, c});
            }
        }
        return res;
    }

    public static void main(String[] args) {
        // 场景一：中间一道墙只留 1 格缺口——典型咽喉
        int[][] wall = new int[12][12];
        for (int c = 0; c < 12; c++) wall[6][c] = 1;
        wall[6][6] = 0;                                  // 唯一缺口
        SnakeFlowAI ai = new SnakeFlowAI(12, 12);
        System.out.println("跨墙独立通道数 = " + ai.escapeRoutes(wall, 5, 6, 7, 6)); // 期望 1

        // 场景二：开阔场上蛇身竖直排列，尾巴在下，食物在右侧
        int[][] grid = new int[12][12];
        for (int r = 6; r <= 9; r++) grid[r][6] = 1;     // 蛇身
        int dir = ai.decide(grid, 5, 6, 9, 6, 5, 9);     // 头(5,6) 尾(9,6) 食物(5,9)
        System.out.println("选择方向索引 = " + dir + " （0上 1下 2左 3右）");
    }
}

四、为什么”通道数 ≥ 2″是判死的分界线

考虑一条 T 形走廊：蛇头在交叉口，往左是一条 20 格的死胡同，往右是开阔地。BFS 可达格数两边相同（都能走 20+ 格），但左边一旦走进去，蛇身会把出入口堵死。

用最小割看，差别立刻显现：

• 走左边后，”蛇头 → 尾巴”的最小割只剩 1（因为死胡同与外界只隔交叉口这一格），Menger 定理告诉我们此时只有 1 条独立通道——蛇身一填，就断联；
• 走右边后，割值上升到 3 或 4（取决于蛇头度数），说明有多条互不相交的逃生路径。

所以 toTail >= 2 不是拍脑袋的经验值，它有严格的图论含义：至少存在 2 条内部不相交的路径，意味着即使一条被身体占据，还有另一条可用。这是”不被自己堵死”的充分条件。

五、”到食物的通道数”约束了什么

只保证”能逃”是不够的，AI 还要保证”能吃”。这里第二个流解决的是另一类陷阱：

食物被卡在一个入口只有 1 格宽的凹槽里。这时 toFood 的最小割是 1——虽然当前可达，但吃下食物的瞬间，蛇身会占据那唯一的入口，形成”吃到即死”的局面。这类局面下 BFS 会兴高采烈地说”可达”，而流算法会明确报出 1。

实践中的处理策略是：

六、复杂度与工程优化

单次建图边数约为 5 RC（拆点边 + 四邻接 + 两条超级边），Dinic 在单位容量网络上近似 O(E√V)。对 20×20 棋盘，一次求解在毫秒级。但要注意：decide() 对每个方向（4 次）各求解两次流，因此每帧要做 8 次最大流 + 4 次 BFS。

实用的加速手段：

• 快速否定路径：先用一次 BFS 判断连通性，若目标根本不可达（toFood = 0），直接跳过流计算；
• 度数上界剪枝：蛇头度数 ≤ 4，所以 toTail ≤ 4。一旦流达到 2（决策阈值），可以在 dfs 中提前终止，无需跑满最大流——这能省掉一大半工作量；
• 区域预分割：用并查集先找连通块，若整片区域是一个完整的连通块且无瓶颈候选，直接按”安全”处理；
• 增量维护：蛇每步只改变 2 个格（头进、尾出），理论上可做动态流维护，但 Dinic 的残余图不适合直接增量，工程上通常改为缓存层级图 + 局部重跑。

七、最小割的另一重用法：标记危险格

criticalCells() 展示了最小割的第二个价值：直接给出咽喉位置。做法是最大流跑满后，在残量网络上从源点做一次可达性标记——in 侧可达而 out 侧不可达的格子，就是割点。

这些格子可以直接喂给评估函数，作为”高风险区”加权惩罚。长期来看，AI 会自发学会避开这些瓶颈通道，行为上表现为”绕远路但更安全”——这正是高水平贪吃蛇 AI 与贪心 AI 的典型差别。

小结

最大流最小割给贪吃蛇提供了一个全局连通冗余度的量化指标，补上了启发式搜索最缺的一环：判断这一步之后自己还能不能活。三个关键设计是：顶点容量 1 的拆点建图（保证路径互不相交）、用 Menger 定理把流值翻译成”独立逃生通道数”、以及双目标（尾巴 + 食物）双流判定。把它作为过滤器放在贪心或 A* 之前，即可得到一个可控、可解释、且不会自我困死的蛇 AI。