每日算法 — 使用java实现打地鼠：区间图建模与最大权独立集

打地鼠看起来只是一个”手快就行”的游戏，但当你想让程序自动玩到最高分时，它立刻变成一个严肃的调度问题：每只地鼠只露出一小段时间窗口，锤子在同一时刻只能砸一个洞，而且锤子从一个洞移动到另一个洞需要时间。要在有限的总时长内拿到最高总分，本质上是”在时间轴上挑选一组互不冲突的任务”——这正是加权区间调度（Weighted Interval Scheduling）问题。

本文用 Java 把打地鼠抽象成区间图（Interval Graph），并证明该图是弦图（Chordal Graph）：于是原本在一般图上 NP-hard 的最大权独立集问题，在这里可以多项式时间求解。我们会分别用动态规划与完美消除序两种视角实现它，并给出可直接运行的项目结构。

一、从游戏规则到区间模型

1.1 游戏的最小规则集

为了让算法成为主角，我们只保留必要的约束：

• 游戏区域有 HOLES 个地鼠洞，编号 0..HOLES-1，相邻洞之间有固定距离。
• 锤子初始停在 0 号洞，移动速度为 SPEED（单位：洞/秒），从 i 移到 j 耗时 |i-j| / SPEED。
• 每只地鼠 m 有出现时刻 start、消失时刻 end、分值 score。
• 击打耗时忽略不计（或视为常数，归入移动时间）。
• 同一时刻只能击打一只地鼠；一只地鼠也只能被击打一次。

一只地鼠 i 若能在玩家位于洞 h、当前时刻 t 时被打到，需要满足 start_i <= t <= end_i 且 t 恰好是到达该洞的时刻。为了把问题干净地化成区间问题，我们采用业界常见的离散时间槽建模：时间被切成整数槽，锤子要么停留、要么移动到相邻洞（每移动一格耗一个槽）。这样”可达”关系就退化为区间重叠关系。

1.2 区间抽象

把每只地鼠看成一个三元组 (start, end, score)，即时间轴上的一个闭区间，权重为分值。两只地鼠”冲突”当且仅当它们的区间相交（因为锤子不可能在同一时刻砸两个洞；若移动时间不可忽略，则把每只地鼠的区间向左扩张 travel 长度，冲突判定仍等价于区间相交，只是区间定义变了）。

于是问题变成：

给定 n 个带权区间，选出若干两两不冲突的区间，使权重和最大。

1.3 朴素 DP 的第一直觉

若把区间按右端点排序（end 升序），定义 p(j) 为”在 j 之前结束、且与 j 不冲突的最后一个区间的下标”，则

dp[j] = max( dp[j-1], score_j + dp[p(j)] )

这就是教科书式的加权区间调度，复杂度 O(n log n)（p(j) 用二分）。它能跑，但只处理了”时间冲突”这一种互斥关系。真实游戏里锤子的移动还会引入更复杂的约束（例如从洞 3 到洞 7 之间若横跨了另一只刚出现的地鼠，你其实可以顺手打它，但你不能分身）。要在图上精确表达这些互斥关系，就需要区间图。

二、区间图与弦图：为什么这里可以多项式求解

2.1 区间图的定义

把每个区间视为一个顶点，两个区间相交则连一条边，得到的图称为区间图。一个显然的事实：

区间图中的一个独立集 = 一组两两不相交的区间。

因此”最大权独立集”就是”最大权不相交区间集合”，与加权区间调度完全等价。问题在于：一般图的最大权独立集是 NP-hard 的，凭什么区间图能快？

2.2 关键性质：区间图是弦图

弦（chord）指连接环上两个非相邻顶点的边。若图中任意长度 ≥ 4 的环都含有一条弦，则称该图为弦图。区间图恰好满足这一点：取区间图中任意一个长度 ≥ 4 的环 I1-I2-...-Ik-I1，设 I1 是这些区间中右端点最早的那个，那么 I1 只可能与环上”包含它右端点”的区间相交，从而 I1 一定与环上某个非相邻区间相邻——这条边就是弦。证明很短，但结论很强：

