第8章：启发式的契约：接受"差不多对"需要多少勇气

A* 的启发函数如果撒了谎,它依然会给你一条路。只是那条路是错的。

一、1968年的赌注

1968年，斯坦福研究院的Peter Hart、Nils Nilsson和Bertram Raphael在一篇论文里提出了一个算法，后来这个算法被证明是人工智能历史上最优雅的思想之一。

他们要解决的问题很简单：让机器人Shakey在房间里找到从A点到B点的最短路径。

暴力搜索可以保证找到最优解——尝试所有可能的路径，选最短的那条。但Shakey的世界有数百万种可能的路径组合，暴力搜索需要的时间是天文数字。

贪心搜索很快——每次都朝着目标方向走。但它会撞上障碍物，走进死胡同，找到的路径可能比最优解长得多。

Hart三人提出的A*算法，做了一个看似不可能的承诺：我可以比暴力搜索快几个数量级，同时保证找到最优解。

这个承诺的代价是什么？一个契约。

如果你给A*一个”诚实”的启发函数——永远不高估剩余代价——它会信守承诺。但如果启发函数”撒谎”，高估了剩余代价，A*依然会给你一条路。只是那条路可能是错的。

这不是算法的bug，这是它的设计。A*用一个数学契约，换取了速度与最优性的平衡。

五十多年后，这个契约的思想依然是启发式算法的核心：当完美不可及时，我们需要明确代价的近似。

二、组合爆炸的诅咒

让我先量化”完美不可及”这件事。

2016年，AlphaGo击败李世石。全世界都在惊叹AI的”直觉”和”创造力”。但很少有人注意到一个技术细节：AlphaGo每一步棋的背后，是蒙特卡洛树搜索在19×19的棋盘上探索了数百万种可能。

不是数百种，不是数千种，是数百万种。

为什么需要这么多？因为围棋的状态空间大约是 $10^{170}$ ——比宇宙中的原子数( $10^{80}$ )还要多90个数量级。

即使每秒搜索 $10^{9}$ 个状态（现代计算机的极限），穷尽所有可能需要的时间是宇宙年龄的 $10^{150}$ 倍。

这不是工程问题，这是物理不可能。

类似的组合爆炸无处不在：

旅行商问题：访问n个城市的所有可能路线有 $n!$ 种。20个城市就是 $2.4 \times 10^{18}$ 种路线。
蛋白质折叠：一个100个氨基酸的蛋白质，每个氨基酸有3种主要构象，总共 $3^{100} \approx 10^{47}$ 种可能的折叠方式。
定理证明：在一阶逻辑里，长度为n的证明，可能的推理步骤数随n指数增长。

这就是启发式存在的理由：当最优解不可及时，我们需要”足够好”的解。

但”足够好”有多好？这不是一个模糊的工程问题，而是一个精确的数学问题。启发式算法必须遵守某些契约——如果违反了这些契约，它给出的”近似解”可能完全错误。

让我回到1968年，看看Hart、Nilsson和Raphael是如何设计这个契约的。

三、A*的数学契约

假设你在一个迷宫里,要从起点S走到终点G。每一步都有代价(比如时间或距离)。你想找到代价最小的路径。

暴力搜索（Dijkstra算法）会尝试所有可能的路径,保证找到最优解,但时间复杂度是 $O (b^{d})$ ——其中b是分支因子,d是解的深度。在复杂迷宫里,这是指数级的。

贪心搜索每次都选择”看起来离终点最近”的方向,速度很快,但可能走进死胡同。更糟糕的是,它可能找到的路径比最优解长几倍。

A*算法在1968年提出时,做了一个看似不可能的承诺:我可以比Dijkstra快,同时保证找到最优解。

它的核心是一个评估函数:

f (n) = g (n) + h (n)

$g (n)$ ：从起点到节点n的实际代价（已知的，确定的）
$h (n)$ ：从n到终点的估计代价（未知的，猜测的）
$f (n)$ ：通过n到达终点的总估计代价

A*每次扩展 $f (n)$ 最小的节点——也就是”实际代价+估计剩余代价”最小的节点。

这个设计的直觉很简单:如果你已经走了10步到达节点n,而你估计还需要5步到达终点,那么通过n的总代价大约是15步。A*优先探索总代价最小的路径。

但这里有一个致命的问题: $h (n)$ 怎么估计?

如果 $h (n)$ 估计得太高,A*会过早放弃最优路径——它会认为”这条路太贵了”,转而探索次优路径。

如果 $h (n)$ 估计得太低（比如 $h (n) = 0$ ），A*退化为Dijkstra算法,会探索所有方向,失去了速度优势。

