每日算法 — 使用java实现官兵捉贼：图论追捕与最短路径

游戏背景与问题建模

官兵捉贼是中国传统的追逃游戏：若干名”官兵”合作围捕一名”贼”，贼在固定区域内移动试图逃脱。本文将其抽象为图论追捕问题（Pursuit-Evasion Problem）：给定一个无向图表示活动区域，官兵和贼轮流在图上移动，官兵的目标是移动到贼所在节点或其相邻节点实现抓捕。

核心算法涉及：图的 BFS 最短路径、多智能体协同策略、以及抓捕成功条件的判定。

算法思路

图建模

将游戏区域抽象为无向图 G = (V, E)，每个节点代表一个位置，边代表可通行的路径。使用邻接表存储图结构。

最短路径预计算

对每个节点运行 BFS，预计算全源最短路径，为追捕决策提供距离信息。

协同追捕策略

1. 最近官兵追捕：每次由距离贼最近的官兵向贼移动一步。
2. 围堵策略：预测贼的移动方向，官兵提前占据关键节点（割点、桥）封堵逃跑路线。
3. 包围圈收缩：多名官兵从不同方向逼近，逐步缩小贼的活动范围。

抓捕判定

当任意官兵与贼处于同一节点，或贼的所有邻接节点均被官兵占据时，抓捕成功。

Java 完整实现

import java.util.*;

/**
 * 官兵捉贼：图论追捕与最短路径算法
 * 支持多官兵协同追捕、围堵策略与抓捕判定
 */
public class CopsAndRobber {

    private List<Integer>[] graph;      // 邻接表
    private int n;                       // 节点数量
    private int[][] dist;                // 全源最短距离

