从算法到人工智能 · 第 19 课：蒙特卡洛——用随机"猜"出答案，以及元启发算法

前面 18 课，我们写的算法有一个共同点：确定性（deterministic）。同样的输入，走同样的步骤，永远得到同样的输出——排序、查找、Dijkstra、DP、回溯，都是这样。

但现实里有一大类问题，确定性算法要么慢到算不出来，要么根本写不出精确步骤：

• 圆周率 π 的精确值，怎么写个"确定性步骤"算出来？
• 一个复杂积分，没有初等原函数，怎么求？
• 一个 NP 难题（比如旅行商问题），穷举要算到宇宙毁灭，怎么办？

答案是：别追求"确定"，改成"随机 + 统计"。 靠大量随机试验，用频率去逼近概率，用平均值去逼近期望——这就是蒙特卡洛方法（Monte Carlo）。

而蒙特卡洛背后的思想，又自然引出一类更强大的算法——元启发算法（metaheuristic）：不保证找到最优解，但在可接受的时间内，用"随机扰动 + 智能接受"找到足够好的解。

这一课分两块：先讲蒙特卡洛（随机采样），再给元启发算法搭一个总纲（第 20、21 课的模拟退火、遗传算法都装在它下面）。

一、蒙特卡洛是什么：扔豆子数出来的 π

蒙特卡洛是摩纳哥的一座赌城。用赌城命名，是因为这个方法的核心就是随机性。

先看最经典的问题——用随机试验估算 π：

import random

def estimate_pi(n):
    """在边长为 1 的正方形里随机扔 n 个点，数落在 1/4 圆内的比例"""
    inside = 0
    for _ in range(n):
        x = random.random()   # 随机 x，范围 [0, 1)
        y = random.random()   # 随机 y，范围 [0, 1)
        if x * x + y * y <= 1.0:   # 点在半径为 1 的 1/4 圆内
            inside += 1
    return 4 * inside / n    # 比例 × 4 = π

print(estimate_pi(100_000))   # 每次跑都略有不同，约 3.14

原理：边长为 1 的正方形面积是 1，里面 1/4 圆的面积是 π/4。往正方形里均匀随机扔点，点落在圆里的概率 = 圆面积 / 正方形面积 = π/4。所以：

π ≈ 4 × (落在圆内的点数 / 总点数)

扔的点越多，比例越接近 π/4，估算越准。这个思路极其朴素，却极其强大。

二、蒙特卡洛的通用套路

把上面的例子抽象一下，蒙特卡洛就是三步：

1. 把问题转化成一个"概率/期望"的表达
2. 用随机抽样，重复做 N 次试验
3. 用样本的平均值/频率，去逼近真实答案

例子 1：估算积分。求 ∫₀¹ x² dx（答案是 1/3），没有解析技巧也能算：

import random

def monte_carlo_integral(f, a, b, n):
    total = 0
    for _ in range(n):
        x = random.uniform(a, b)   # 在 [a, b] 里随机取点
        total += f(x)
    return (b - a) * total / n     # 区间宽度 × 平均函数值

print(monte_carlo_integral(lambda x: x * x, 0, 1, 100_000))  # 约 0.333

例子 2：估算概率。掷两枚骰子，和等于 7 的概率是多少？理论值是 6/36 ≈ 0.1667，用随机模拟同样能逼近：

import random

def estimate_probability(n):
    hit = 0
    for _ in range(n):
        a = random.randint(1, 6)
        b = random.randint(1, 6)
        if a + b == 7:
            hit += 1
    return hit / n

print(estimate_probability(100_000))   # 约 0.1667

看到共同点了：不推公式，不找规律，直接"模拟"这件事本身，让统计帮你出答案。

三、蒙特卡洛为什么靠谱：大数定律

你可能会问：结果每次都带点随机误差，这能算"算法"吗？

能的。它的理论基石是大数定律：试验次数 N 越大，样本平均值就越接近真实期望。更实用的一条结论是——蒙特卡洛的误差大致按 1/√N 缩小。

也就是说，想让精度提高 10 倍（误差缩小到 1/10），试验次数要增加 100 倍。下面这段代码能直观看到"N 越大越准"：

import random

def estimate_pi(n):
    inside = 0
    for _ in range(n):
        if random.random()**2 + random.random()**2 <= 1.0:
            inside += 1
    return 4 * inside / n