Hart、Nilsson和Raphael证明了一个深刻的定理:如果启发函数满足可采纳性(admissibility),A*保证找到最优解。

可采纳性的定义:

h (n) \leq h^{*} (n)

其中 $h^{*} (n)$ 是从n到终点的真实最短代价。

换句话说,启发函数必须是乐观的——永远不能高估剩余代价。你可以低估（这会让搜索变慢），但不能高估（这会让搜索找到错误答案）。

这就是A*的契约:给我一个可采纳的启发函数,我保证找到最优解。违反契约,保证失效。

为什么这个契约有效?让我用一个具体例子说明。

四、自己动手:看契约如何被打破

可采纳性不是一个抽象的数学要求。它是A*能否找到最优解的充要条件。

让我们亲手验证这件事。

实验目标:用同一个迷宫,分别用可采纳和不可采纳的启发函数运行A*,看看结果有什么不同。

迷宫地图（0=可通行，1=障碍物，S=起点，G=终点）：

S . . . . .
. # # # # .
. . . . # .
. # # . # .
. . . . . G

S是起点(0,0),G是终点(4,5)
.是可通行格子,每步代价=1
#是障碍物,不可通行

任务:找从S到G的最短路径。

python

import heapq

# ------------------------------------------------------------------
# 定义迷宫：5行6列，1=障碍物，0=可通行
# S=(0,0)，G=(4,5)
# ------------------------------------------------------------------
GRID = [
    [0, 0, 0, 0, 0, 0],  # 行0：S . . . . .
    [0, 1, 1, 1, 1, 0],  # 行1：. # # # # .
    [0, 0, 0, 0, 1, 0],  # 行2：. . . . # .
    [0, 1, 1, 0, 1, 0],  # 行3：. # # . # .
    [0, 0, 0, 0, 0, 0],  # 行4：. . . . . G
]
ROWS, COLS = len(GRID), len(GRID[0])
START = (0, 0)
GOAL  = (4, 5)

def neighbors(r, c):
    """返回上下左右四个可通行邻居"""
    for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
        nr, nc = r+dr, c+dc
        if 0 <= nr < ROWS and 0 <= nc < COLS and GRID[nr][nc] == 0:
            yield nr, nc

def reconstruct_path(parent, node):
    """从 parent 字典回溯，重建路径"""
    path = []
    while node is not None:
        path.append(node)
        node = parent[node]
    return list(reversed(path))

def astar(h_func, label="A*"):
    """
    通用 A* 搜索。
    h_func(r, c) 是启发函数；返回 (路径长度, 路径, 扩展节点数)。
    """
    # 优先队列元素：(f, g, 节点)
    open_heap = [(h_func(*START), 0, START)]
    g_cost = {START: 0}    # 从起点到各节点的实际代价
    parent = {START: None} # 路径回溯
    closed = set()
    expanded = 0           # 记录扩展的节点数

    while open_heap:
        f, g, node = heapq.heappop(open_heap)

        if node in closed:
            continue
        closed.add(node)
        expanded += 1

        # 到达终点
        if node == GOAL:
            path = reconstruct_path(parent, node)
            return len(path) - 1, path, expanded  # 步数=节点数-1

        # 扩展邻居
        for nb in neighbors(*node):
            new_g = g + 1  # 每步代价为1
            if nb not in g_cost or new_g < g_cost[nb]:
                g_cost[nb] = new_g
                parent[nb] = node
                f_val = new_g + h_func(*nb)
                heapq.heappush(open_heap, (f_val, new_g, nb))

    return None, [], expanded  # 无解

# ------------------------------------------------------------------
# 步骤1：可采纳启发函数——曼哈顿距离
#   h₁(n) = |n_row - G_row| + |n_col - G_col|
#   永远不高估剩余代价 → 满足可采纳性 → 保证最优解
# ------------------------------------------------------------------
def h_admissible(r, c):
    """曼哈顿距离：可采纳，不高估"""
    return abs(r - GOAL[0]) + abs(c - GOAL[1])

steps1, path1, exp1 = astar(h_admissible, "可采纳A*")
print("=== 步骤1：可采纳启发函数（曼哈顿距离）===")
print(f"路径长度：{steps1} 步")
print(f"扩展节点数：{exp1}")
print(f"路径：{path1}")

