每日算法 — 使用java实现多米诺骨牌：链式反应模拟与图论最长路径

引言

多米诺骨牌是一种经典的连锁反应游戏。将若干骨牌按特定间距竖直排列，推倒第一块后，后续骨牌会依次倒下形成壮观的链式反应。本文用Java实现一个带物理模拟的多米诺骨牌系统，讲解如何将骨牌排列建模为有向图，并通过拓扑排序检测有效排列，利用最长路径算法计算最大连锁长度，同时用简单的刚体物理模拟骨牌倾倒过程。

核心算法思路

1. 骨牌建模与图构建

每块骨牌抽象为一个节点，若骨牌A倒下后能碰到骨牌B，则在图中添加一条有向边 A → B。整个排列构成一个有向图。若图中存在环，则某些骨牌会互相推倒形成死循环，物理上不可能稳定实现，因此有效排列必须是有向无环图（DAG）。

2. 拓扑排序验证

使用 Kahn算法（入度减零法）对图进行拓扑排序。若排序后节点数等于总节点数，说明无环，排列有效。

3. 最长路径计算

在DAG中，从起点到任意节点的最长路径可通过动态规划求解：
– dp[v] = max(dp[u] + 1)，其中 u → v 是图中所有入边
– 按拓扑序遍历，保证计算 dp[v] 时所有 dp[u] 已确定

4. 物理碰撞检测

每块骨牌倒下时绕底部旋转，当顶部碰到下一块骨牌的中心区域时触发连锁。通过几何计算判断碰撞是否发生。

完整Java实现

import java.util.*;

/**
 * 多米诺骨牌链式反应模拟系统
 * 核心算法：拓扑排序 + DAG最长路径 + 刚体碰撞检测
 */
public class DominoSimulator {

    // 骨牌类
    static class Domino {
        int id;           // 编号
        double x, y;      // 底部中心坐标
        double width;     // 骨牌宽度
        double height;    // 骨牌高度
        boolean fallen;   // 是否已倒下
        double fallAngle; // 倾倒角度（弧度，0表示竖直）
        List<Domino> next = new ArrayList<>(); // 能推倒的骨牌列表

        Domino(int id, double x, double y, double width, double height) {
            this.id = id;
            this.x = x;
            this.y = y;
            this.width = width;
            this.height = height;
            this.fallen = false;
            this.fallAngle = 0;
        }

        // 计算骨牌顶部坐标（考虑倾倒角度）
        double topX() {
            return x + height * Math.sin(fallAngle);
        }

        double topY() {
            return y + height * Math.cos(fallAngle);
        }
    }

    // 图节点，用于拓扑排序
    static class GraphNode {
        int id;
        List<Integer> edges = new ArrayList<>(); // 出边
        int inDegree = 0; // 入度
    }

    private List<Domino> dominoes;
    private Map<Integer, GraphNode> graph;

    public DominoSimulator(List<Domino> dominoes) {
        this.dominoes = dominoes;
        this.graph = new HashMap<>();
    }

    /**
     * 构建有向图：判断每块骨牌倒下后能碰到哪些其他骨牌
     */
    public void buildGraph() {
        for (Domino d : dominoes) {
            graph.putIfAbsent(d.id, new GraphNode());
            graph.get(d.id).id = d.id;
        }

        for (int i = 0; i < dominoes.size(); i++) {
            Domino a = dominoes.get(i);
            // 骨牌a倒下后顶部位置（假设完全倒下，角度约75度）
            double fallX = a.x + a.height * Math.sin(Math.toRadians(75));
            double fallY = a.y + a.height * Math.cos(Math.toRadians(75));

            for (int j = 0; j < dominoes.size(); j++) {
                if (i == j) continue;
                Domino b = dominoes.get(j);
                // 判断倒下后的顶部是否落在b的中心区域
                double dist = Math.hypot(fallX - b.x, fallY - b.y);
                if (dist < b.height * 0.6 && b.x > a.x) {
                    // a能推倒b，添加边 a -> b
                    graph.get(a.id).edges.add(b.id);
                    graph.get(b.id).inDegree++;
                }
            }
        }
    }

    /**
     * Kahn算法拓扑排序，验证图是否为DAG
     * @return 拓扑序列表，若存在环返回null
     */
    public List<Integer> topologicalSort() {
        Queue<Integer> queue = new LinkedList<>();
        Map<Integer, Integer> inDegreeMap = new HashMap<>();

        for (GraphNode node : graph.values()) {
            inDegreeMap.put(node.id, node.inDegree);
            if (node.inDegree == 0) {
                queue.offer(node.id);
            }
        }

        List<Integer> topoOrder = new ArrayList<>();
        while (!queue.isEmpty()) {
            int u = queue.poll();
            topoOrder.add(u);
            for (int v : graph.get(u).edges) {
                int newDeg = inDegreeMap.get(v) - 1;
                inDegreeMap.put(v, newDeg);
                if (newDeg == 0) {
                    queue.offer(v);
                }
            }
        }

        // 若拓扑序节点数小于总节点数，说明存在环
        if (topoOrder.size() < graph.size()) {
            System.out.println("警告：骨牌排列存在环，无法形成有效链式反应！");
            return null;
        }
        return topoOrder;
    }