for n in [100, 1_000, 10_000, 100_000, 1_000_000]:
    print(f"n={n:>9,}  π ≈ {estimate_pi(n):.5f}")

跑出来大概是：n 从 100 到 100 万，结果从 3.2 一路收敛到 3.141 附近。误差确实在缩小，但越来越慢——这正是 1/√N 的含义。

这也是蒙特卡洛的代价：它靠"堆次数"换精度，收敛不算快。

四、什么时候该用蒙特卡洛

既然收敛慢，为什么还用？因为它有一个无可替代的优点：几乎不依赖问题的维度。

经验法则：能精确解就精确解；确定性方法算不动（尤其高维、无解析式、随机性强）时，才轮到蒙特卡洛。它在金融定价、物理模拟、强化学习里都是主力。

五、元启发算法总纲：从"随机猜"到"聪明地搜"

蒙特卡洛是在随机采样一个分布。但还有另一类更难的问题：在一个巨大的解空间里，找一个"最好的解"。

比如旅行商问题：一个快递员要拜访 20 个城市，找最短路线。穷举所有顺序是 20! ≈ 2.4×10¹⁸ 种，算到天荒地老。这时候怎么办？

元启发算法（metaheuristic） 的思路是：不保证找到全局最优，但用"随机扰动 + 智能接受"的策略，在可接受时间内找到足够好的解。

先理清几个容易混的词：

"元（meta）"的意思就是比具体方法高一层：它不关心你的问题是排路线、排课表还是调参数，它只管一套通用的搜索框架。

元启发的通用骨架

几乎所有元启发算法，都套在这个框子里：

def metaheuristic():
    s = 初始化一个解()          # 起点：随机，或贪心给个还不错的
    best = s                    # 记住迄今最好的解
    while 没到终止条件():
        s_new = 扰动(s)         # 在 s 附近生成一个新候选解（邻域搜索）
        if 接受(s_new, s):      # ★ 接受准则：这是元启发的灵魂
            s = s_new
        if 评估(s_new) 优于 评估(best):
            best = s_new        # 更新全局最优
    return best

三个关键点：

1. 扰动：在当前解附近"动一下"生成候选解。比如交换路线里的两个城市。
2. 接受准则：这是元启发的精髓。贪心只接受"更好的"，所以会卡在局部最优；元启发允许偶尔接受"更差的"，从而跳出局部最优。
3. 全局最优记忆：best 单独记着，防止在"走坏路"时把最好的解丢了。

两大流派（第 20、21 课的主角）

按"同时维护几个解"，元启发分两派：

它们共享上面那套骨架，差别只在"扰动怎么做"和"接受准则怎么写"。这两课会分别展开。

六、一张图看懂：精确、启发、元启发、蒙特卡洛

确定性（确定能出答案）
 ├─ 精确算法：保证最优（穷举 / DP / Dijkstra）
 │        ↓ 问题太大算不动时
 └─ 启发式：针对具体问题的经验规则（快，但不保证最优、不通用）

随机性（靠概率/统计）
 ├─ 蒙特卡洛：随机采样逼近"一个数值答案"（π、积分、概率）
 └─ 元启发：随机扰动逼近"一个最优解"（模拟退火、遗传算法）

这样定位：蒙特卡洛答的是"这个值是多少"，元启发答的是"这个解怎么选"。 但两者血脉相连——都用随机性，去对付"确定性方法搞不定"的问题。

七、小结

1. 蒙特卡洛 = 用随机试验的频率/平均值，去逼近概率/期望，靠大数定律保证收敛，误差按 1/√N 缩小。
2. 蒙特卡洛几乎不怕维度，是高维、无解析解问题的"最后兜底"，但能用精确算法就别用随机。
3. 元启发算法 = 通用搜索框架（初始化 → 扰动 → 接受 → 记忆最优），核心是"允许偶尔接受更差解"来跳出局部最优；第 20、21 课的模拟退火和遗传算法就是它的两个代表。

八、动手实验

1. 改一改精度：把第一节的 estimate_pi 分别用 n=1 万、10 万、100 万跑三遍，记录结果，体会"1/√N"的收敛速度。
2. 估算一个积分：用 monte_carlo_integral 算 ∫₀² x³ dx（真值是 4），看看 10 万次采样能多接近。
3. 概率模拟：两枚骰子之和为 2 的概率理论值是多少？写个蒙特卡洛模拟验证，再对比和等于 7 的概率，理解"频率趋近概率"。