# ------------------------------------------------------------------
# 步骤2：不可采纳启发函数——曼哈顿距离 × 2
#   h₂(n) = 2 × (|n_row - G_row| + |n_col - G_col|)
#   高估了剩余代价 → 违反可采纳性 → 可能找到次优路径
# ------------------------------------------------------------------
def h_inadmissible(r, c):
    """2倍曼哈顿距离：不可采纳，会高估"""
    return 2 * (abs(r - GOAL[0]) + abs(c - GOAL[1]))

steps2, path2, exp2 = astar(h_inadmissible, "不可采纳A*")
print("\n=== 步骤2：不可采纳启发函数（2倍曼哈顿距离）===")
print(f"路径长度：{steps2} 步")
print(f"扩展节点数：{exp2}")
print(f"路径：{path2}")

# ------------------------------------------------------------------
# 对比结论
# ------------------------------------------------------------------
print("\n=== 对比结论 ===")
print(f"可采纳启发函数   → {steps1} 步（最优解保证）")
print(f"不可采纳启发函数 → {steps2} 步（{'最优' if steps1==steps2 else '次优，非最优'}）")
if steps1 != steps2:
    print(f"  差距：{steps2 - steps1} 步（契约被打破，找到了更长的路径）")
print(f"\n注意：可采纳版扩展 {exp1} 个节点，不可采纳版扩展 {exp2} 个节点。")
print("  不可采纳启发函数扩展更少节点，速度更快，但牺牲了最优性保证。")

步骤1:用可采纳启发函数

最简单的可采纳启发函数是曼哈顿距离(Manhattan Distance):

h_{1} (n) = | n_{x} - G_{x} | + | n_{y} - G_{y} |

这是”如果没有障碍物,直线走到终点”的代价。因为实际路径必须绕过障碍物,所以 $h_{1} (n) \leq h^{*} (n)$ ,满足可采纳性。

从S开始,计算相邻节点的 $f (n) = g (n) + h_{1} (n)$ :

节点	g(n)	h₁(n)	f(n)
S右	1	9	10
S下	1	8	9

选择 $f (n)$ 最小的”S下”扩展。继续这个过程,你会发现A*最终找到最短路径,长度=11步。

步骤2:用不可采纳启发函数

现在故意违反契约。定义一个高估的启发函数:

h_{2} (n) = 2 \times (| n_{x} - G_{x} | + | n_{y} - G_{y} |)

这个函数把剩余代价估计为曼哈顿距离的2倍——明显高估了。

重新从S开始:

节点	g(n)	h₂(n)	f(n)
S右	1	18	19
S下	1	16	17

看起来”S下”仍然更优。但继续搜索,你会发现:当A*接近真正的最优路径时,因为 $h_{2} (n)$ 高估了剩余代价,它会认为”这条路太贵了”,转而探索次优路径。

结果:A*可能找到一条长度=13的路径,而不是最优的11步。

这就是可采纳性的意义:如果 $h (n)$ 可采纳,A*找到的第一条路径必然是最短路径。这是数学保证,不是经验规律。

但可采纳性也有代价。

五、信息论视角:启发函数的熵代价

可采纳性保证了正确性,但代价是什么?

考虑两个极端:

极度保守: $h (n) = 0$ ,永远估计剩余代价为0。

这显然可采纳(因为真实代价 $h^{*} (n) \geq 0$ ),但完全没用——A*退化为Dijkstra算法,会均匀地探索所有方向,直到碰到终点。从信息论角度看,这相当于对搜索空间的最大熵探索:每个方向的先验概率相同。

极度激进: $h (n) = h^{*} (n)$ ,完美预测剩余代价。

这是理想情况——A*会直接走最优路径,不探索任何无用节点。这相当于零熵搜索:你已经知道答案,不需要探索。但问题是:如果你已经知道 $h^{*} (n)$ ,你就已经解决了问题,不需要搜索了。

现实中的启发函数在两者之间:尽可能接近 $h^{*} (n)$ ,同时保持可采纳。

这个权衡可以用有效分支因子(effective branching factor) $b^{*}$ 量化:

N = 1 + b^{*} + (b^{*})^{2} + \dots + (b^{*})^{d}

其中 $N$ 是A*扩展的节点总数, $d$ 是解的深度。 $b^{*}$ 越小,搜索效率越高。

Pearl在1984年的经典教材里给出了实验数据：

当 $h (n) = 0$ 时， $b^{*} \approx 2.8$ （在8-puzzle上）
当 $h (n) = 曼哈顿距离$ 时， $b^{*} \approx 1.4$
当使用更精确的启发函数（如模式数据库）时， $b^{*} \approx 1.1$

从2.8降到1.1,意味着搜索树的节点数从 ${2.8}^{20} \approx 10^{9}$ 降到 ${1.1}^{20} \approx 8$ ——六个数量级的差距。

