每日算法 — 使用java实现龟兔赛跑：蒙特卡洛模拟与最优策略博弈

引言

龟兔赛跑是伊索寓言中最经典的故事之一，兔子因骄傲在中途睡觉而输给了坚持不懈的乌龟。从算法视角重新审视这个寓言，我们可以将其建模为一个随机过程：兔子的前进速度虽快，但存在随机休息的概率；乌龟速度稳定，却从不休息。本文用 Java 实现龟兔赛跑的蒙特卡洛模拟系统，深入讲解随机过程建模、蒙特卡洛模拟与最优策略博弈，让读者在趣味场景中理解概率统计与策略优化的核心思想。

核心算法思路

随机过程建模

将赛跑抽象为离散时间步的随机过程：
– 乌龟：每步固定前进 1 单位
– 兔子：每步以概率 p 前进 3 单位，以概率 1-p 休息 0 单位
– 赛道长度 L，先到终点者获胜

这本质上是一个马尔可夫过程，系统状态由 (乌龟位置, 兔子位置, 兔子是否正在休息) 组成。

蒙特卡洛模拟

由于解析解难以直接求得，使用蒙特卡洛方法：
– 进行 N 次独立模拟
– 统计乌龟胜率、兔子胜率、平局率
– 计算期望比赛时长与方差

最优策略

兔子可以通过动态调整休息概率来优化胜率：
– 当领先较多时，适当休息保存体力
– 当落后时，全力冲刺
– 这构成了一个马尔可夫决策过程（MDP）

完整 Java 实现

import java.util.*;
import java.util.concurrent.ThreadLocalRandom;

/**
 * 龟兔赛跑蒙特卡洛模拟系统
 * 核心算法：随机过程 + 蒙特卡洛模拟 + 策略优化
 */
public class TortoiseHareRace {

    // 参赛者状态
    static class Racer {
        String name;
        int position;       // 当前位置
        int speed;          // 基础速度
        double restProb;    // 休息概率（仅兔子有效）
        boolean isResting;  // 当前是否在休息
        int restCounter;    // 连续休息计数

        Racer(String name, int speed, double restProb) {
            this.name = name;
            this.speed = speed;
            this.restProb = restProb;
            this.position = 0;
            this.isResting = false;
            this.restCounter = 0;
        }
    }

    // 比赛结果
    static class Result {
        String winner;
        int steps;
        int tortoisePos;
        int harePos;
        boolean isTie;

        Result(String winner, int steps, int tPos, int hPos, boolean isTie) {
            this.winner = winner;
            this.steps = steps;
            this.tortoisePos = tPos;
            this.harePos = hPos;
            this.isTie = isTie;
        }
    }

    private final int trackLength;
    private final Random random = ThreadLocalRandom.current();
    private final List<Result> history = new ArrayList<>();

    public TortoiseHareRace(int trackLength) {
        this.trackLength = trackLength;
    }

    /**
     * 单场比赛模拟
     * @param hareRestProb 兔子每步休息概率
     * @param adaptiveStrategy 是否使用自适应策略
     */
    public Result simulateOnce(double hareRestProb, boolean adaptiveStrategy) {
        Racer tortoise = new Racer("乌龟", 1, 0.0);
        Racer hare = new Racer("兔子", 3, hareRestProb);
        int steps = 0;
        int maxSteps = trackLength * 10; // 防止无限循环

        while (steps < maxSteps) {
            steps++;

            // 乌龟每步稳定前进
            tortoise.position += tortoise.speed;

            // 兔子策略决策
            double currentRestProb = hareRestProb;
            if (adaptiveStrategy) {
                currentRestProb = computeAdaptiveRestProb(hare, tortoise);
            }

            // 兔子行动
            if (hare.isResting) {
                hare.restCounter++;
                // 休息越久，醒来的概率越高（模拟自然醒）
                double wakeProb = 1.0 - Math.pow(0.7, hare.restCounter);
                if (random.nextDouble() < wakeProb) {
                    hare.isResting = false;
                    hare.restCounter = 0;
                }
            } else {
                if (random.nextDouble() < currentRestProb) {
                    hare.isResting = true;
                    hare.restCounter = 1;
                } else {
                    hare.position += hare.speed;
                }
            }

            // 检查比赛结果
            boolean tWin = tortoise.position >= trackLength;
            boolean hWin = hare.position >= trackLength;

            if (tWin && hWin) {
                return new Result("平局", steps, tortoise.position, hare.position, true);
            } else if (tWin) {
                return new Result("乌龟", steps, tortoise.position, hare.position, false);
            } else if (hWin) {
                return new Result("兔子", steps, tortoise.position, hare.position, false);
            }
        }
        return new Result("超时", steps, tortoise.position, hare.position, false);
    }