    /**
     * 在DAG上求最长路径（最大连锁骨牌数）
     * @param topoOrder 拓扑序
     * @return 最长路径长度
     */
    public int longestChain(List<Integer> topoOrder) {
        Map<Integer, Integer> dp = new HashMap<>();
        for (int id : topoOrder) {
            dp.put(id, 1); // 至少包含自己
        }

        int maxLen = 1;
        for (int u : topoOrder) {
            for (int v : graph.get(u).edges) {
                if (dp.get(v) < dp.get(u) + 1) {
                    dp.put(v, dp.get(u) + 1);
                    maxLen = Math.max(maxLen, dp.get(v));
                }
            }
        }
        return maxLen;
    }

    /**
     * 模拟链式反应过程
     * @param startId 起始骨牌编号
     */
    public void simulateChainReaction(int startId) {
        Queue<Domino> queue = new LinkedList<>();
        Domino start = dominoes.stream().filter(d -> d.id == startId).findFirst().orElse(null);
        if (start == null) return;

        start.fallen = true;
        start.fallAngle = Math.toRadians(75);
        queue.offer(start);

        System.out.println("=== 链式反应模拟开始 ===");
        int step = 0;
        while (!queue.isEmpty()) {
            Domino current = queue.poll();
            step++;
            System.out.printf("步骤%d: 骨牌%d倒下 (位置: %.1f, %.1f)\n",
                step, current.id, current.x, current.y);

            // 查找能推倒的下一批骨牌
            for (int nextId : graph.get(current.id).edges) {
                Domino next = dominoes.stream().filter(d -> d.id == nextId).findFirst().orElse(null);
                if (next != null && !next.fallen) {
                    next.fallen = true;
                    next.fallAngle = Math.toRadians(75);
                    queue.offer(next);
                }
            }
        }
        System.out.println("=== 链式反应结束，共倒下 " + step + " 块骨牌 ===");
    }

    /**
     * 打印图的邻接表
     */
    public void printGraph() {
        System.out.println("=== 骨牌推倒关系图 ===");
        for (GraphNode node : graph.values()) {
            System.out.print("骨牌" + node.id + " -> ");
            for (int v : node.edges) {
                System.out.print("骨牌" + v + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        // 创建7块直线排列的骨牌，间距略小于高度
        List<Domino> list = new ArrayList<>();
        for (int i = 0; i < 7; i++) {
            list.add(new Domino(i, i * 35, 0, 10, 50));
        }

        DominoSimulator sim = new DominoSimulator(list);
        sim.buildGraph();
        sim.printGraph();

        List<Integer> topo = sim.topologicalSort();
        if (topo != null) {
            System.out.println("拓扑排序结果: " + topo);
            int maxChain = sim.longestChain(topo);
            System.out.println("最长连锁路径: " + maxChain + " 块骨牌");
            sim.simulateChainReaction(0);
        }

        // 测试环形排列（应检测出环）
        System.out.println("\n=== 环形排列测试 ===");
        List<Domino> circle = new ArrayList<>();
        circle.add(new Domino(0, 0, 0, 10, 50));
        circle.add(new Domino(1, 40, 0, 10, 50));
        circle.add(new Domino(2, 20, 40, 10, 50)); // 形成三角，互相推倒
        DominoSimulator circleSim = new DominoSimulator(circle);
        circleSim.buildGraph();
        circleSim.topologicalSort(); // 应输出警告
    }
}

算法复杂度分析

扩展方向

1. 分支骨牌：一块骨牌可推倒多块，形成树形结构，最长路径算法依然适用
2. 三维排列：引入z坐标，用空间哈希加速碰撞检测
3. 延时触发：部分骨牌需要多块前驱同时倒下才触发，可用”与门”逻辑建模
4. 最优布局：给定骨牌数量，用遗传算法搜索能形成最长链的平面布局

总结

本文将多米诺骨牌游戏抽象为有向图问题，通过拓扑排序验证排列可行性，利用DAG最长路径算法计算最大连锁效应，并辅以物理碰撞检测完成完整模拟。核心思想是：将物理世界的连锁反应转化为图论中的路径问题，体现了算法建模的强大威力。