启发函数的质量,直接决定了搜索需要消耗的计算资源。

但这里有一个深层的张力:好的启发函数需要领域知识。曼哈顿距离对网格有效,但对图搜索呢?对连续空间呢?对围棋呢?

在复杂环境中,设计一个既可采纳又接近 $h^{*} (n)$ 的启发函数,本身就是一个困难的问题。

这就是[Zixi Li, 2026a]的ADS工作要解决的问题:能否让机器自动学习启发函数?

六、ADS:启发式的信息论化

传统启发式设计有一个根本局限： $h (n)$ 是手工设计的，需要领域知识，而且是静态的——一旦设计好，在整个搜索过程中保持不变。

但搜索空间是动态的。在开阔区域，启发函数值得信任；在障碍物密集区域，任何启发函数都可能误导。固定权重 $α = 1$ 是对这种动态性的粗暴简化。

[Zixi Li, 2026a] 的 ADS（自适应双搜索）提出了一个问题：能否用信息论量化启发函数的可信程度，让权重随当前状态的不确定性自动调整？

核心思想是将启发函数的权重 $α$ 与当前状态的熵挂钩：

当模型对当前状态高度确定（低熵）时， $α$ 大——信任启发函数，快速前进
当模型对当前状态充满不确定（高熵）时， $α \to \infty$ ——形成势垒，拒绝进入高不确定性区域

这不是参数调优，而是将不确定性量化为可操作的搜索约束。A* 的可采纳性保证了"不高估"，ADS 的熵障碍保证了"不探索高熵死路"。

与可采纳性的关系：可采纳性是对 $h (n)$ 值域的约束（不高估），ADS 的熵正则化是对搜索方向的约束（排斥高不确定性）。两者互补：前者是静态的、数学的；后者是动态的、信息论的。

ADS 的更完整技术细节，以及它如何被应用于 LLM 推理空间，在第10章展开。

## 七、近似算法的契约:放弃最优,但不放弃保证

A*的可采纳性保证了最优解,但代价是必须探索所有”可能最优”的路径。在某些问题上,这依然太慢。

1973年,计算复杂性理论迎来了一个转折点。Stephen Cook证明了SAT问题是NP完全的——如果你能在多项式时间内解决它,你就能解决所有NP问题。

这个证明引发了一个深刻的哲学转变:也许我们应该放弃寻找最优解,转而寻找”足够好”的解。

但”足够好”需要一个精确的定义。否则,任何算法都可以声称自己”足够好”。

1974年,David Johnson引入了近似比(approximation ratio)的概念。对于最小化问题,一个α-近似算法保证:

算法解 \leq α \times 最优解

这是一个最坏情况保证——无论输入如何,近似比都不会超过α。

让我用一个经典例子说明。

7.1 顶点覆盖:一个2-近似算法

顶点覆盖问题(Vertex Cover):给定一个图,找到最小的顶点集合,使得图中每条边至少有一个端点在集合中。

这个问题是NP完全的。暴力搜索需要检查 $2^{n}$ 种可能(n是顶点数)。

但有一个极其简单的2-近似算法:

python

import random

def greedy_vertex_cover(edges):
    """
    贪心顶点覆盖：2-近似算法，时间复杂度 O(|E|)。
    edges: [(u, v), ...] 边列表
    返回: 顶点覆盖集合 C，保证 |C| ≤ 2|C*|
    """
    remaining = list(edges)
    C = set()
    while remaining:
        u, v = random.choice(remaining)   # 随机选一条边
        C.add(u)
        C.add(v)
        # 删除所有与 u 或 v 相连的边
        remaining = [(a, b) for a, b in remaining if a not in (u, v) and b not in (u, v)]
    return C

这个算法的运行时间是 $O (| E |)$ (E是边数),而且保证:

| C | \leq 2 \times | C^{*} |

其中 $C^{*}$ 是最优顶点覆盖。

证明(这是近似算法分析的经典技巧):

每次选择的边 $(u, v)$ ,最优解 $C^{*}$ 必须至少包含u或v之一——否则这条边就没有被覆盖。

我们的算法两个都选了。所以我们选择的顶点数,最多是最优解的2倍。

这个保证是紧的——存在输入使得算法恰好达到2倍。但它是最坏情况的保证:无论输入如何,近似比都不会超过2。

7.2 PTAS:任意接近最优

近似算法的圣杯是PTAS(Polynomial-Time Approximation Scheme)。

PTAS是一族算法,对于任意 $ϵ > 0$ ,它能在多项式时间内找到 $(1 + ϵ)$ -近似解。

