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

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

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

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

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

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

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

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

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

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

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

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

这个游戏的形式化骨架

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

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

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

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

20.1 两种近似的失败

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

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

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

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

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

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

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

一个具体的失败现场

用一个极简单的旅行商问题（4个城市，边权如下）看清楚贪心和随机的区别：

城市: A, B, C, D
边权（距离）:
  A-B: 10, A-C: 15, A-D: 20
  B-C: 35, B-D: 25
  C-D: 30
最优的哈密顿回路: A->B->D->C->A, 总代价 = 10+25+30+15 = 80

贪心（最近邻）从A出发：A到B（10，最短）-> B到D（25，除A外最短，因为B到C是35）-> D到C（30）-> 被迫回到A（15）。路径：A->B->D->C->A，代价 = 10+25+30+15 = 80。这次碰巧对了，因为图太小。

但换一个出发点的代价：从B出发-> B到A（10）-> A到C（15）-> C到D（30）-> 被迫回B（35）。路径：B->A->C->D->B，代价 = 10+15+30+35 = 90。次优。这还只是4个城市；城市多起来，贪心的误差可以指数级放大。

随机搜索：随机采样100条回路，最好的可能是85，也可能110——没有承诺。多跑几次，每次答案不同。

这两种都没有合同。贪心只在某些图上对，随机永远不确定。缺少的正是那条不等式： $h (n) \leq h^{*} (n)$ 。有了它，你才知道乐观的边界在哪里。

看到没有？贪心在这个小图上从A出发是对的，从B出发就是错的。你不能拿"它在A上对了"来证明算法有效——一个没有合同的算法，不是"大致有效"，而是"你不知道它什么时候失效"。这是可以致命的。

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) \leq h^{*} (n)

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

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

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

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

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

20.2.5 实操：追踪一次完整的A*搜索

光看定义不够。下面用一个6节点的有向图，完整追踪A*的每一步。建议你拿张纸，跟着画。

节点: S (起点), A, B, C, D, G (目标)
边 (S->节点, 代价):
  S->A: 1,  S->B: 4
  A->C: 3,  A->D: 2
  B->D: 2
  C->G: 2
  D->G: 4

启发函数 h (到G的估计代价):
  h(S)=5, h(A)=4, h(B)=4, h(C)=2, h(D)=2, h(G)=0

真实最优代价 h* (可以通过反向Dijkstra验证):
  h*(S)=5 (S->A->C->G: 1+3+2=6? 不对...
  实际: S->A->D->G: 1+2+4=7; S->B->D->G: 4+2+4=10; S->A->C->G: 1+3+2=6)
  最短: S->A->C->G = 6, 所以 h*(S)=6, h(S)=5 ≤ 6 ✓ 可采纳
  h*(A)=5 (A->C->G=3+2=5), h(A)=4 ≤ 5 ✓
  h*(B)=6 (B->D->G=2+4=6), h(B)=4 ≤ 6 ✓
  h*(C)=2, h(C)=2 ✓ (恰好精确)
  h*(D)=4, h(D)=2 ≤ 4 ✓
  h*(G)=0, h(G)=0 ✓

所有节点都满足 h(n) ≤ h*(n), h是可采纳的。

追踪A*：

初始：优先队列 = [(S, f=0+5=5)]。g(S)=0。

第1步：展开S（f=5最小）。后继：

A: g=1, f=1+4=5 -> 加入队列
B: g=4, f=4+4=8 -> 加入队列队列：[(A,5), (B,8)]

第2步：展开A（f=5最小）。后继：

C: g=1+3=4, f=4+2=6 -> 加入
D: g=1+2=3, f=3+2=5 -> 加入队列：[(D,5), (C,6), (B,8)]

第3步：展开D（f=5最小）。后继：

G: g=3+4=7, f=7+0=7 -> 加入队列：[(C,6), (G,7), (B,8)]

第4步：展开C（f=6最小）。后继：

G: g=4+2=6, f=6+0=6 -> 更新G（已有f=7的版本，新的f=6更好，替换）队列：[(G,6), (B,8)]

第5步：展开G（f=6最小）。G是目标，找到路径 S->A->C->G，总代价6。

注意：第3步时，A没有走S->A->D->G这条路（总代价=7），因为D展开后G的f=7，而队列里C的f=6更优先。A正确地跳过了次优路径。

