每日算法 — 使用java实现青蛙过河：蒙特卡洛模拟与概率最优跳跃策略

引言

青蛙过河是一款经典的益智游戏：青蛙需要从河岸一侧通过若干荷叶跳到对岸。每片荷叶存在一定的承重概率，青蛙落脚后荷叶可能沉没。玩家需要在有限的生命值内，选择最优的跳跃路径到达对岸。本文用Java实现该游戏，重点讲解蒙特卡洛模拟（Monte Carlo Simulation）评估各路径的成功概率，并基于概率最大化策略决策最优跳跃序列。

核心算法思路

1. 问题建模

将过河场景抽象为图结构：
– 节点：每片荷叶及两岸
– 边：青蛙可跳跃的距离范围内的荷叶对
– 权重：荷叶沉没概率（动态变化）

青蛙每次跳跃后，落脚荷叶以一定概率沉没，沉没后该节点永久失效。目标是找到期望成功率最高的路径。

2. 蒙特卡洛模拟

蒙特卡洛方法通过大量随机采样估计复杂系统的统计特性。对于青蛙过河：
– 对候选路径进行 N 次独立模拟
– 每次模拟中，按荷叶沉没概率随机决定是否沉没
– 统计成功到达对岸的次数比例，作为该路径的期望成功率

3. 概率最优策略

对每个可达的下一跳目标，用蒙特卡洛模拟评估从该位置到终点的成功概率，选择概率最大的方向。

Java 实现

import java.util.*;

/**
 * 青蛙过河 - 蒙特卡洛模拟与概率最优跳跃策略
 */
public class FrogCrossingRiver {

    // 荷叶节点
    static class LilyPad {
        int id;
        double x, y;           // 坐标位置
        double sinkProb;       // 单次踩踏后沉没概率
        boolean sunk = false;  // 是否已沉没

        LilyPad(int id, double x, double y, double sinkProb) {
            this.id = id; this.x = x; this.y = y; this.sinkProb = sinkProb;
        }

        LilyPad copy() {
            LilyPad p = new LilyPad(id, x, y, sinkProb);
            p.sunk = sunk;
            return p;
        }
    }

    // 游戏状态
    static class GameState {
        List<LilyPad> pads;
        int frogPos;  // 当前所在荷叶id，-1表示左岸，-2表示右岸

        GameState(List<LilyPad> pads, int frogPos) {
            this.pads = pads; this.frogPos = frogPos;
        }

        GameState copy() {
            List<LilyPad> np = new ArrayList<>();
            for (LilyPad p : pads) np.add(p.copy());
            return new GameState(np, frogPos);
        }
    }

    final double maxJumpDist;   // 青蛙最大跳跃距离
    final int monteCarloRuns;   // 蒙特卡洛模拟次数
    final Random rand = new Random(42);

    public FrogCrossingRiver(double maxJumpDist, int monteCarloRuns) {
        this.maxJumpDist = maxJumpDist;
        this.monteCarloRuns = monteCarloRuns;
    }

    // 计算两点距离
    double dist(LilyPad a, LilyPad b) {
        return Math.hypot(a.x - b.x, a.y - b.y);
    }

    /**
     * 获取从当前位置可跳跃的所有目标
     */
    List<Integer> getReachable(GameState state) {
        List<Integer> targets = new ArrayList<>();
        double cx, cy;
        if (state.frogPos == -1) { // 左岸
            cx = 0; cy = 0;
        } else {
            LilyPad cur = state.pads.get(state.frogPos);
            if (cur.sunk) return targets;
            cx = cur.x; cy = cur.y;
        }
        // 右岸作为目标
        double rightBankX = 100.0;
        if (Math.abs(rightBankX - cx) <= maxJumpDist) {
            targets.add(-2);
        }
        // 各荷叶作为目标
        for (int i = 0; i < state.pads.size(); i++) {
            LilyPad p = state.pads.get(i);
            if (p.sunk || i == state.frogPos) continue;
            if (Math.hypot(p.x - cx, p.y - cy) <= maxJumpDist) {
                targets.add(i);
            }
        }
        return targets;
    }

    /**
     * 单次蒙特卡洛模拟：从给定状态出发，随机策略走到终点，返回是否成功
     */
    boolean simulateOnce(GameState initState) {
        GameState state = initState.copy();
        while (true) {
            List<Integer> reachable = getReachable(state);
            // 如果能直接到右岸，优先尝试
            if (reachable.contains(-2)) {
                // 先处理当前荷叶沉没
                if (state.frogPos >= 0) {
                    LilyPad cur = state.pads.get(state.frogPos);
                    if (rand.nextDouble() < cur.sinkProb) {
                        cur.sunk = true; // 沉没，青蛙落水失败
                        return false;
                    }
                }
                return true; // 成功到达右岸
            }
            // 过滤掉已沉没和不可达的
            reachable.removeIf(id -> id == -2);
            if (reachable.isEmpty()) return false;

            // 随机选择下一跳（模拟中可用任意策略，这里用随机）
            int next = reachable.get(rand.nextInt(reachable.size()));

            // 当前荷叶可能沉没
            if (state.frogPos >= 0) {
                LilyPad cur = state.pads.get(state.frogPos);
                if (rand.nextDouble() < cur.sinkProb) {
                    cur.sunk = true;
                    return false;
                }
            }
            state.frogPos = next;
        }
    }