换句话说,你可以任意接近最优解——想要99%最优?可以。想要99.9%最优?也可以。代价只是多项式时间的增长。

[Li & Jin, 2015]为加权单位圆盘覆盖问题提供了首个PTAS。这个问题在无线网络设计中有重要应用:给定平面上的点,用最少的单位圆盘覆盖所有点。

他们的算法时间复杂度是 $O (n^{2 / ϵ})$ 。从 $ϵ = 0.1$ 到 $ϵ = 0.01$ ,时间从 $O (n^{20})$ 增长到 $O (n^{200})$ ——依然是多项式,但实际上不可计算。

这揭示了PTAS的局限:理论上可行,实践上可能不可行。

近似算法的契约:我不保证给你最优解,但保证给你的解不会太差,而且我能精确告诉你”不会太差”的程度。这是一个诚实的契约——比”我尽力了”要强得多。

八、伪代码:A*与自适应启发权重

让我把前面讨论的核心算法形式化。

算法1:标准A*搜索

python

import heapq

def astar(graph, start, goal, h):
    # graph: dict {node: [(neighbor, cost), ...]}
    # h: 启发函数 h(node) -> 估计到终点的代价
    # 返回: 最短路径列表，或 None（无解）
    open_heap = [(h(start), 0, start, [start])]  # (f, g, node, path)
    closed = set()

    while open_heap:
        f, g, node, path = heapq.heappop(open_heap)
        if node == goal:
            return path
        if node in closed:
            continue
        closed.add(node)
        for neighbor, cost in graph.get(node, []):
            if neighbor in closed:
                continue
            g_new = g + cost
            heapq.heappush(open_heap, (g_new + h(neighbor), g_new, neighbor, path + [neighbor]))

    return None  # 无解

时间复杂度： $O (b^{d})$ ，其中 $b$ 是分支因子， $d$ 是解的深度。启发函数越好，实际扩展的节点越少。

算法2:ADS自适应启发权重

python

import math

def ads_search(start, goal, cost_fn, h_fn, policy_fn, k=3.0):
    # policy_fn(s) -> 动作概率分布 dict {action: prob}
    # h_fn(s)      -> 启发式估计值（到终点的代价）
    # cost_fn(s,a) -> 执行动作 a 的代价
    def entropy(probs):
        return -sum(p * math.log(p + 1e-10) for p in probs if p > 0)

    s, path, g = start, [start], 0.0

    while s != goal:
        action_probs = policy_fn(s)
        actions = list(action_probs.keys())
        probs   = list(action_probs.values())

        U_s   = entropy(probs)
        H_max = math.log(len(actions) + 1e-10)

        # 信息论势垒：熵越接近最大值，不确定性越高，降低对启发式的信任
        B_s   = U_s / (H_max + 1e-10)
        alpha = 1.0 / (1.0 + math.exp(-k * B_s))   # sigmoid

        best_action, best_f = None, float("inf")
        for action in actions:
            f_val = g + cost_fn(s, action) + alpha * h_fn(action)
            if f_val < best_f:
                best_f, best_action = f_val, action

        g += cost_fn(s, best_action)
        s = best_action
        path.append(s)

    return path

关键创新：α 不是固定的，而是根据当前状态的信息论特性动态调整。熵高（不确定性大）时降低对启发式的依赖；熵低时信任启发式快速前进。

九、可视化：启发权重如何影响搜索路径

想象一个2D网格世界,有障碍物和目标。不同的启发权重α会导致完全不同的搜索行为。

图8.1:不同启发权重下的搜索路径对比 三种启发权重配置的搜索行为:(a) α=0(Dijkstra):均匀扩散,探索所有方向,保证最优但效率低。(b) α=1(标准A):沿启发方向前进,遇到障碍物时适度回溯。(c) α=2(贪心):过度信任启发式,可能陷入局部最优。绿色是起点,红色是终点,蓝色阴影是扩展的节点,黄色线是最终路径。*

关键观察: - α太小:搜索过于保守,扩展大量无用节点 - α太大:搜索过于激进,可能错过最优路径 - α=1且h可采纳:平衡点,保证最优且效率高

ADS的创新在于:α不是固定的,而是根据局部地形自适应调整。

这个自适应性来自信息论势垒B(s)的计算: - 在开阔区域:IG高(沿启发方向信息增益大),U低(后续状态确定) → B高 → α高 - 在障碍物附近:IG低(启发方向被阻挡),U高(多个绕行选择) → B低 → α低

十、启发式的哲学：接受不完美的勇气