现在，如果把h改成不可采纳的会怎样？设 $h^{'} (A) = 6$ （高估了，因为真实h*=5）。那么：

展开S后，A的f=1+6=7, B的f=4+4=8
队列：[(A,7), (B,8)]
展开A（f=7），D的f=5, C的f=6
队列：[(C,6), (D,7), (B,8)]
展开C，G的f=6...最终仍然找到了最优，但这是因为图太小。

在更复杂的图上，高估会导致A*提前认定某条路径"不值得探索"——而那条路径恰好是最优的。可采纳性不保证效率，可采纳性保证不会错过最优。丢了它，最优就可能从你手中溜走，而你永远不会知道。

仔细看第3步：展开D的时候，队列里有C(f=6)，D(f=5)。A选D，因为D更乐观。乐观让A愿意冒险，但也让它在看到更好的路径时能及时掉头——因为乐观是向下修正的，不是向上。如果h是自大的（高估），A*就会过早地丢掉某些节点，永远不回头。乐观是探索的动力，自大是错过的原因。

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

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

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

h (n) \leq c (n, n^{'}) + h (n^{'})

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

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

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

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

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

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

20.3.5 一致性被违反时：A* 的困惑

用20.2.5的同一个图，构造一个可采纳但不一致的h：

设 $h^{″} (S) = 5, h^{″} (A) = 4, h^{″} (B) = 5, h^{″} (C) = 2, h^{″} (D) = 1, h^{″} (G) = 0$ 。

检查可采纳性：所有 $h^{″} (n) \leq h^{*} (n)$ 吗？

$h^{″} (B) = 5 \leq 6$ ✓， $h^{″} (D) = 1 \leq 4$ ✓。是的，可采纳。

检查一致性：对每条边 $(n, n^{'})$ ， $h^{″} (n) \leq c (n, n^{'}) + h^{″} (n^{'})$ 吗？

边 B->D： $h^{″} (B) = 5$ ， $c (B, D) + h^{″} (D) = 2 + 1 = 3$ 。 $5 \leq 3$ ？不成立。

这里发生了什么？从B看起来，到G的估计是5；但从D（B走一步后）看，估计突然变成了1。地图师在B说了”还远着呢”，走一步到D又改口”快到了”。这个改口让A*困惑：

从S出发：A(f=5), B(f=4+5=9)。选A。然后D的f=1+2+1=4。选D。然后G的f=3+4+0=7。选C(f=6)。C->G(f=6)。找到最优路径S->A->C->G，代价6。

看起来没问题？但问题出现在这个细节：在D被展开后，队列里有C(f=6)和G(f=7,f via D)。如果我们之后发现另一条到D的更短路（比如S->B->D的代价更小？不，S->B->D是4+2=6，比S->A->D的3更差），而h''是不一致的，我们可能需要重新展开已展开的节点。一致性保证了f值非递减，从而第一次到达目标就是最优；不一致时，A*可能要在目标节点上继续搜索，直到f值超过当前最优代价。

在更大规模的搜索中，不一致的代价是巨大的：A可能需要重新展开节点，算法退化到接近Dijkstra的效率。一致性不是装饰——它是A效率的合同。

不一致的启发函数就像一个反复无常的导游。他告诉你在B时还剩5公里；你走到D，他又说其实还剩1公里。加在一起，B->D这段路他只算了2公里（5->1），但实际距离也是2公里——“刚好”对上。但如果你在D时他又突然说还剩4公里（到下一个路口），你会开始怀疑：他到底知不知道自己在说什么？A*的怀疑是数学层面的：不一致时，f值可能下降，算法不再保证第一个解就是最优。

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

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

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

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

一些著名的结果：

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

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

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

20.4.5 实操：顶点覆盖的2-近似——极大匹配的力量

顶点覆盖问题：给定图 $G = (V, E)$ ，找一个最小的顶点集合 $C \subseteq V$ ，使得每条边至少有一个端点在 $C$ 中。这是一个NP完全问题。但存在一个简单的2-近似算法——记住，2意味着你找到的集合最多是最优解的2倍大。

算法（极大匹配法）：

找图的一个极大匹配 $M$ （不能再添加任何边的匹配）
输出 $M$ 中所有边的两个端点

为什么这是2-近似？

设 $M$ 是找到的极大匹配，包含 $k$ 条边。输出集 $C$ 包含这 $k$ 条边的 $2 k$ 个端点。

下界：最优顶点覆盖至少需要 $k$ 个顶点。因为 $M$ 中的 $k$ 条边彼此不共享端点（匹配的性质），要覆盖这 $k$ 条边，至少需要 $k$ 个顶点——每条边至少选一个端点，而且选的不同边不能共享顶点。所以 $OPT \geq k$ 。
上界：我们输出了 $2 k$ 个顶点， $| C | = 2 k \leq 2 \cdot OPT$ 。✓

为什么极大（不是最大）就够了？ 一个简单的贪心构造极大匹配：遍历所有边，如果当前边的两个端点都还没被匹配覆盖，就把这条边加入匹配。最终得到的不一定是最大匹配（边数最多的匹配），但一定是极大的（无法再添加边）。对于2-近似，极大就足够了。

一个具体例子：

图: 顶点 {1,2,3,4,5}
边: (1,2), (2,3), (3,4), (4,5), (1,5)

贪心极大匹配（按边顺序遍历）：

遇到(1,2)：1和2都未匹配 -> 加入M。M=
遇到(2,3)：2已匹配 -> 跳过
遇到(3,4)：3和4都未匹配 -> 加入M。M=
遇到(4,5)：4已匹配 -> 跳过
遇到(1,5)：1已匹配 -> 跳过

输出C = {1,2,3,4}，大小4。

最优解是多少？这个图是5个顶点的环。要覆盖所有5条边，至少需要3个顶点（每隔一个取一个，可以取{2,4,5}覆盖所有边）。所以OPT=3。我们的解是4，近似比4/3≈1.33 ≤ 2。✓

换个遍历顺序会怎样？如果先遇到(2,3)再遇到(1,2)和(3,4)，M可能变成{(2,3),(4,5)}或{(2,3),(1,5)}，输出的大小都是4。不同的极大匹配给出不同但都在2倍以内的解。

注意这个算法的美感：它没有尝试"聪明地"选择顶点，它依赖一个极其简单的事实——匹配的大小天然是OPT的下界。这个下界不是算出来的，是图的结构本身提供的。好的近似算法，往往不是"聪明地逼近最优"，而是"找到了一个必然接近最优的简单结构"。这和李雅普诺夫函数有异曲同工之处——都是找到一个天然递减（或天然界住）的量。

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

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

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

P_{x \sim D} [h (x) \neq c (x)] \leq ε

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

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

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

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

20.5.5 实操：VC维的三道练习题

例1：实数线上的区间。假设空间 $H_{1}$ 是实数线上的闭区间 $[a, b]$ ：对一个点 $x$ ，预测+1若 $x \in [a, b]$ ，否则-1。能打散多大的点集？

2个点：设点在位置 $x_{1} = 0, x_{2} = 1$ 。能产生所有4种标签吗？

(+,+)：区间 $[0, 1]$ ✓
(-,-)：区间 $[2, 3]$ （不覆盖任何点）✓
(+,-)：区间 $[0, 0]$ ✓
(-,+)：不可能。因为如果一个区间覆盖了右边的点( $x_{2} = 1$ )，它必定也覆盖中间的任何点。但要覆盖 $x_{2}$ 而不覆盖 $x_{1}$ ？如果 $x_{1} = 0 < x_{2} = 1$ ，任何包含 $x_{2}$ 的区间，如果也包含 $x_{1}$ 之间的所有点...等等——区间是连续的，但 $x_{1}$ 和 $x_{2}$ 是离散点。区间 $[0.5, 1.5]$ 包含 $x_{2}$ 但不含 $x_{1} = 0$ 。所以 (-,+) 是可能的！区间 $[0.5, 1.5]$ 给 $x_{1}$ 标签-1，给 $x_{2}$ 标签+1。✓

4种都能产生。所以VC维 ≥ 2。

3个点：在 $x_{1} = 0, x_{2} = 1, x_{3} = 2$ 上，能产生 (+,-,+) 吗？需要覆盖 $x_{1}$ 和 $x_{3}$ 但不覆盖 $x_{2}$ 。但区间是连续的，任何覆盖0和2的区间必定覆盖1。所以 (+,-,+) 不可能。VC维 = 2。

例2：平面上的线性分类器（通过原点的直线）。 $H_{2}$ ： $sign (w \cdot x)$ ， $w \in R^{2}$ 。能打散平面上3个不共线的点吗？可以——8种标签都能实现。4个点呢？不能——存在4个点的集合，任何通过原点的直线无法打散。VC维 = 2（因为直线必须过原点，损失了一个自由度；不要求过原点的直线VC维=3）。

例3：神经网络和VC维的张力。一个具有 $W$ 个权重的神经网络，其VC维大约是 $O (W \log W)$ 量级。但现代深度网络动辄数十亿参数——按PAC理论，需要天文数字的样本。而实践中，这些网络用远少于理论要求的样本就能泛化。这个张力正是第21章"泛化=压缩"视角的出发点：VC维衡量的是最坏情况下的复杂度，但实际网络的有效复杂度远低于参数数量——大量参数被结构约束（权重衰减、架构设计、SGD的隐式正则化）压缩到了远小的有效空间里。

把这三道题并排，你看到什么？VC维不是一个模糊的"复杂度"，而是可以手算的具体数字。2、2（或3）、数十亿——这些数字告诉你为什么有些假设类容易学，有些需要更多数据，有些让理论家困惑。可计算性是最好的清醒剂。

20.6 三种合同的统一

把这一章的内容并排看：

合同类型	承诺	条件	代价
可采纳性 + A*	找到最优解	$h$ 永远不高估	可能探索更大空间
近似比 $ρ$	解不超过最优的 $ρ$ 倍	最坏情况保证	放弃最优
PAC 学习	以高概率近似正确	足够多样本	允许失败概率 $δ$

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

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

20.7 合同签订之后：谁来写合同？

这一章建立了一个令人安心的框架：只要签了合同，启发式的行为就有数学保证。但有一个问题我们一直在回避：合同是谁写的？

可采纳的启发函数 $h$ 需要人工设计。PAC 学习的假设空间 $H$ 需要人工选择。近似算法的近似比需要人工证明。这些"合同"，全部来自系统外部的设计者。

回到第15章的语言：在形式系统里，公理需要从外部输入，系统自身无法选择公理。在启发式合同里，合同的条款（ $h$ 的形式、 $H$ 的结构、近似比的证明）同样来自系统外部。

这意味着：当前所有的"有保证的推理"，都在依赖一个外部承诺——你相信设计者选的启发函数是合理的，相信选的假设空间是合适的。但如果这个外部承诺本身是错的呢？如果在某个场景下，你的启发函数系统性地高估了，而你不知道呢？

这个问题引出了一个更深的问题：合同能不能从数据里自动写出来？ 能不能让系统观测自己的行为，从成功和失败中推断出合适的启发式？如果启发式的设计本身是一个推断问题——从问题实例的历史中，推断出什么样的估计策略在未来的实例上有效——那么启发式的设计就是元学习。

而元学习，正是第21章要打开的门：学习，能否被理解为从数据里推断出最短描述？如果学习是逆推断，那么"学到一个好的启发式"这件事，本身能不能被理解为一种逆推断？

这三个问题——谁写合同、合同能不能自动写、写合同本身算不算学习——把我们从"启发式的形式化"推向了"学习的逆推断结构"。合同的形式化是这一章的工作；合同从哪来，是下一章的工作。最终的答案，在第25章。

悬而未决

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

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

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

思考题

★ 热身

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

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

★★ 推导

可采纳性的代价：设计一个简单的搜索问题（画一个5个节点的图，标上边权），使得：可采纳的启发函数 $h_{1}$ 需要展开更多节点才找到最优解，而不可采纳的 $h_{2}$ 用更少节点找到了同一个解。写出两个 $h$ 的具体值，并追踪 A* 在两种情况下的展开顺序。这说明可采纳性保证的是什么，不保证的是什么？
PAC 与贝叶斯的关系：第17章的贝叶斯推断和本章的 PAC 学习，都处理"从有限数据泛化"。PAC 的保证对最坏分布成立，贝叶斯的保证依赖先验。哪种保证对假设更少？在一个"先验完全错误"的场景下，哪种框架会先崩溃？

★★★ 挑战

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

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

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

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

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

20.1 两种近似的失败 ​

一个具体的失败现场 ​

20.2 可采纳性：永远不高估 ​

20.2.5 实操：追踪一次完整的A*搜索 ​

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

20.3.5 一致性被违反时：A* 的困惑 ​

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

20.4.5 实操：顶点覆盖的2-近似——极大匹配的力量 ​

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

20.5.5 实操：VC维的三道练习题 ​

20.6 三种合同的统一 ​

20.7 合同签订之后：谁来写合同？ ​

悬而未决 ​

思考题 ​