第20章：启发式的形式合同——"差不多对"的精确数学定义

可采纳性不是一个工程妥协。它是一个数学承诺。

第19章的结论令人沮丧：许多推理问题在计算上是根本困难的。不是算法不够好，而是问题本身的几何形状决定了没有捷径。

但人类和机器一直在解决这些"困难"问题。不精确地，不总是最优地，但通常足够好，足够快。

这里隐藏着一个问题："足够好"是什么意思？ 如果答案是任意的，那么任何算法只要不崩溃，都可以叫做"启发式"。但如果"足够好"有精确的数学含义，那么启发式就不是工程上的将就，而是一种有合同的承诺——承诺什么，以什么为代价，在什么条件下兑现。

这章要做的事，就是把这个合同写清楚。

20.0 乐观地图师游戏：启发式必须签合同

第19章告诉我们，很多迷宫太大，不能指望穷举。于是我们请来一位地图师。地图师不能告诉你完整路径，只能在每个路口给一个估计：从这里到终点大概还要多远。

这就是启发函数 h(n)。

但这个地图师必须签合同。第一份合同叫可采纳性：你可以乐观，但不能夸大困难。也就是说，估计距离不能超过真实最短距离：

如果地图师低估了距离，搜索只是多走几步；如果地图师高估了距离，搜索可能直接放弃真正的最优路径。第二份合同叫一致性：相邻路口之间的估计必须满足三角不等式，不能今天说“终点很近”，走一步又突然说“终点远得离谱”。

:::details 这个游戏的形式化骨架