让我回到本章开头的问题:当完美不可及时,我们应该做什么?

启发式算法的答案是:明确代价地接受近似。

这需要勇气,因为你必须承认完美不可及。但这不是失败,而是智慧。

可采纳性是A*的契约:我可以乐观,但不能撒谎。如果 $h (n)$ 高估了代价,A*可能找到次优解——契约被打破,保证失效。这是一个诚实的契约:我告诉你我的假设,如果假设成立,我保证结果。

近似比是近似算法的契约:我不承诺最优,但承诺不会太差。2-近似算法保证解不超过最优解的2倍,这是最坏情况的数学保证——不是平均情况,不是”通常很好”,而是”永远不会超过2倍”。

概率保证是随机化算法的契约:我不保证每次都对,但保证以 $1 - δ$ 的概率正确。这是一个可量化的风险:你可以选择 $δ = 10^{- 6}$ ,让失败概率低于百万分之一。

这三种契约,对应三种不同的”不完美”:

条件保证:如果假设成立,我保证最优(A*)
最坏情况保证:我保证不会太差,但可能不是最优(近似算法)
概率保证:我大概率正确,但有小概率失败(随机化算法)

相比之下,没有契约的启发式——”我尽力了”、”通常很好”、”在我测试的数据上有效”——是不诚实的近似。它们没有告诉你失败的条件,没有量化”不够好”的程度,没有给出风险的概率。

但启发式也有代价:

设计成本:好的启发函数需要领域知识。曼哈顿距离对网格有效,但对图搜索呢?对连续空间呢?每个新问题都需要重新设计启发函数。

计算成本:复杂的启发函数可能比搜索本身还慢。如果 $h (n)$ 需要 $O (n^{2})$ 计算,还不如直接搜索。

泛化风险:针对特定问题设计的启发式,换个场景可能失效。这就是为什么ADS用神经网络学习启发策略——它可以跨任务泛化。但代价是失去了数学保证。

这引出了一个深层的张力:可证明的保证 vs 经验的泛化。

A*有可采纳性保证,但需要手工设计 $h (n)$ 。神经网络可以自动学习,但没有保证。我们能否两者兼得?

这是第十二章的问题。现在,先记住这个张力。

十一、姚期智原理：算法设计即博弈

在讨论Collins如何突破确定性下界之前，我们需要先理解一个更深层的问题：启发式设计，究竟是在和谁博弈？

1977年，姚期智（Andrew Chi-Chih Yao）在一篇短短几页的论文里，给出了一个改变算法复杂度理论格局的答案。

8.1 把算法设计变成博弈

想象这样一个游戏。

有两个玩家：

玩家A（算法设计者）：选择一个算法 $A$ 来解决某个问题
玩家B（对手/输入分布）：选择一个输入分布 $D$ ，试图让算法跑得最慢

玩家A先行还是后行？如果A先选算法，B就针对这个算法构造最坏情况输入。如果B先选分布，A就针对这个分布优化算法。

这是一个零和博弈。

8.2 MiniMax定理的两侧

姚期智原理（Yao's Minimax Principle）说的是：在确定性算法和随机性输入之间，存在一个MiniMax等式。

min_{确定性算法 A} max_{输入分布 D} E_{x \sim D} [T (A, x)] = max_{输入分布 D} min_{确定性算法 A} E_{x \sim D} [T (A, x)]

这个等式的左边是："最优的确定性算法，在最坏情况输入分布下的期望时间"。

这个等式的右边是："在某个固定输入分布下，最优确定性算法的期望时间"。

两边相等。这意味着：你可以通过分析固定分布下的确定性算法下界，来得到所有随机化算法的下界。

8.3 费曼式讲解：为什么这是深刻的？

让我用一个比喻说清楚。

假设你是一个将军（算法设计者），要制定一个通用战术（算法），面对不同的敌人（输入）。你不知道敌人会怎么部署。

悲观情形（MaxMin）：你先选战术，然后敌人选对你最不利的部署。

你的最优战术 = "在最坏敌人部署下，我能做到最好的结果"

乐观情形（MinMax）：敌人先选分布，然后你选最好的战术。

你的最优战术 = "在已知敌人的平均部署统计下，我能做到的最好结果"

MiniMax定理说：这两个值相等。

这意味着什么？

确定性算法的最坏情况下界 = 随机化算法的平均情况下界。

更直白地说：如果你想证明"任何确定性算法都至少需要 $T$ 步"，你只需要证明"存在某个输入分布，使得任何确定性算法的期望时间至少是 $T$ "。