区间图是弦图；并且按右端点升序排列，恰好给出一个完美消除序（Perfect Elimination Ordering, PEO）。

完美消除序是指一个顶点排列 v1..vn，使得每个 vi 在 {vi,...,vn} 中的邻居集合构成一个团（两两相邻）。弦图的判定与 PEO 构造都可以线性时间完成，而一旦有了 PEO，很多 NP-hard 问题就退化为贪心。

2.3 在 PEO 上求最大权独立集

按 PEO 逆序处理（即从右端点最大的区间开始往前），对每个顶点 v，它的”后续邻居”构成团，团内最多只能选一个。于是有经典结论：

• 在 PEO 上做动态规划（而非贪心）是安全的：按 PEO 逆序，每步在”当前顶点与后续邻居团”里做一次局部最优决策，可以把原本需要全局比较的问题压缩成若干个小团上的决策。
• 直接贪心（每次取团内权重最大者）不保证最优——它可能提前锁定一个重顶点，从而错失两个中等顶点之和。这一点在 3.5 节的代码里我们会刻意做一次对拍，让差异显式暴露出来。
• 对区间图而言，团对应”共享某个时间点的所有区间”，团大小等于该时刻同时出现的地鼠数上界，通常 ≤ 5，因此团内枚举（2^5 种选法）是常数级。

实际工程里，我更推荐加权区间调度 DP（简单、可证明最优），而把弦图性质作为正确性的理论保证 + 剪枝的依据。下面的代码里两者都会实现，并互相对拍验证结果一致。

三、Java 完整实现

3.1 项目结构

mole-whack/
├── pom.xml
└── src/main/java/com/example/mole/
    ├── Mole.java                  // 地鼠实体：区间 + 权重
    ├── IntervalGraph.java         // 区间图构建、团枚举、PEO 生成
    ├── WeightedIntervalScheduler.java  // DP 求解最大权独立集
    ├── GreedyPeoSolver.java       // 完美消除序贪心求解（用于对拍验证）
    ├── MoleGame.java              // 游戏模拟与可视化输出
    └── Main.java                  // 入口

3.2 地鼠实体

package com.example.mole;

/**
 * 一只地鼠：时间轴上的一段闭区间 + 分值。
 */
public class Mole implements Comparable<Mole> {
    public final int id;
    public final int hole;    // 出现的洞编号
    public final int start;   // 出现时刻（含）
    public final int end;     // 消失时刻（含）
    public final int score;   // 击打得分

    public Mole(int id, int hole, int start, int end, int score) {
        if (start > end) throw new IllegalArgumentException("区间非法: " + start + " > " + end);
        this.id = id;
        this.hole = hole;
        this.start = start;
        this.end = end;
        this.score = score;
    }

    /** 两个区间是否相交（闭区间，端点相同也算冲突） */
    public boolean conflicts(Mole o) {
        return Math.max(this.start, o.start) <= Math.min(this.end, o.end);
    }

    /** 按右端点升序，右端点相同则左端点升序 —— 这个次序就是区间图的完美消除序 */
    @Override
    public int compareTo(Mole o) {
        int c = Integer.compare(end, o.end);
        return c != 0 ? c : Integer.compare(start, o.start);
    }

    @Override
    public String toString() {
        return String.format("Mole#%d[hole=%d, t=%d..%d, w=%d]", id, hole, start, end, score);
    }
}

3.3 区间图：构建、最大团、完美消除序

package com.example.mole;

import java.util.*;

/**
 * 区间图：顶点是区间，相交则连边。
 * 由于区间图是弦图，按右端点排序天然是完美消除序（PEO）。
 */
public class IntervalGraph {
    private final List<Mole> sorted;            // 按右端点升序 = PEO
    private final List<List<Integer>> adj;      // 邻接表（基于 PEO 下标）
    private final long[][] cliqueWeights;       // 每个顶点的后续邻居团（含自身）

