第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是解的深度。在复杂迷宫里,这是指数级的。

:::details Dijkstra 算法：最短路径的暴力保证
Dijkstra（迪杰斯特拉）算法是荷兰计算机科学家 Edsger Dijkstra 在 1956 年提出的最短路径算法，思路是：从起点出发，每次选择当前已知代价最小的未访问节点，扩展它的邻居，直到到达终点。

• 保证：如果所有边的代价非负，Dijkstra 一定找到最优（代价最小）的路径
• 代价：它探索所有可能的路径，不知道"大致往哪个方向走才对"，效率低

分支因子 b：在搜索树里，每个节点平均有多少个子节点（可选的下一步）。迷宫里可能是 4（上下左右），围棋里大约是 250。

搜索深度 d：到达答案需要的步数。

两者组合后，搜索空间是 b^d——这就是组合爆炸的数学来源。A* 用启发函数"剪枝"，减少需要探索的节点数，从而在保证最优性的同时大幅提速。
:::

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

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

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

• 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)是从n到终点的真实最短代价。

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

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

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

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

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

让我们亲手验证这件事。

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

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

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

• S是起点(0,0),G是终点(4,5)

• .是可通行格子,每步代价=1

• #是障碍物,不可通行

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

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) \leq h^*(n),满足可采纳性。

从S开始,计算相邻节点的f(n) = g(n) + h_1(n):

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

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

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

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

重新从S开始:

看起来”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是A*扩展的节点总数,d是解的深度。b^*越小,搜索效率越高。

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

• 当h(n) = 0时，b^* \approx 2.8（在8-puzzle上）

• 当h(n) = \text{曼哈顿距离}时，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) 是手工设计的，需要领域知识，而且是静态的——一旦设计好，在整个搜索过程中保持不变。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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^*是最优顶点覆盖。

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

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

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

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

7.2 PTAS:任意接近最优

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

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

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

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

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

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

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

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

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

算法1:标准A*搜索

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自适应启发权重

import math

def ads_search(start, goal, cost_fn, h_fn, policy_fn):
    # 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 -> 1 时 alpha -> 无穷，彻底排除高熵死路
        B_s   = U_s / (H_max + 1e-10)
        alpha = -math.log(1 - B_s + 1e-10)

        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网格世界,有障碍物和目标。不同的启发权重α会导致完全不同的搜索行为。