这是一个极其有力的工具——你把"最坏情况"分析转化为了"平均情况"分析，而后者通常更容易处理。

8.4 启发式设计的博弈论视角

现在把这个框架应用到启发式设计上。

启发式函数 $h (n)$ 的设计，本质上是一个博弈：

玩家	选择	目标
启发式设计者	启发函数 $h (n)$	最小化搜索时间
问题实例生成器	输入图/迷宫的分布	最大化搜索时间

姚期智原理告诉我们：无论多么聪明的确定性启发式，都有一个由输入分布决定的性能下界。

这个下界不是工程限制，而是信息论限制：如果你的启发式函数是确定性的，对手（输入分布）总能找到一类问题，让你的性能退化到最坏情况。

8.5 从相对下界到绝对下界

这里出现了一个关键区分：

相对下界（Relative Lower Bound）：

"对于确定性启发式 $h$ ，存在输入使得搜索时间是 $Ω (T)$ "
这是相对于特定算法的下界——换一个算法，下界可能不同

绝对下界（Absolute Lower Bound）：

"对于任何确定性算法，搜索时间都是 $Ω (T)$ "
这是关于问题本身的下界——没有任何确定性算法能突破它

姚期智原理建立了两者之间的桥梁：通过博弈论的MiniMax等式，你可以把特定算法的最坏情况下界，提升为对所有确定性算法都成立的绝对下界。

但这里有一个陷阱：这个绝对下界，只对确定性算法成立。

随机化算法不受同样的约束。

为什么？因为随机化算法打破了博弈的对称性：对手无法针对一个随机算法构造最坏情况输入——因为随机算法每次运行都不同，对手不知道该如何"针对"它。

这就引出了Collins的核心思想。

十二、Collins：用随机化突破确定性下界

启发式通常是确定性的:给定状态s,h(s)总是返回同一个值。但[Zixi Li, 2026b]的Collins工作表明,随机化可以突破确定性的信息论下界。

Collins针对的是优化器状态压缩问题,但其核心思想揭示了启发式设计的一个深层原理。

8.1 确定性的信息论下界

Proposition 1(确定性下界):任何确定性数据结构,维护d个参数的精度ε状态,必须使用 $Ω (d \log (1 / ϵ))$ 比特。

这不是工程限制,这是信息论的计数论证:

要区分 $Q^{d}$ 个不同状态(其中 $Q = 1 / ϵ$ 是量化级别),你需要至少 $\log_{2} (Q^{d}) = d \log Q$ 比特信息。

这意味着:如果你想用确定性方法存储Adam优化器的一阶和二阶矩(对于d个参数),你至少需要 $O (d)$ 的内存。

对于大型语言模型(d可能是数十亿),这是一个巨大的瓶颈。

8.2 随机化的突破:用概率换空间

Collins用Count-Sketch + 2-Universal Hashing,将状态复杂度从 $O (d)$ 降至 $O (k)$ ,其中 $k ≪ d$ 。压缩比 $c = d / k$ 可以达到数十。

关键思想:不存储精确状态,而是存储状态的随机投影。

这类似于物理学中的粗粒化(coarse-graining):你不追踪每个粒子的精确位置,而是追踪宏观统计量。代价是引入噪声,但如果噪声足够小,宏观行为依然正确。

Chernoff不等式给出了安全上界:

c_{opt} \leq T_{eff} \cdot {SNR}_{b}

其中 $T_{eff}$ 是有效训练步数, ${SNR}_{b}$ 是批次信噪比。

实验验证了理论预测: $c \leq 32$ 时收敛损失与基线无差异, $c > 40$ 时急剧退化——相变点 $c \approx 34$ 与理论预测高度吻合。

8.3 对启发式的启示:确定性vs概率保证

Collins的工作揭示了启发式设计的一个深层权衡:

确定性启发式:保证对于给定输入,总是返回相同的估计。但受信息论下界约束——好的启发函数需要存储大量领域知识。

随机化启发式:用概率保证换取更低的计算/存储成本。不保证每次都正确,但保证”高概率正确”。

这是另一种契约——从”保证正确”到”以 $1 - δ$ 的概率正确”。

从物理学角度看,这是热力学第二定律的体现:你可以用熵(随机性)换取能量(计算资源)。确定性系统需要维持低熵状态,代价是高能量消耗。随机化系统允许更高的熵,因此能量消耗更低。

Landauer原理给出了理论下界:擦除1比特信息至少需要 $k_{B} T \ln 2$ 的能量。随机化启发式不擦除信息——它允许信息以噪声的形式存在,因此能量成本更低。