    /**
     * 蒙特卡洛评估：从当前状态选择某目标后的期望成功率
     */
    double evaluateMove(GameState state, int targetId) {
        int success = 0;
        for (int i = 0; i < monteCarloRuns; i++) {
            GameState sim = state.copy();
            // 执行跳跃到targetId
            if (sim.frogPos >= 0) {
                LilyPad cur = sim.pads.get(sim.frogPos);
                if (rand.nextDouble() < cur.sinkProb) {
                    continue; // 起跳就沉没，算失败
                }
            }
            sim.frogPos = targetId;
            // 目标荷叶是否立即沉没（仅在踩踏后）
            if (targetId >= 0) {
                LilyPad target = sim.pads.get(targetId);
                if (rand.nextDouble() < target.sinkProb) {
                    continue; // 落脚沉没
                }
            }
            if (targetId == -2) {
                success++; // 到达右岸
            } else {
                if (simulateOnce(sim)) success++;
            }
        }
        return (double) success / monteCarloRuns;
    }

    /**
     * 决策最优下一跳
     */
    int decideBestMove(GameState state) {
        List<Integer> reachable = getReachable(state);
        if (reachable.isEmpty()) return -3; // 无路可走
        if (reachable.contains(-2)) return -2; // 能直接到对岸就直接跳

        double bestProb = -1;
        int bestId = -3;
        for (int target : reachable) {
            double prob = evaluateMove(state, target);
            if (prob > bestProb) {
                bestProb = prob;
                bestId = target;
            }
        }
        return bestId;
    }

    /**
     * 完整游戏流程
     */
    public boolean playGame(List<LilyPad> pads) {
        GameState state = new GameState(pads, -1);
        int moves = 0;
        final int maxMoves = 50;

        while (moves < maxMoves) {
            int move = decideBestMove(state);
            if (move == -3) {
                System.out.println("第" + moves + "步：无路可走，失败");
                return false;
            }
            if (move == -2) {
                System.out.println("第" + moves + "步：成功到达右岸！");
                return true;
            }
            LilyPad target = state.pads.get(move);
            System.out.printf("第%d步：从%d跳到荷叶%d (坐标%.1f,%.1f，沉没概率%.2f)%n",
                moves, state.frogPos, move, target.x, target.y, target.sinkProb);
            state.frogPos = move;
            moves++;
        }
        System.out.println("超过最大步数限制");
        return false;
    }

    public static void main(String[] args) {
        // 构造测试场景：河宽100，荷叶分布在中间区域
        List<LilyPad> pads = new ArrayList<>();
        pads.add(new LilyPad(0, 20, 10, 0.1));
        pads.add(new LilyPad(1, 25, -5, 0.15));
        pads.add(new LilyPad(2, 40, 8, 0.05));
        pads.add(new LilyPad(3, 45, -8, 0.2));
        pads.add(new LilyPad(4, 60, 5, 0.1));
        pads.add(new LilyPad(5, 70, -3, 0.08));
        pads.add(new LilyPad(6, 80, 7, 0.12));
        pads.add(new LilyPad(7, 55, -10, 0.18));
        pads.add(new LilyPad(8, 35, 12, 0.06));
        pads.add(new LilyPad(9, 85, -6, 0.14));

        FrogCrossingRiver game = new FrogCrossingRiver(30.0, 1000);
        boolean win = game.playGame(pads);
        System.out.println("游戏结果：" + (win ? "胜利" : "失败"));
    }
}

算法复杂度分析

优化方向

1. 重要性采样：对高沉没概率荷叶减少采样权重，聚焦关键路径
2. 并行模拟：利用多线程并行执行蒙特卡洛实验，降低决策延迟
3. 价值函数近似：用神经网络拟合状态价值，避免每次重复模拟
4. UCT 树搜索：结合蒙特卡洛树搜索（MCTS）在动作空间上做系统性探索

总结

本文通过蒙特卡洛模拟为青蛙过河游戏提供了概率最优的跳跃决策。核心思想是将不确定环境下的路径规划转化为统计估计问题，通过大量随机采样逼近真实的成功概率。这种方法不仅适用于游戏 AI，也广泛应用于金融风控、物流路径规划等存在不确定性的决策场景。