    public IntervalGraph(List<Mole> moles) {
        this.sorted = new ArrayList<>(moles);
        Collections.sort(this.sorted);          // 触发 compareTo，得到 PEO
        int n = sorted.size();
        adj = new ArrayList<>(n);
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        // O(n^2) 建图：n 通常在数千以内，足够
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (sorted.get(i).conflicts(sorted.get(j))) {
                    adj.get(i).add(j);          // 只保留"后续邻居"（PEO 中下标更大者）
                }
            }
        }
        cliqueWeights = new long[n][];
        for (int i = 0; i < n; i++) buildClique(i);
    }

    /** 顶点 i 在 PEO 后缀中的邻居集合应当构成团，这里顺便做一次校验 */
    private void buildClique(int i) {
        List<Integer> nbrs = adj.get(i);
        for (int a = 0; a < nbrs.size(); a++) {
            for (int b = a + 1; b < nbrs.size(); b++) {
                if (!conflictsByIndex(nbrs.get(a), nbrs.get(b))) {
                    throw new IllegalStateException(
                        "PEO 校验失败：i=" + i + " 的后续邻居未成团，说明输入不是区间图");
                }
            }
        }
        cliqueWeights[i] = new long[nbrs.size() + 1];
        cliqueWeights[i][0] = sorted.get(i).score;
        for (int k = 0; k < nbrs.size(); k++) {
            cliqueWeights[i][k + 1] = sorted.get(nbrs.get(k)).score;
        }
    }

    private boolean conflictsByIndex(int a, int b) {
        return sorted.get(a).conflicts(sorted.get(b));
    }

    public int size() { return sorted.size(); }
    public Mole moleAt(int i) { return sorted.get(i); }
    public List<Integer> laterNeighbors(int i) { return adj.get(i); }
    /** 顶点 i 及其后续邻居的权重（团内最多选一个） */
    public long[] cliqueOf(int i) { return cliqueWeights[i]; }

    /** 输出区间图统计信息，便于观察团大小（= 同一时刻最多几只地鼠） */
    public void printStats() {
        int maxClique = 0;
        for (int i = 0; i < size(); i++) maxClique = Math.max(maxClique, adj.get(i).size() + 1);
        System.out.printf("区间图: |V|=%d, 最大团规模=%d%n", size(), maxClique);
    }
}

buildClique 里的断言非常关键：如果输入不满足”区间”语义（例如你手动塞了任意二元关系），PEO 校验会立刻失败。这是把理论性质写进代码做自检的典型手法。

3.4 加权区间调度 DP（推荐解法）

package com.example.mole;

import java.util.*;

/**
 * 加权区间调度：dp[j] = max(dp[j-1], w_j + dp[p(j)])
 * 其中 p(j) 是最靠后的、与 j 不冲突的区间下标。
 * 由于 sorted 已按右端点升序，p(j) 可用二分查找得到。
 */
public class WeightedIntervalScheduler {
    private final List<Mole> sorted;
    private final long[] dp;      // dp[j] 表示前 j+1 个区间的最大总分
    private final int[] prev;     // 决策回溯

    public WeightedIntervalScheduler(List<Mole> moles) {
        this.sorted = new ArrayList<>(moles);
        Collections.sort(this.sorted);
        int n = sorted.size();
        dp = new long[n];
        prev = new int[n];
        for (int j = 0; j < n; j++) {
            int p = lastCompatible(j);
            long takeScore = sorted.get(j).score + (p >= 0 ? dp[p] : 0);
            long skipScore = j > 0 ? dp[j - 1] : 0;
            if (takeScore >= skipScore) {
                dp[j] = takeScore;
                prev[j] = p;          // 选择 j，前驱为 p
            } else {
                dp[j] = skipScore;
                prev[j] = j - 1;      // 跳过 j
            }
        }
    }