启发式是在已知结构上做近似。下一章，我们将看到 Transformer 如何通过动态连接所有节点，彻底重构了"结构"的概念。

悬而未决

启发函数的”好坏”能否被形式化定义?
什么样的 $h (n)$ 在理论上最优?Pearl证明了一致性(consistency)强于可采纳性,但这是最强的有用条件吗?是否存在”最接近 $h^{*} (n)$ 的可采纳函数”?这个问题等价于:给定有限的计算资源,如何最优地分配给启发函数的设计?
熵障碍的适用边界在哪里?
ADS的动态对数障碍在算术任务上有效,但在抽象代数上失败。这个失败是原则性的还是工程性的?换句话说:是熵正则化本身不适合高阶抽象,还是只是360M模型太小?如果给3B模型,抽象代数任务会成功吗?这个问题触及熵作为推理约束的根本限制。
神经网络学到的隐式启发式与人工设计的显式启发式有何本质区别?
AlphaGo的价值网络是一种启发函数,但它不满足可采纳性——为什么仍然有效?一个可能的答案是:神经网络学到的是平均情况的启发式,而可采纳性是最坏情况的保证。但这意味着什么?是否存在”平均情况可采纳性”的概念?
随机化启发式的理论边界在哪里?
Collins证明了确定性下界 $Ω (d \log (1 / ϵ))$ ,但随机化的上界是什么?Chernoff界给出了 $c_{opt} \leq T_{eff} \cdot {SNR}_{b}$ ,但这是紧的吗?是否存在”最优随机化启发式”——在给定失败概率 $δ$ 下,最小化计算成本?
启发式能否在线学习?
经典启发式是离线设计的——在搜索开始前就固定了。但能否设计一个启发函数,在搜索过程中学习并调整自己?每次扩展节点,都更新对 $h^{*} (n)$ 的估计,使得后续搜索更高效?这类似强化学习,但目标是加速当前搜索,而不是泛化到未来任务。
近似算法的下界在哪里?
我们知道顶点覆盖有2-近似算法,但能否做到1.5-近似?1.1-近似?对于某些NP完全问题,存在近似下界——除非P=NP,否则不存在 $(1 + ϵ)$ -近似算法。这些下界告诉我们:有些问题,近似也是困难的。

第8章：启发式的契约：接受"差不多对"需要多少勇气 ​

一、1968年的赌注 ​

二、组合爆炸的诅咒 ​

三、A*的数学契约 ​

四、自己动手:看契约如何被打破 ​

步骤1:用可采纳启发函数 ​

步骤2:用不可采纳启发函数 ​

五、信息论视角:启发函数的熵代价 ​

六、ADS:启发式的信息论化 ​

7.1 顶点覆盖:一个2-近似算法 ​

7.2 PTAS:任意接近最优 ​

八、伪代码:A*与自适应启发权重 ​

九、可视化：启发权重如何影响搜索路径 ​

十、启发式的哲学：接受不完美的勇气 ​

十一、姚期智原理：算法设计即博弈 ​

8.1 把算法设计变成博弈 ​

8.2 MiniMax定理的两侧 ​

8.3 费曼式讲解：为什么这是深刻的？ ​

8.4 启发式设计的博弈论视角 ​

8.5 从相对下界到绝对下界 ​

十二、Collins：用随机化突破确定性下界 ​

8.1 确定性的信息论下界 ​

8.2 随机化的突破:用概率换空间 ​

8.3 对启发式的启示:确定性vs概率保证 ​

悬而未决 ​

延伸阅读 ​

第8章：启发式的契约：接受"差不多对"需要多少勇气

一、1968年的赌注

二、组合爆炸的诅咒

三、A*的数学契约

四、自己动手:看契约如何被打破

步骤1:用可采纳启发函数

步骤2:用不可采纳启发函数

五、信息论视角:启发函数的熵代价

六、ADS:启发式的信息论化

7.1 顶点覆盖:一个2-近似算法

7.2 PTAS:任意接近最优

八、伪代码:A*与自适应启发权重

九、可视化：启发权重如何影响搜索路径

十、启发式的哲学：接受不完美的勇气

十一、姚期智原理：算法设计即博弈

8.1 把算法设计变成博弈

8.2 MiniMax定理的两侧

8.3 费曼式讲解：为什么这是深刻的？

8.4 启发式设计的博弈论视角

8.5 从相对下界到绝对下界

十二、Collins：用随机化突破确定性下界

8.1 确定性的信息论下界

8.2 随机化的突破:用概率换空间

8.3 对启发式的启示:确定性vs概率保证

悬而未决

延伸阅读