    /**
     * 初始化图结构
     * @param edges 边列表，每条边为 {u, v}
     * @param n     节点数量（节点编号 0 ~ n-1）
     */
    public CopsAndRobber(int[][] edges, int n) {
        this.n = n;
        this.graph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] e : edges) {
            graph[e[0]].add(e[1]);
            graph[e[1]].add(e[0]);
        }
        precomputeShortestPaths();
    }

    /**
     * 预计算全源最短路径（对每个节点运行 BFS）
     */
    private void precomputeShortestPaths() {
        dist = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dist[i], -1);
            bfs(i);
        }
    }

    private void bfs(int src) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(src);
        dist[src][src] = 0;

        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int v : graph[u]) {
                if (dist[src][v] == -1) {
                    dist[src][v] = dist[src][u] + 1;
                    queue.offer(v);
                }
            }
        }
    }

    /**
     * 模拟追捕过程
     * @param copPositions    官兵初始位置列表
     * @param robberPosition  贼初始位置
     * @param maxSteps        最大模拟步数
     * @return 追捕结果
     */
    public ChaseResult simulateChase(List<Integer> copPositions, int robberPosition, int maxSteps) {
        List<Integer> cops = new ArrayList<>(copPositions);
        int robber = robberPosition;
        List<String> history = new ArrayList<>();
        history.add(String.format("初始: 官兵=%s, 贼=%d", cops, robber));

        for (int step = 1; step <= maxSteps; step++) {
            // 贼移动：逃向距离所有官兵最远的邻接节点
            robber = moveRobber(robber, cops);
            history.add(String.format("第%d步: 贼移动到 %d", step, robber));

            // 检查抓捕
            if (isCaught(robber, cops)) {
                history.add("抓捕成功！");
                return new ChaseResult(true, step, cops, robber, history);
            }

            // 官兵移动：每名官兵向贼最短路径方向前进一步
            for (int i = 0; i < cops.size(); i++) {
                cops.set(i, moveCopTowardsRobber(cops.get(i), robber, cops));
            }
            history.add(String.format("第%d步: 官兵移动到 %s", step, cops));

            // 再次检查抓捕
            if (isCaught(robber, cops)) {
                history.add("抓捕成功！");
                return new ChaseResult(true, step, cops, robber, history);
            }
        }

        history.add("达到最大步数，贼逃脱！");
        return new ChaseResult(false, maxSteps, cops, robber, history);
    }

    /**
     * 贼的移动策略：逃向距离所有官兵总和最远的邻接节点
     */
    private int moveRobber(int robber, List<Integer> cops) {
        List<Integer> neighbors = graph[robber];
        if (neighbors.isEmpty()) return robber;

        int bestNode = robber;
        int maxMinDist = -1;

        for (int next : neighbors) {
            // 计算该节点到最近官兵的距离
            int minDist = Integer.MAX_VALUE;
            for (int cop : cops) {
                if (dist[cop][next] != -1) {
                    minDist = Math.min(minDist, dist[cop][next]);
                }
            }
            // 选择使"到最近官兵距离"最大的节点
            if (minDist > maxMinDist) {
                maxMinDist = minDist;
                bestNode = next;
            }
        }

        return bestNode;
    }

    /**
     * 官兵移动策略：沿最短路径向贼移动一步，避免碰撞
     */
    private int moveCopTowardsRobber(int cop, int robber, List<Integer> otherCops) {
        if (cop == robber) return cop;

        List<Integer> neighbors = graph[cop];
        int bestNode = cop;
        int minDist = dist[cop][robber];

        for (int next : neighbors) {
            // 避免两名官兵移动到同一位置
            if (otherCops.contains(next) && next != cop) continue;

            if (dist[next][robber] != -1 && dist[next][robber] < minDist) {
                minDist = dist[next][robber];
                bestNode = next;
            }
        }

        return bestNode;
    }

    /**
     * 判断贼是否被抓捕
     * 条件：贼与某官兵同节点，或贼的所有邻接节点都被官兵占据
     */
    private boolean isCaught(int robber, List<Integer> cops) {
        // 同节点抓捕
        if (cops.contains(robber)) return true;

        // 围堵抓捕：所有邻接节点都被官兵占据
        List<Integer> neighbors = graph[robber];
        if (neighbors.isEmpty()) return true; // 无处可逃

        for (int neighbor : neighbors) {
            if (!cops.contains(neighbor)) {
                return false;
            }
        }
        return true;
    }

    /**
     * 计算最少需要多少名官兵才能确保抓捕
     * 简化为：覆盖所有与贼距离为1的节点所需的最少官兵数
     */
    public int minCopsNeeded(int robberPos) {
        return graph[robberPos].size();
    }

    /**
     * 寻找图上的关键节点（割点），用于围堵策略
     */
    public List<Integer> findArticulationPoints() {
        boolean[] visited = new boolean[n];
        int[] disc = new int[n];      // 发现时间
        int[] low = new int[n];       // 最早可达祖先
        int[] parent = new int[n];
        Arrays.fill(parent, -1);
        List<Integer> articulationPoints = new ArrayList<>();
        boolean[] isAp = new boolean[n];
        int[] time = {0};

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfsArticulation(i, visited, disc, low, parent, isAp, time);
            }
        }

        for (int i = 0; i < n; i++) {
            if (isAp[i]) articulationPoints.add(i);
        }
        return articulationPoints;
    }

    private void dfsArticulation(int u, boolean[] visited, int[] disc, int[] low,
                                  int[] parent, boolean[] isAp, int[] time) {
        visited[u] = true;
        disc[u] = low[u] = ++time[0];
        int children = 0;

        for (int v : graph[u]) {
            if (!visited[v]) {
                children++;
                parent[v] = u;
                dfsArticulation(v, visited, disc, low, parent, isAp, time);
                low[u] = Math.min(low[u], low[v]);

                if (parent[u] == -1 && children > 1) {
                    isAp[u] = true;
                }
                if (parent[u] != -1 && low[v] >= disc[u]) {
                    isAp[u] = true;
                }
            } else if (v != parent[u]) {
                low[u] = Math.min(low[u], disc[v]);
            }
        }
    }

    // 结果封装
    public static class ChaseResult {
        public final boolean caught;
        public final int steps;
        public final List<Integer> finalCopPositions;
        public final int finalRobberPosition;
        public final List<String> history;

        public ChaseResult(boolean caught, int steps, List<Integer> cops,
                           int robber, List<String> history) {
            this.caught = caught;
            this.steps = steps;
            this.finalCopPositions = cops;
            this.finalRobberPosition = robber;
            this.history = history;
        }
    }

    public static void main(String[] args) {
        // 构建一个 4x4 网格图（节点编号 0-15）
        List<int[]> edges = new ArrayList<>();
        int rows = 4, cols = 4;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                int id = r * cols + c;
                if (c + 1 < cols) edges.add(new int[]{id, id + 1});     // 右
                if (r + 1 < rows) edges.add(new int[]{id, id + cols}); // 下
            }
        }

        CopsAndRobber game = new CopsAndRobber(edges.toArray(new int[0][]), rows * cols);

        System.out.println("=== 官兵捉贼模拟 ===");
        List<Integer> cops = Arrays.asList(0, 3);
        int robber = 15;
        ChaseResult result = game.simulateChase(cops, robber, 20);
        System.out.println("抓捕结果: " + (result.caught ? "成功" : "失败"));
        System.out.println("使用步数: " + result.steps);
        System.out.println("历史记录:");
        for (String h : result.history) {
            System.out.println("  " + h);
        }

        System.out.println("\n割点（关键围堵位置）: " + game.findArticulationPoints());
    }
}

复杂度分析

图上的追捕问题与图搜索博弈（Graph Searching Game）密切相关。对于一般图，确定最少需要多少名搜索者才能捕获 fugitive 是一个 PSPACE-完全问题。本文实现的启发式策略在实际场景中表现良好。

扩展思考

• 信息不完全博弈：官兵不知道贼的精确位置，只能根据目击报告更新概率分布，使用贝叶斯推断。
• 多贼场景：多名贼分散逃跑，官兵需要分组追捕，可建模为最小费用最大流问题。
• 带权图：不同道路通行速度不同，使用 Dijkstra 替代 BFS 计算最短路径。
• 视野限制：官兵和贼只能看到一定范围内的节点，引入局部感知与巡逻策略。