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

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

---

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

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

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

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

---

20.1 两种近似的失败

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

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

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

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

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

兔狲教授评

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

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

---

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)\le h^{\ast }(n)$$

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

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

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

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

可采纳性是如何被违反的

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

---

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

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

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

$$h(n)\le c(n,n^{\prime })+h(n^{\prime })$$

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

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

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

在一致性下，A 展开的每个节点，$f$ 值非递减*。这保证了：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 难的。允许误差并不总是让问题变简单。近似比本身也有一个信息论下界，这个下界来自问题的内在结构，不依赖任何具体算法。

近似比的不可突破性

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

---

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

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

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

$$P_{x\sim \mathcal{D}}[h(x)\ne c(x)]\le \epsilon$$

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

兔狲教授评

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

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

VC 维：假设空间的复杂度

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

---

20.6 三种合同的统一

把这一章的内容并排看：

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

三种合同，三种不同的"差不多对"——对应三种不同的代价结构和保证类型。它们的共同点是：都把"差不多"从直觉词变成了数学量。合同可以违反，但违反是可检测的。这和第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完全）。试着用自然语言描述这个归约的大致思路——你如何把一个哈密顿回路的判定实例，转化成一个旅行商问题的实例，使得"找到近似解"等价于"判断哈密顿回路存在"？

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