*三种启发权重配置的搜索行为:(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-\delta的概率正确。这是一个可量化的风险:你可以选择\delta = 10^{-6},让失败概率低于百万分之一。

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

1. 条件保证:如果假设成立,我保证最优(A*)

2. 最坏情况保证:我保证不会太差,但可能不是最优(近似算法)

3. 概率保证:我大概率正确,但有小概率失败(随机化算法)

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

但启发式也有代价:

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

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

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

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

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

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

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

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

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

8.1 把算法设计变成博弈

想象这样一个游戏。

有两个玩家：

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

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

这是一个零和博弈。

8.2 MiniMax定理的两侧

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

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

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

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

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

让我用一个比喻说清楚。

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

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

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

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

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

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

这意味着什么？

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

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

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

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

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

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

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

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

8.5 从相对下界到绝对下界

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

相对下界（Relative Lower Bound）：

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

绝对下界（Absolute Lower Bound）：

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

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

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

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

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

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

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

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

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

8.1 确定性的信息论下界

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

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

要区分Q^d个不同状态(其中Q = 1/\epsilon是量化级别),你需要至少\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 \ll d。压缩比c = d/k可以达到数十。

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

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

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

其中T_{\text{eff}}是有效训练步数,\text{SNR}_b是批次信噪比。

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

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

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

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

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

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

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

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

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

悬而未决

• 启发函数的”好坏”能否被形式化定义?

  什么样的h(n)在理论上最优?Pearl证明了一致性(consistency)强于可采纳性,但这是最强的有用条件吗?是否存在”最接近h^*(n)的可采纳函数”?这个问题等价于:给定有限的计算资源,如何最优地分配给启发函数的设计?

• 熵障碍的适用边界在哪里?

  ADS的动态对数障碍在算术任务上有效,但在抽象代数上失败。这个失败是原则性的还是工程性的?换句话说:是熵正则化本身不适合高阶抽象,还是只是360M模型太小?如果给3B模型,抽象代数任务会成功吗?这个问题触及熵作为推理约束的根本限制。

• 神经网络学到的隐式启发式与人工设计的显式启发式有何本质区别?

  AlphaGo的价值网络是一种启发函数,但它不满足可采纳性——为什么仍然有效?一个可能的答案是:神经网络学到的是平均情况的启发式,而可采纳性是最坏情况的保证。但这意味着什么?是否存在”平均情况可采纳性”的概念?

• 随机化启发式的理论边界在哪里?

  Collins证明了确定性下界\Omega(d \log(1/\epsilon)),但随机化的上界是什么?Chernoff界给出了c_{\text{opt}} \leq T_{\text{eff}} \cdot \text{SNR}_b,但这是紧的吗?是否存在”最优随机化启发式”——在给定失败概率\delta下,最小化计算成本?

• 启发式能否在线学习?

  经典启发式是离线设计的——在搜索开始前就固定了。但能否设计一个启发函数,在搜索过程中学习并调整自己?每次扩展节点,都更新对h^*(n)的估计,使得后续搜索更高效?这类似强化学习,但目标是加速当前搜索,而不是泛化到未来任务。

• 近似算法的下界在哪里?

  我们知道顶点覆盖有2-近似算法,但能否做到1.5-近似?1.1-近似?对于某些NP完全问题,存在近似下界——除非P=NP,否则不存在(1+\epsilon)-近似算法。这些下界告诉我们:有些问题,近似也是困难的。

番外：搜索即收敛——启发式的动力学视角

A* 的每一步，其实是一个欧拉步。

回到评估函数 f(n) = g(n) + h(n)。把搜索过程看作状态空间里的离散动力系统：

这和梯度下降的欧拉离散化结构完全一样：

g 是已走代价，是"过去"；h 是估计剩余，是"未来"；\alpha 是对未来的置信度。搜索就是在这两个力的拉锯下，一步步逼近目标。

:::details 欧拉步是什么？
微积分里，导数描述的是连续变化。但计算机只能做离散的事情——每次走一小步。

欧拉方法就是把"连续流动"切成一段段小步：

意思是：现在在 x_t，变化速度是 f(x_t)，走一小步 \Delta t，到达 x_{t+1}。

梯度下降是欧拉步的特例——变化方向是负梯度（最陡下坡方向），步长是学习率 \eta：

A* 的搜索也是同一个结构：当前状态 s_t，评估每个方向的代价，选最小的走一步。区别只是 A* 用的是离散的图，梯度下降用的是连续的曲面。本质上，两者都是在问同一个问题：下一步往哪走，才能最快到达目标？
:::

三角不等式是收敛的保证。

一致性条件 h(n) \leq c(n, n') + h(n') 正是三角形三边关系：g、c、h 构成一个三角形。这个不等式保证了 f 值单调不减——这正是李雅普诺夫函数的条件：V(s_{t+1}) \leq V(s_t)，系统稳定收敛到目标。

:::details 三角不等式是什么？
你小学就知道：三角形任意两边之和大于第三边。

a + b \geq c

在启发式搜索里，这条规则变成：从 n 到终点的估计代价，不能超过"先走一步到 n'，再从 n' 到终点"的总代价。

直觉：你对剩余路程的猜测，不能比"实际走一步之后再猜"还要悲观。否则你的地图是自相矛盾的——就像一张声称"北京到上海 2000 公里，但北京到南京只要 100 公里，南京到上海只要 100 公里"的地图，你会怀疑它在撒谎。

满足这条规则的启发函数叫一致的（consistent）。一致性保证 A* 不会走回头路，每个节点只需扩展一次。
:::

:::details 李雅普诺夫函数是什么？
想象一个球在碗里滚动。不管从哪里放手，球最终都会滚到碗底。

李雅普诺夫函数就是那个"碗的高度"——一个衡量系统离目标有多远的数值。只要每一步这个数值都在减小（或不增大），系统就一定会收敛到目标，不会乱跑。

在 A* 里，f 值就是这个碗的高度。一致性保证 f 单调不减，等价于说：我们永远在朝目标靠近，不会绕圈子。

李雅普诺夫 1892 年用这个思想证明了一大类动力系统的稳定性。A* 的最优性证明，本质上是同一件事。
:::

ADS 在做什么？

ADS 的对数势垒 \alpha = -\log(1 - B_s) 是在动态变形这个三角形。熵低时 \alpha \approx 0，三角形塌缩，g 主导；熵高时 \alpha \to \infty，h 那条边爆炸，高不确定性方向被彻底排除。

势垒不是在"调参"，而是在根据局部不确定性重塑搜索空间的几何。

这个"搜索即收敛"的直觉，在启发式语境下是一个几何故事。

但如果把搜索空间换成 LLM 的信念空间，把 h 换成交叉熵能量函数，把欧拉步换成推理算子——同样的收敛结构，会有一个更深的名字。

第十二章揭晓。

延伸阅读

• Hart, Nilsson, Raphael (1968). A Formal Basis for the Heuristic Determination of Minimum Cost Paths — A*算法原始论文,定义了可采纳性和一致性

• Yao, A. C.-C. (1977). Probabilistic Computations: Toward a Unified Measure of Complexity — 姚期智原理原始论文，MiniMax定理将确定性下界提升为随机化下界 → [FOCS 1977]

• [Zixi Li, 2026a] — ADS自适应双搜索,启发式的信息论化,知识蒸馏框架

• [Zixi Li, 2026b] — Collins随机化优化器,确定性下界与Chernoff上界,c_{\text{opt}} \approx 34的相变

• [Li & Jin, 2015] — 加权单位圆盘覆盖的PTAS,近似算法的黄金标准 → [arXiv:1502.04918]

• [Esmer et al., 2022] — 近似单调局部搜索的指数时间近似算法 → [arXiv:2206.13481]

• Pearl, J. (1984). Heuristics: Intelligent Search Strategies for Computer Problem Solving — 启发式搜索的经典教材

• Motwani, R. & Raghavan, P. (1995). Randomized Algorithms — 剑桥大学出版社出版的随机化算法权威教材，系统讲述Chernoff界、2-Universal哈希、MiniMax原理及其在算法设计中的应用

• Russell & Norvig (2020). Artificial Intelligence: A Modern Approach (4th ed.) — 第3-4章详细讨论A*及其变体