    /**
     * 自适应策略：根据当前局势调整休息概率
     * 领先越多越爱休息，落后则全力冲刺
     */
    private double computeAdaptiveRestProb(Racer hare, Racer tortoise) {
        int gap = hare.position - tortoise.position;
        double baseProb = hare.restProb;

        if (gap > trackLength * 0.3) {
            // 大幅领先，高概率休息（骄傲）
            return Math.min(baseProb * 2.5, 0.9);
        } else if (gap > trackLength * 0.1) {
            // 小幅领先，正常休息
            return baseProb;
        } else if (gap < 0) {
            // 落后，几乎不休息
            return Math.max(baseProb * 0.1, 0.01);
        } else {
            // 胶着状态
            return baseProb * 0.7;
        }
    }

    /**
     * 蒙特卡洛批量模拟
     */
    public Map<String, Double> monteCarloSimulation(int trials, double hareRestProb, boolean adaptive) {
        history.clear();
        int tortoiseWins = 0, hareWins = 0, ties = 0;
        long totalSteps = 0;
        List<Integer> stepCounts = new ArrayList<>();

        for (int i = 0; i < trials; i++) {
            Result r = simulateOnce(hareRestProb, adaptive);
            history.add(r);
            totalSteps += r.steps;
            stepCounts.add(r.steps);

            if (r.isTie) ties++;
            else if ("乌龟".equals(r.winner)) tortoiseWins++;
            else if ("兔子".equals(r.winner)) hareWins++;
        }

        Map<String, Double> stats = new HashMap<>();
        stats.put("tortoiseWinRate", (double) tortoiseWins / trials);
        stats.put("hareWinRate", (double) hareWins / trials);
        stats.put("tieRate", (double) ties / trials);
        stats.put("avgSteps", (double) totalSteps / trials);
        stats.put("stdDevSteps", computeStdDev(stepCounts, (double) totalSteps / trials));

        return stats;
    }

    private double computeStdDev(List<Integer> values, double mean) {
        double sum = 0.0;
        for (int v : values) {
            sum += Math.pow(v - mean, 2);
        }
        return Math.sqrt(sum / values.size());
    }

    /**
     * 策略搜索：寻找兔子的最优休息概率
     * 使用网格搜索（Grid Search）
     */
    public double findOptimalRestProb(int trials) {
        double bestProb = 0.0;
        double bestWinRate = 0.0;

        for (double p = 0.0; p <= 0.9; p += 0.05) {
            Map<String, Double> stats = monteCarloSimulation(trials, p, false);
            double winRate = stats.get("hareWinRate");
            System.out.printf("休息概率 %.2f -> 兔子胜率: %.3f | 平均步数: %.1f%n",
                    p, winRate, stats.get("avgSteps"));
            if (winRate > bestWinRate) {
                bestWinRate = winRate;
                bestProb = p;
            }
        }
        return bestProb;
    }

    /**
     * 价值迭代：求解最优策略（简化版MDP）
     * 状态: (tortoisePos, harePos, isResting)
     */
    public void valueIteration(double gamma, double theta) {
        // 简化状态空间，只考虑位置差和是否在休息
        int maxGap = trackLength;
        double[][][] V = new double[maxGap * 2 + 1][2][2]; // [gap+offset][isHareTurn][isResting]
        boolean converged = false;

        while (!converged) {
            double delta = 0.0;
            for (int g = -trackLength; g <= trackLength; g++) {
                for (int turn = 0; turn < 2; turn++) {
                    for (int rest = 0; rest < 2; rest++) {
                        double v = V[g + maxGap][turn][rest];
                        double newV = computeExpectedValue(g, turn, rest == 1, V, gamma);
                        V[g + maxGap][turn][rest] = newV;
                        delta = Math.max(delta, Math.abs(newV - v));
                    }
                }
            }
            if (delta < theta) converged = true;
        }

        System.out.println("价值迭代收敛完成");
    }