    /** 二分：找到右端点严格小于 sorted[j].start 的最后一支地鼠 */
    private int lastCompatible(int j) {
        int lo = 0, hi = j - 1, ans = -1;
        int start = sorted.get(j).start;
        while (lo <= hi) {
            int mid = (lo + hi) >>> 1;
            if (sorted.get(mid).end < start) {  // 闭区间：end == start 仍冲突
                ans = mid;
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return ans;
    }

    public long bestScore() { return dp.length == 0 ? 0 : dp[dp.length - 1]; }

    /** 回溯出被选中的地鼠序列（按时间顺序） */
    public List<Mole> chosen() {
        List<Mole> out = new ArrayList<>();
        int j = dp.length - 1;
        while (j >= 0) {
            int p = prev[j];
            // 判断 j 是"选"还是"跳"
            boolean took = (p == -1 && dp[j] == sorted.get(j).score)
                        || (p >= 0 && dp[j] == sorted.get(j).score + dp[p]);
            if (took) {
                out.add(sorted.get(j));
                j = p;
            } else {
                j = j - 1;
            }
        }
        Collections.reverse(out);
        return out;
    }
}

3.5 完美消除序贪心（用于对拍）

package com.example.mole;

import java.util.*;

/**
 * 基于弦图完美消除序的贪心：逆序处理顶点，
 * 每次在"自身 + 后续邻居团"中选择最优的一个。
 * 权重非负时该贪心可证明最优（团内至多选一个，局部最优即全局最优）。
 */
public class GreedyPeoSolver {
    public static long solve(IntervalGraph g) {
        int n = g.size();
        boolean[] blocked = new boolean[n];   // blocked[i] 表示 i 的某个"后续邻居"已被选中
        boolean[] taken = new boolean[n];     // taken[i] 表示 i 被选中
        long total = 0;
        // 逆序 PEO：从右端点最大者开始
        for (int i = n - 1; i >= 0; i--) {
            if (blocked[i]) continue;
            // 在当前顶点与其后续邻居中挑权重最大者
            int best = i;
            for (int nb : g.laterNeighbors(i)) {
                if (!taken[nb] && g.moleAt(nb).score > g.moleAt(best).score) best = nb;
            }
            taken[best] = true;
            total += g.moleAt(best).score;
            // best 一旦被选，它的所有"较早邻居"都要被封锁
            // 这里简化：把所有与该顶点冲突的顶点标记为 blocked
            for (int k = 0; k < n; k++) {
                if (k != best && !taken[k] && g.moleAt(k).conflicts(g.moleAt(best))) {
                    blocked[k] = true;
                }
            }
        }
        return total;
    }
}

实现说明：这段贪心是作为对照实验写的，不用于生产。它按完美消除序逆序贪心，看起来”每次取团内最重者”很合理，但贪心对加权独立集并不普遍最优——在某些实例上它会因为提前锁定了一个重顶点而错失两个中等顶点之和。所以运行 Main 时：
– 若贪心结果等于 DP 结果，说明这个实例上贪心恰好最优，双方互相印证；
– 若贪心结果小于 DP 结果，说明贪心不是最优，DP 的答案才是对的。
这个”对拍”设计本身也是一条工程经验：任何启发式都必须有一个可证明最优的参照物来校核，否则你无法察觉它何时失效。

3.6 游戏模拟与入口

package com.example.mole;

import java.util.*;

public class MoleGame {
    private final Random rnd;
    private final int holes, horizon, maxSpawn;

    public MoleGame(long seed) {
        this.rnd = new Random(seed);
        this.holes = 8;
        this.horizon = 200;     // 总时长 200 个时间槽
        this.maxSpawn = 60;     // 最多 60 只地鼠
    }

    /** 随机生成一批地鼠：分值与其停留时长反相关（露头越短越值钱） */
    public List<Mole> spawnMoles() {
        List<Mole> list = new ArrayList<>();
        int last = 0;
        for (int id = 0; id < maxSpawn; id++) {
            int start = last + rnd.nextInt(3);          // 稀疏分布，便于观察
            int dur = 3 + rnd.nextInt(12);
            int end = Math.min(horizon, start + dur);
            if (start >= horizon) break;
            int score = 1 + (150 - dur * 10) / 20;
            list.add(new Mole(id, rnd.nextInt(holes), start, end, Math.max(1, score)));
            last = start + 1;
        }
        return list;
    }
}

public class Main {
    public static void main(String[] args) {
        MoleGame game = new MoleGame(20261029L);
        List<Mole> moles = game.spawnMoles();
        System.out.println("生成地鼠 " + moles.size() + " 只");

        // 1) DP 求解
        WeightedIntervalScheduler dp = new WeightedIntervalScheduler(moles);
        List<Mole> chosen = dp.chosen();
        System.out.println("DP 最优总分 = " + dp.bestScore() + "，击打 " + chosen.size() + " 只");
        for (Mole m : chosen) System.out.println("  " + m);

        // 2) 用区间图 + 完美消除序验证
        IntervalGraph graph = new IntervalGraph(moles);
        graph.printStats();
        long greedy = GreedyPeoSolver.solve(graph);
        System.out.println("弦图贪心总分 = " + greedy
            + (greedy == dp.bestScore()
                ? "  ✔ 该实例上贪心恰好最优"
                : "  ▲ 贪心劣于 DP，说明本例中局部最优选择牺牲了全局最优（DP 结果为准）"));

        // 3) 冲突自检：被选中的地鼠之间必须两两不冲突
        for (int i = 0; i < chosen.size(); i++) {
            for (int j = i + 1; j < chosen.size(); j++) {
                if (chosen.get(i).conflicts(chosen.get(j))) {
                    System.out.println("错误：选中集合存在冲突！");
                }
            }
        }
    }
}

pom.xml 只需最简配置：

<project xmlns="http://maven.apache.org/POM/4.0.0">
  <modelVersion>4.0.0</modelVersion>
  <groupId>com.example</groupId>
  <artifactId>mole-whack</artifactId>
  <version>1.0.0</version>
  <properties>
    <maven.compiler.source>17</maven.compiler.source>
    <maven.compiler.target>17</maven.compiler.target>
  </properties>
</project>

运行：mvn -q compile exec:java -Dexec.mainClass=com.example.mole.Main

四、复杂度分析

注意 n 是地鼠总数而不是时间槽数。实战里一局 200 槽、60 只地鼠，DP 耗时在微秒级；即便一分钟长局（数千只），仍然在毫秒级。

五、为什么这个模型比”贪心最短移动”更强

很多人第一反应是”哪只地鼠先消失先打哪只”，即经典的最早截止时间优先（EDF）。EDF 在单机、无移动开销、权值全为 1 的场景下确实最优（这就是区间调度的贪心可解性），但在打地鼠里会失效：一只 1 分的短命地鼠可能让你错过后面 10 分的长寿地鼠。加权区间调度把这个直觉量化了：它允许”跳过低价值冲突项”，其正确性由区间图弦性提供的团结构支撑。

进一步还可以把结论推广两个方向：

• 多锤子（多线程玩家）：等价于”区间图的 k 着色与最大权 k-独立集”，权重全为 1 时是区间图着色贪心（按左端点排序分配最早可用锤子），复杂度 O(n log k)。
• 带惩罚的爽约：地鼠若未被击打会扣分，此时把”跳过”赋予负权，DP 的 skipScore 分支需要并入 -penalty，模型依然成立（只是权重不再全正，PEO 贪心的最优性需重新论证，DP 始终正确）。

这两点正是区间图作为”结构化 NP-hard 问题”的价值：图的结构性质决定算法能走多远。下回看到”一段时间内只能做一件事”的需求，先问问自己——这些任务能不能画成区间？