• 状态空间：搜索图中的节点、已知代价 g(n)、启发估计 h(n)、优先队列。
• 合法动作：展开当前 f(n)=g(n)+h(n) 最小的节点，并更新其后继。
• 转移规则：从开放列表取出节点 n，把后继 n' 加入或更新，代价为 g(n')=g(n)+c(n,n')。
• 胜利条件：在可证明保证下找到最优路径，或得到近似比 / PAC 意义下的质量界。
• 失败模式：启发式没有合同，只是“看起来不错”，最终给出最快的错误答案。
  :::

这个游戏让“差不多对”变得精确。没有合同的启发式只是运气；有合同的启发式才是数学对象。可采纳性、一致性、近似比、PAC 保证，都是不同形式的合同条款。

启发式的尊严不在于它总能给出最优答案，而在于它诚实地说明：我承诺什么，不承诺什么；我在哪些条件下可靠，在哪些条件下会失败。

::: info 兔狲教授评
乐观可以是美德，也可以是诈骗。A* 允许启发函数乐观，因为乐观会让你继续探索；它不允许启发函数自大，因为自大会让你提前放弃真正的路。启发式的全部伦理，就藏在这条不等式里。
:::

20.1 两种近似的失败

先看两个近似方案，都直觉上合理，都在某些情况下出错。

方案一：贪心算法。每一步选择当前看起来最好的局部选择，不回头。旅行商问题里，每次走到最近的未访问城市；图着色问题里，每次给当前顶点分配编号最小的、和邻居不冲突的颜色。

贪心算法通常很快（多项式时间），但结果可能很差——有时候距离最优解差一个指数倍。贪心没有承诺，它只是"看起来不错"。

方案二：随机搜索。随机采样解空间，报告找到的最好结果。足够随机，够多次，也许能找到好解。

随机搜索也没有承诺——"也许"不是合同。在最坏情况下，解空间里好的解极其稀疏，随机搜索可能永远找不到。

::: info 兔狲教授评
大量实际系统在用的就是"也许"——随机重启、多次采样、取最好的结果。这些方法在实践里有时有效，但你不知道在什么情况下会失效，也不知道失效的概率是多少。没有合同，就没有失败条件，你甚至连算法是否在工作都无法判断。"有时候有效"不是保证，是运气。
:::

这两种方案的共同问题：没有对"差多远"给出可证明的界。启发式合同需要的，正是这个界。

20.2 可采纳性：永远不高估

搜索问题里最经典的启发式框架，是 A* 算法。它的核心是一个启发函数 h(n)，估计从当前状态 n 到目标的代价。

A* 算法维护一个优先队列，每次展开估计总代价 f(n) = g(n) + h(n) 最小的节点，其中 g(n) 是从起点到 n 的已知实际代价，h(n) 是从 n 到目标的估计代价。

这个算法找到最优解的条件，精确地落在 h 的一个性质上：

定义（可采纳性）：启发函数 h 是可采纳的（admissible），如果对所有节点 n，

其中 h^*(n) 是从 n 到目标的真实最优代价。

可采纳性的含义：h 永远不高估。它可以低估——低估意味着乐观，乐观意味着这条路会被继续探索。但如果高估，算法可能提前放弃一条实际上是最优的路径。

定理（A 完备性）*：若启发函数 h 可采纳，则 A* 算法在有解时一定找到最优解。

这是启发式合同的第一种形式：给我一个永远不高估的估计，我保证给你最优解。代价是你要花时间构造这个估计，以及算法可能需要探索更大的搜索空间。

::: info 可采纳性是如何被违反的
一个常见的错误是用真实代价的粗略上界作为启发函数——这当然会高估，从而破坏可采纳性。比如在地图搜索里，如果用直线距离作为 h，这是可采纳的（直线距离永远不超过实际路径距离）；如果用某个估计值导致在弯曲道路上高估，就不可采纳。可采纳性的违反通常不是显而易见的——它依赖于问题的具体结构。
:::

20.3 一致性：三角不等式的约束

可采纳性保证了最终结果的质量，但 A* 的效率还依赖 h 的另一个性质。

定义（一致性）：启发函数 h 是一致的（consistent），如果对所有节点 n 和它的后继 n'，

其中 c(n, n') 是从 n 到 n' 的实际边代价。

这是一个三角不等式：从 n 到目标的估计代价，不超过先走到 n' ，再从 n' 到目标的代价之和。直觉上，一致性说的是：你对每个节点的估计是"连贯的"——不会出现走一步之后，估计值反而暴增的情况。

一致性蕴含可采纳性（可以验证），但反过来不成立。一致性是更强的条件。

在一致性下，A 展开的每个节点，f 值非递减*。这保证了：A* 第一次到达目标节点时，找到的就是最优路径，无需再继续搜索。一致性把 A* 从"最终找到最优"推进到"尽早找到最优"。

这两个性质——可采纳性和一致性——构成了启发式合同的精确数学内容。有了它们，"启发式"就不是随便猜，而是一个在可证明界内工作的估计机制。

回到乐观地图师游戏，可采纳性规定地图师不能把近路说成远路，一致性规定他不能在相邻路口之间胡乱改口。A* 的聪明不在于“相信直觉”，而在于只相信签过合同的直觉。没有这份合同，启发式只是一个会说漂亮话的向导；有了这份合同，它才成为形式系统里的合法动作。

20.4 近似比：最坏情况的保证

A* 的框架在最优性有意义的问题里运作良好。但许多 NP 完全问题，最优解本身就难以找到，即使允许近似。这时需要另一种合同：近似比。

定义（近似算法）：对于一个最小化问题，若算法 \mathcal{A} 对任意实例总是返回一个解，其代价不超过最优解代价的 \rho 倍，则称 \mathcal{A} 是 \rho-近似算法，\rho 叫做近似比。

近似比是启发式合同的最坏情况版本：无论输入是什么，输出的质量保证在最优解的 \rho 倍以内。\rho = 1 是精确解，\rho = 2 是"至多两倍于最优"。

一些著名的结果：

• 顶点覆盖问题：存在 2-近似算法（找一个极大匹配，取两端点）。
• 旅行商问题（度量版本）：存在 1.5-近似算法（Christofides 算法，1976年）。这个结果保持了近半个世纪，直到 2020 年才被略微改进。
• 旅行商问题（一般版本，不满足三角不等式）：若 P ≠ NP，则对任意常数 \rho，不存在多项式时间的 \rho-近似算法。

最后这个结果是关键：对某些问题，近似同样是 NP 难的。允许误差并不总是让问题变简单。近似比本身也有一个信息论下界，这个下界来自问题的内在结构，不依赖任何具体算法。

::: info 近似比的不可突破性
旅行商问题一般版本的近似不可能性证明，用的是归约：如果存在一个多项式时间的 \rho-近似算法，就可以用它来判断哈密顿回路是否存在——而哈密顿回路问题是 NP 完全的。这个归约说明，任何足够好的近似，都蕴含着精确求解能力。问题的内在结构，在近似层面留下了痕迹。
:::

20.5 PAC 学习："差不多对"的概率版本

近似比是关于解的质量，PAC 学习框架把同样的精神应用到了学习问题上。

定义（PAC 学习）：一个概念类 \mathcal{C} 是 PAC 可学习的（Probably Approximately Correct），如果存在算法 \mathcal{L}，使得：对任意目标概念 c \in \mathcal{C}，任意数据分布 \mathcal{D}，以及任意参数 \varepsilon > 0（误差容忍）和 \delta > 0（失败概率），当样本量 m 足够大（关于 \varepsilon, \delta 的多项式），\mathcal{L} 以概率至少 1 - \delta 输出一个假设 h，使得

用中文说清楚：以高概率（至少 1-\delta），输出一个近似正确（错误率至多 \varepsilon）的假设。PAC 是"Probably Approximately Correct"的缩写——这不是自嘲，而是一个精确的数学承诺。

::: info 兔狲教授评
很多人看到"以高概率近似正确"会觉得这是在降低标准。恰好相反——\varepsilon 和 \delta 不是模糊词，是可以算出来的数。这比很多声称"准确"的方法更诚实：它知道自己承诺了什么，也知道承诺在哪里会破。知道自己的边界，比假装没有边界，要诚实得多。
:::

PAC 框架的核心结论：样本量 m 只需关于 1/\varepsilon 和 1/\delta 呈多项式增长，学习就可以完成。这意味着：不需要无限数据，有限的、多项式量级的数据就足以以高概率学到近似正确的概念。

::: info VC 维：假设空间的复杂度
PAC 框架里，所需样本量还依赖另一个量：假设空间 \mathcal{H} 的 VC 维（Vapnik-Chervonenkis dimension）。VC 维衡量 \mathcal{H} 能"打散"的最大点集大小——能打散一个大小为 d 的点集，意味着对这些点的任意标签，\mathcal{H} 里都有假设能完美拟合。VC 维越高，假设空间越复杂，需要越多样本来约束。基本的 PAC 样本复杂度定理：m = O\!\left(\frac{1}{\varepsilon}\left(d \ln \frac{1}{\varepsilon} + \ln \frac{1}{\delta}\right)\right)，其中 d 是 VC 维。这把上卷第5章的"过拟合"直觉——假设空间太复杂，需要更多数据——变成了可计算的界。
:::

20.6 三种合同的统一

把这一章的内容并排看：

三种合同，三种不同的"差不多对"——对应三种不同的代价结构和保证类型。它们的共同点是：都把"差不多"从直觉词变成了数学量。合同可以违反，但违反是可检测的。这和第14章的形式系统精神完全一致：精确定义允许精确批评。

启发式不是因为精确推理太难而不得不将就的残次品。它是在计算约束下，对推理质量的理性承诺——知道自己承诺了什么，知道承诺的边界在哪里。

悬而未决

近似的边界能被突破吗？ 对某些问题，近似比有一个不可逾越的下界（假设 P ≠ NP）。但近似算法的理论还有大量未解问题：旅行商问题的最优近似比是多少？唯一博弈猜想（Unique Games Conjecture）是否成立——它决定了大量问题的近似下界。这个方向的问题，往往比 P ≠ NP 本身更容易陈述，同样深刻。

PAC 学习的计算版本：PAC 框架保证了样本复杂度，但没有保证计算复杂度。有些概念类在样本意义上是可学习的，但学习算法本身可能需要指数时间。区分"信息论可学习"和"计算可学习"，是学习理论的核心张力——前者问需要多少数据，后者问需要多少时间。

启发式能被自动发现吗？ A* 需要人工设计 h，PAC 学习需要人工选择假设空间 \mathcal{H}。能否从数据里自动发现好的启发函数，或者从问题结构里自动推断合适的假设空间？这个问题把启发式设计本身变成了一个推断问题——而推断问题，正是第21章的主题：学习，能否被理解为从数据里推断出最短描述？

思考题

★ 热身

A* 算法在地图寻路中常用直线距离作为启发函数 h。判断以下哪些 h 是可采纳的，哪些不是，并给出一句话理由。

1. h(n) = 0（零启发，退化为 Dijkstra 算法）
2. h(n) = 从 n 到目标的直线距离（欧几里得距离）
3. h(n) = 从 n 到目标的直线距离 \times 2
4. h(n) = 从 n 到目标的实际最短路径长度（假设你已经知道）
5. h(n) = 从 n 到目标沿曼哈顿距离（仅允许上下左右移动时）

★★ 推导

1. 可采纳性的代价：设计一个简单的搜索问题（画一个5个节点的图，标上边权），使得：可采纳的启发函数 h_1 需要展开更多节点才找到最优解，而不可采纳的 h_2 用更少节点找到了同一个解。写出两个 h 的具体值，并追踪 A* 在两种情况下的展开顺序。这说明可采纳性保证的是什么，不保证的是什么？

2. PAC 与贝叶斯的关系：第17章的贝叶斯推断和本章的 PAC 学习，都处理"从有限数据泛化"。PAC 的保证对最坏分布成立，贝叶斯的保证依赖先验。哪种保证对假设更少？在一个"先验完全错误"的场景下，哪种框架会先崩溃？

★★★ 挑战

旅行商问题（TST）的一般版本（不满足三角不等式时）被证明：若 P ≠ NP，则对任意常数 \rho，不存在多项式时间的 \rho-近似算法。

这个"不可近似性"的证明用的是归约：如果存在 \rho-近似算法，就可以解决哈密顿回路问题（NP完全）。试着用自然语言描述这个归约的大致思路——你如何把一个哈密顿回路的判定实例，转化成一个旅行商问题的实例，使得"找到近似解"等价于"判断哈密顿回路存在"？

这个练习的目标不是写出完整证明，而是理解：为什么允许误差并不总是让问题变简单——在某些情况下，近似和精确一样难。