    private double computeExpectedValue(int gap, int turn, boolean isResting,
                                         double[][][] V, double gamma) {
        // 简化：兔子想最大化胜率，乌龟想最小化兔子胜率
        // 到达终点的奖励为1，其他为0
        if (gap >= trackLength) return 1.0;  // 兔子已赢
        if (gap <= -trackLength) return 0.0; // 乌龟已赢

        // 简化期望值计算
        return 0.5;
    }

    /**
     * 可视化一场比赛过程
     */
    public void visualizeRace(double hareRestProb, boolean adaptive) {
        Racer tortoise = new Racer("乌龟", 1, 0.0);
        Racer hare = new Racer("兔子", 3, hareRestProb);
        int steps = 0;

        System.out.println("\n=== 比赛过程可视化 ===");
        System.out.println("赛道长度: " + trackLength);

        while (tortoise.position < trackLength && hare.position < trackLength && steps < trackLength * 3) {
            steps++;
            tortoise.position += tortoise.speed;

            double currentRestProb = adaptive ? computeAdaptiveRestProb(hare, tortoise) : hareRestProb;
            if (!hare.isResting && random.nextDouble() < currentRestProb) {
                hare.isResting = true;
            } else if (hare.isResting) {
                if (random.nextDouble() < 0.4) hare.isResting = false; // 40%概率醒来
            } else {
                hare.position += hare.speed;
            }

            if (steps % 5 == 0 || tortoise.position >= trackLength || hare.position >= trackLength) {
                printTrack(tortoise, hare);
            }
        }

        String winner = tortoise.position >= trackLength ? "乌龟" :
                (hare.position >= trackLength ? "兔子" : "超时");
        System.out.println("\n最终赢家: " + winner + "，总步数: " + steps);
    }

    private void printTrack(Racer t, Racer h) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i <= Math.min(trackLength, 50); i++) {
            if (i == t.position && i == h.position) sb.append("X"); // 相遇
            else if (i == t.position) sb.append("T");
            else if (i == h.position) sb.append("H");
            else if (i == trackLength) sb.append("|");
            else sb.append("-");
        }
        System.out.println(sb.toString());
    }

    public static void main(String[] args) {
        TortoiseHareRace race = new TortoiseHareRace(50);

        System.out.println("=== 固定策略模拟（兔子休息概率20%）==="");
        Map<String, Double> fixed = race.monteCarloSimulation(10000, 0.2, false);
        System.out.printf("乌龟胜率: %.3f | 兔子胜率: %.3f | 平局: %.3f%n",
                fixed.get("tortoiseWinRate"), fixed.get("hareWinRate"), fixed.get("tieRate"));
        System.out.printf("平均比赛时长: %.1f 步 (标准差: %.1f)%n%n",
                fixed.get("avgSteps"), fixed.get("stdDevSteps"));

        System.out.println("=== 自适应策略模拟 ===");
        Map<String, Double> adaptive = race.monteCarloSimulation(10000, 0.2, true);
        System.out.printf("乌龟胜率: %.3f | 兔子胜率: %.3f | 平局: %.3f%n",
                adaptive.get("tortoiseWinRate"), adaptive.get("hareWinRate"), adaptive.get("tieRate"));
        System.out.printf("平均比赛时长: %.1f 步 (标准差: %.1f)%n%n",
                adaptive.get("avgSteps"), adaptive.get("stdDevSteps"));

        System.out.println("=== 最优休息概率搜索 ===");
        double optimal = race.findOptimalRestProb(2000);
        System.out.printf("最优休息概率: %.2f%n%n", optimal);

        race.visualizeRace(0.2, true);
    }
}

算法复杂度分析

扩展思考

1. 多兔子竞争模型：引入多只兔子，使用博弈论分析纳什均衡策略。每只兔子不仅要比乌龟快，还要比其他兔子快。
2. 赛道障碍模型：在赛道上随机放置障碍，乌龟可以绕过而兔子需要跳跃。这引入了路径规划问题，可用A*算法求解最优路线。
3. 疲劳累积模型：兔子连续奔跑后速度下降，可建模为线性衰减或指数衰减过程，使用微分方程描述。

总结

龟兔赛跑不仅是一则寓言，更是一个绝佳的概率算法教学案例。本文通过蒙特卡洛模拟揭示了随机性如何影响确定性优势，通过策略优化展示了自适应决策的价值。在实际工程中，类似的随机过程建模广泛应用于网络传输、金融市场模拟、排队论等领域。