第20章:启发式的形式合同——"差不多对"的精确数学定义
可采纳性不是一个工程妥协。它是一个数学承诺。
第19章的结论令人沮丧:许多推理问题在计算意义上是根本困难的。不是算法不够好,而是问题本身的几何形状决定了没有捷径。
但人类和机器一直在解决这些"困难"问题。不精确,不总是最优,但通常足够好,足够快。
这里藏着一个问题:"足够好"是什么意思? 如果答案是任意的,那么任何不崩溃的算法都可以自称"启发式"。但如果"足够好"有精确的数学含义,那么启发式就不是工程妥协,而是一份带合同的承诺:承诺什么,以什么为代价,在什么条件下兑现。
这正是本章要做的事:把这份合同写清楚。
20.0 乐观制图师游戏:启发式必须签合同
第19章告诉我们,很多迷宫太大,不能指望蛮力穷举。于是我们雇一位制图师。制图师不能告诉你完整路线;在每个路口,他只能给出一个估计:从这里到终点大概还有多远。
这就是启发函数
但这位制图师必须签合同。第一份合同叫可采纳性:你可以乐观,但不能夸大困难。也就是说,估计距离不能超过真实最短距离:
如果制图师低估了距离,搜索只是多走几步。如果制图师高估了距离,搜索可能完全放弃真正的最优路径。第二份合同叫一致性:相邻路口之间的估计必须满足三角不等式——制图师不能今天说"我们快到了",走一步之后突然又说"还远得很"。
这个游戏的形式化骨架
- 状态空间:搜索图中的节点、已知代价
、启发估计 ,以及一个优先队列。 - 合法动作:展开
最小的节点,然后更新它的后继。 - 转移规则:从开放列表取出节点
,把每个后继 加入或更新,代价为 。 - 胜利条件:在可证明的保证下找到最优路径,或者得到近似比 / PAC 式的质量界。
- 失败模式:启发式没有合同——它只是"看起来不错",最终给出最快的错误答案。
这个游戏把"足够好"变得精确。没有合同的启发式只是运气;有合同的启发式才是数学对象。可采纳性、一致性、近似比、PAC 保证——这些都是不同合同的不同条款。
启发式的尊严不在于它总能给出最优答案,而在于它诚实地说明:我承诺什么,不承诺什么;在哪些条件下我可靠,在哪些条件下我会失败。
乐观可以是美德,也可以是诈骗。A* 允许启发函数乐观,因为乐观让你继续探索;它不允许启发函数自大,因为自大让你过早放弃一条真正的路。启发式的全部伦理,就藏在这条不等式里。
20.0.5 用代码玩这个游戏
20.2.5 节在一个六节点图上手工追踪了一次 A* 搜索。下面的程序用同一个算法把同一个图跑了两遍——一遍用书里的可采纳启发式,一遍在节点 A 处加一个高估。同样的迷宫,同样的算法:一个返回最优路线,另一个给出最快的错误答案。
#!/usr/bin/env python3
"""
optimistic_cartographer.py -- the Optimistic Cartographer Game of Ch. 20.
Book reference: The Reasoning Kingdom, Volume 2, Chapter 20, Section 20.0
"The Optimistic Cartographer Game: Heuristics Must Sign a Contract."
The maze is too big for brute force, so we hire a cartographer who, at
every intersection, estimates how far the goal still is: the heuristic
h(n). This program runs A* on the exact six-node graph the book traces
by hand in Section 20.2.5, with two cartographers:
* the honest one, whose estimates never exceed the true distance
(admissible: h <= h*) -- the contract of Section 20.0;
* the arrogant one, who overestimates at node A -- no contract.
Same maze, same algorithm: one returns the optimal route, the other
delivers the fastest wrong answer. That is the whole ethics of
heuristics, hiding inside one inequality.
Run: python3 optimistic_cartographer.py
"""
import heapq
# The book's graph, Section 20.2.5: S (start), A, B, C, D, G (goal).
EDGES = {
"S": (("A", 1), ("B", 4)),
"A": (("C", 3), ("D", 2)),
"B": (("D", 2),),
"C": (("G", 2),),
"D": (("G", 4),),
"G": (),
}
HONEST_H = {"S": 5, "A": 4, "B": 4, "C": 2, "D": 2, "G": 0}
ARROGANT_H = {"S": 5, "A": 10, "B": 1, "C": 2, "D": 2, "G": 0}
START, GOAL = "S", "G"
def astar(edges, h, start, goal):
"""A* on a graph; returns (path, cost, expanded_in_order)."""
heap = [(h[start], 0, start, [start])]
best_g = {start: 0}
expanded = []
while heap:
_, g, node, path = heapq.heappop(heap)
if g > best_g.get(node, float("inf")):
continue
expanded.append(node)
if node == goal:
return path, g, expanded
for nxt, cost in edges.get(node, ()):
ng = g + cost
if ng < best_g.get(nxt, float("inf")):
best_g[nxt] = ng
heapq.heappush(heap, (ng + h[nxt], ng, nxt, path + [nxt]))
return None, None, expanded
def trace(name, h, expected):
path, cost, expanded = astar(EDGES, h, START, GOAL)
print(f"\n{name}:")
print(f" route found: {' -> '.join(path)}")
print(f" total cost: {cost}")
print(f" nodes expanded in order: {' -> '.join(expanded)}")
assert path == expected["path"] and cost == expected["cost"]
def demo():
print("=" * 70)
print(" THE OPTIMISTIC CARTOGRAPHER GAME -- two cartographers, one maze")
print(" The Reasoning Kingdom, Volume 2, Chapter 20 (Sec. 20.0, 20.2.5)")
print("=" * 70)
print("\nThe maze (the same six nodes the book traces by hand):")
print(" S->A:1 S->B:4 A->C:3 A->D:2 B->D:2 C->G:2 D->G:4")
print("\nThe honest cartographer -- h never exceeds the true distance:")
print(" h: S=5, A=4, B=4, C=2, D=2, G=0 (h(n) <= h*(n) everywhere)")
trace("honest cartographer (admissible)", HONEST_H,
{"path": ["S", "A", "C", "G"], "cost": 6})
print(" optimal route S->A->C->G, cost 6 -- exactly what the hand")
print(" trace in the book found.")
print("\nThe arrogant cartographer -- one lie, at node A:")
print(" h: S=5, A=10, B=1, C=2, D=2, G=0 (h(A)=10 > h*(A)=5: contract broken)")
trace("arrogant cartographer (inadmissible)", ARROGANT_H,
{"path": ["S", "B", "D", "G"], "cost": 10})
print(" route S->B->D->G, cost 10. The overestimate at A made the")
print(" search abandon the truly optimal path. Optimism keeps you")
print(" exploring; arrogance makes you give up on a real path early.")
print(" Same maze, same algorithm -- one inequality of difference.")
print("=" * 70)
if __name__ == "__main__":
demo()20.1 两种近似如何失败
先看两种近似方案。它们听起来都符合直觉,也都会在某些情况下出错。
方案一:贪心算法。 每一步都做局部看起来最好的选择,绝不回头。在旅行商问题里,总是走向最近的未访问城市;在图着色问题里,总是给当前顶点分配与邻居不冲突的最小颜色编号。
贪心算法通常很快(多项式时间),但结果可能很糟——有时比最优解差一个指数因子。贪心没有承诺,它只是"看起来不错"。
方案二:随机搜索。 在解空间里随机采样,报告找到的最好结果。足够随机,跑足够多次,也许就能找到一个好解。
随机搜索也没有承诺——"也许"不是合同。在最坏情况下,好的解极其稀疏,随机搜索可能永远找不到。
现实世界中有很大一部分系统靠的就是"也许"——随机重启、反复采样、保留最好结果。这些方法在实践中有时有效,但你不知道它们什么时候会失效,也不知道失败的概率。没有合同,就没有失败条件——你甚至无法判断算法是否在工作。"有时候有效"不是保证,是运气。
这两种方案的共同问题:它们都没有给出"差多远"的可证明界。而这个界,正是启发式合同所要求的。
一个具体的失败现场
拿一个极其简单的旅行商问题——4 个城市,边权如下——你就能亲眼看到贪心和随机的区别:
Cities: A, B, C, D
Edge weights (distances):
A-B: 10, A-C: 15, A-D: 20
B-C: 35, B-D: 25
C-D: 30
Optimal Hamiltonian cycle: A->B->D->C->A, total cost = 10+25+30+15 = 80贪心(最近邻)从 A 出发:A 到 B(10,最短)-> B 到 D(25,从 B 出发除 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——没有承诺。再跑一次,每次答案都不同。
两者都没有合同。贪心在某些图上对,随机永远不确定。缺的正是那条不等式:
看到了吗?贪心在这个小图上从 A 出发是对的,从 B 出发就错了。你不能用"它在 A 上对了"来证明算法有效——没有合同的算法不是"大致有效",而是"你不知道它什么时候失效"。这是会致命的。
20.2 可采纳性:永远不高估
搜索中最经典的启发式框架是 A* 算法。它的核心是一个启发函数
A* 维护一个优先队列,每一步展开估计总代价
这个算法能找到最优解的条件,精确地落在
定义(可采纳性):启发函数
其中
可采纳性的含义:
定理(A 完备性)*:如果启发函数
这是启发式合同的第一种形式:给我一个永远不高估的估计,我保证给你最优解。代价是你必须花时间构造这个估计,而且算法可能需要探索更大的搜索空间。
一个常见错误是把真实代价的粗略上界当作启发式——这自然会高估,从而破坏可采纳性。例如,在地图搜索中,如果用直线距离作为
20.2.5 实操:追踪一次完整的 A* 搜索
光看定义不够。下面是一个 6 节点有向图;让我们逐步追踪 A* 的每一步。拿张纸,跟着画。
Nodes: S (start), A, B, C, D, G (goal)
Edges (S->node, cost):
S->A: 1, S->B: 4
A->C: 3, A->D: 2
B->D: 2
C->G: 2
D->G: 4
Heuristic function h (estimated cost to G):
h(S)=5, h(A)=4, h(B)=4, h(C)=2, h(D)=2, h(G)=0
True optimal cost h* (verifiable via reverse Dijkstra):
Actual: S->A->D->G: 1+2+4=7; S->B->D->G: 4+2+4=10; S->A->C->G: 1+3+2=6
Shortest: S->A->C->G = 6, so h*(S)=6, h(S)=5 ≤ 6 ✓ admissible
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 ✓ (exactly precise)
h*(D)=4, h(D)=2 ≤ 4 ✓
h*(G)=0, h(G)=0 ✓
For every node, h(n) ≤ h*(n) holds, so h is admissible.追踪 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* 正确地跳过了次优路径。
现在,如果我们把
- 展开 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,5), (B,8)]
- 展开 C,G 的 f=6……最终仍然找到了最优解,但这只是因为图太小。
在更复杂的图上,高估会让 A* 过早判定某条路径"不值得探索"——而那条路径恰好是最优的。可采纳性不保证效率;可采纳性保证你不会错过最优解。丢掉它,最优解就可能从你手中溜走,而你甚至永远不知道。
仔细看第 3 步:展开 D 时,队列里有 C(f=6) 和 D(f=5)。A* 选了 D,因为 D 更乐观。乐观让 A* 愿意冒险,但也让它在看到更好的路径时能及时掉头——因为乐观只会向下修正,绝不会向上。如果
20.3 一致性:三角不等式的约束
可采纳性保证了最终结果的质量,但 A* 的效率取决于
定义(一致性):启发函数
其中
这是一个三角不等式:从
一致性蕴含可采纳性(你可以验证这一点),但反过来不成立。一致性是更强的条件。
在一致性下,A 展开的每个节点上
这两个性质——可采纳性和一致性——就是启发式合同的精确数学内容。有了它们,"启发式"就不再是随机猜测,而是在可证明界内工作的估计机制。
回到乐观制图师游戏:可采纳性要求制图师不能把近路说成远路;一致性要求制图师不能在相邻路口之间来回改口。A* 的聪明之处不是"相信直觉",而是只相信签过合同的直觉。没有合同,启发式只是一个油嘴滑舌的向导;有了合同,启发式才成为形式系统里的合法动作。
20.3.5 一致性被违反时:A* 的困惑
用 20.2.5 的同一个图,构造一个可采纳但不一致的
设
检查可采纳性:对每个节点,
✓, ✓。是的,可采纳。
检查一致性:对每条边
- 边 B->D:
, 。 吗?否。
发生了什么?从 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,经由 D 得到)。如果我们之后又发现另一条到 D 的更短路线(比如 S->B->D 代价更小?不——S->B->D 是 4+2=6,比 S->A->D 的 3 更差),而
在更大规模的搜索中,不一致的代价是巨大的:A* 可能需要重新展开节点,算法退化为接近 Dijkstra 的效率。一致性不是装饰——它是支撑 A* 效率的合同。
不一致的启发式就像一个反复无常的导游。他在 B 告诉你还剩 5 公里;你走到 D,他却说其实只剩 1 公里。加在一起,B->D 这一段他只算了 2 公里(5 -> 1),而实际距离也恰好是 2 公里——"刚好对上"。但如果到了 D,他突然又说还剩 4 公里(到下一个路口),你就会开始怀疑:他到底知不知道自己在说什么?A* 的怀疑是数学层面的:不一致时,
20.4 近似比:最坏情况的保证
当最优性作为一个目标讲得通时,A* 工作得很好。但对许多 NP 完全问题来说,即使允许近似,最优解本身也很难找到。这时就需要另一种合同:近似比。
定义(近似算法):对于一个最小化问题,如果算法
近似比是启发式合同的最坏情况版本:无论输入是什么,输出的质量都保持在最优解的
一些著名的结果:
- 顶点覆盖:存在 2-近似算法(找一个极大匹配,取两端点)。
- 旅行商问题(度量版本):存在 1.5-近似算法(Christofides 算法,1976 年)。这个结果保持了近半个世纪,直到 2020 年才被略微改进。
- 旅行商问题(一般版本,不满足三角不等式):若 P ≠ NP,则对任意常数
,都不存在多项式时间的 -近似算法。
最后一个结果是关键:对某些问题,近似本身就是 NP 难的。允许误差并不总是让问题变简单。近似比有自己的信息论下界,这个下界来自问题的内在结构,与任何具体算法无关。
一般 TSP 的不可能性证明用的是归约:如果存在一个多项式时间的
20.4.5 实操:顶点覆盖的 2-近似——极大匹配的力量
顶点覆盖问题:给定图
算法(极大匹配法):
- 找图的一个极大匹配
(无法再加入任何边的匹配) - 输出
中每条边的两个端点
为什么这是 2-近似?
设
- 下界:最优顶点覆盖至少需要
个顶点。因为 中的 条边互不共享端点(这正是匹配的定义),覆盖这 条边至少需要 个顶点——每条边至少要选一个端点,而不同边的端点不能共享。所以 。 - 上界:我们输出了
个顶点, 。✓
为什么极大(而不是最大)就够了? 一个简单的贪心构造极大匹配:遍历所有边;如果当前边的两个端点都还没有被匹配覆盖,就把这条边加入匹配。结果不一定是最大匹配(边数最多的匹配),但一定是极大的(无法再加入边)。对于 2-近似,极大就够了。
一个具体例子:
Graph: vertices {1,2,3,4,5}
Edges: (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),
注意这个算法之美:它并不试图"聪明地"挑选顶点。它依赖一个极其简单的事实——匹配的大小天然是 OPT 的下界。这个界不是算出来的,而是图的结构本身提供的。好的近似算法往往不是"聪明地逼近最优",而是"找到了一个必然接近最优的简单结构"。这与李雅普诺夫函数一脉相承——两者都是找到一个自然递减(或自然有界)的量。
20.5 PAC 学习:"差不多对"的概率版本
近似比关心的是解的质量;PAC 框架把同样的精神应用到学习问题上。
定义(PAC 学习):概念类
用大白话说:它以高概率(至少
很多人把"以高概率近似正确"读成降低标准。恰恰相反——
PAC 框架的核心结论:样本量
在 PAC 框架中,所需的样本量还取决于另一个量:假设空间
20.5.5 实操:VC 维的三道练习题
练习 1:实数轴上的区间。 设假设空间
2 个点:把它们放在
- (+,+):区间
✓ - (-,-):区间
(不覆盖任何点)✓ - (+,-):区间
✓ - (-,+):不可能。因为如果一个区间覆盖了右边的点(
),它必然也覆盖两者之间的任何点。要覆盖 而不覆盖 ?如果 ,任何包含 以及它和 之间所有点的区间都必须……等等——区间是连续的,但 和 是离散的点。区间 包含 ,但不包含 。所以 (-,+) 是可能的!区间 把 标为 -1,把 标为 +1。✓
4 种标注都能产生。所以 VC 维 ≥ 2。
3 个点:令
练习 2:平面上的线性分类器(过原点的直线)。
练习 3:神经网络与 VC 维之间的张力。 一个有
把三道练习并排放在一起,你看到了什么?VC 维不是什么模糊的"复杂度";它是一个你可以手算出来的具体数字。2、2(或 3)、数十亿——这些数字告诉你为什么有些假设类容易学,有些需要更多数据,有些让理论家困惑。可计算性是最好的清醒剂。
20.6 三种合同的统一
把本章的内容放在一起:
| 合同 | 承诺 | 条件 | 代价 |
|---|---|---|---|
| 可采纳性 + A* | 找到最优解 | 可能探索更大的空间 | |
| 近似比 | 解至多是最优的 | 最坏情况保证 | 放弃最优性 |
| PAC 学习 | 以高概率近似正确 | 足够的样本 | 允许失败概率 |
三种合同,三种不同的"足够好"——各有自己的代价结构和保证类型。它们的共同点在于:每一种都把"近似"从一种直觉变成了一个数学量。合同可以被违反,但违反是可检测的。这完全符合第 14 章形式系统的精神:精确定义允许精确批评。
启发式不是因为我们请不起精确推理而被迫接受的三流妥协。它是在计算约束下对推断质量的理性承诺——知道自己承诺什么,也知道承诺的边界在哪里。
20.7 合同签订之后:谁来写合同?
本章建立了一个令人安心的框架:只要签了合同,启发式的行为就有数学保证。但有一个我们一直回避的问题:合同是谁写的?
一个可采纳的启发式
回到第 15 章的语言:在形式系统中,公理必须从外部输入;系统不能自己选择公理。在启发式合同中,合同的条款(
这意味着:今天所有的"有保证的推理"都依赖一个外部承诺——你相信设计者所选的启发式是合理的,相信所选的假设空间是恰当的。但如果这个外部承诺本身就是错的呢?如果在某个场景中,你的启发式系统性地高估,而你不知道呢?
这个问题引出一个更深的问题:合同能否自动地从数据中写出来? 我们能否让系统观察自己的行为,从成功和失败中推断出合适的启发式?如果设计启发式本身就是一个推断问题——从问题实例的历史中推断出哪种估计策略在未来实例上有效——那么启发式设计就是元学习。
而元学习,正是第 21 章打开的那扇门:学习能否被理解为从数据中推断出最短描述?如果学习是逆推断,那么"学到一个好的启发式"这件事本身,能否被理解为一种逆推断?
这三个问题——谁写合同、合同能否自动写出、写合同本身算不算学习——把我们从"启发式的形式化"推向"学习的逆推断结构"。合同的形式化是本章的工作;合同从何而来是下一章的工作。最终的答案在第 21 章。
悬而未决
近似的边界能被打破吗? 对某些问题,近似比存在不可逾越的下界(假设 P ≠ NP)。但近似算法理论仍然有大量未解问题:旅行商问题的最优近似比是多少?唯一博弈猜想(Unique Games Conjecture)是否成立——它为大量问题钉下了近似下界。这个方向的问题往往比 P ≠ NP 本身更容易陈述,也同样深刻。
PAC 学习的计算版本:PAC 框架保证的是样本复杂度,而不是计算复杂度。有些概念类在样本意义上是可学习的,但学习算法本身可能需要指数时间。区分"信息论上可学习"和"计算上可学习",是学习理论的核心张力——前者问你需要多少数据,后者问你需要多少时间。
启发式能被自动发现吗? A* 需要手工设计的
思考题
★ 热身
在地图上的 A* 寻路中,直线距离常被用作启发式
(零启发式;A* 退化为 Dijkstra 算法) 从 到目标的直线(欧几里得)距离 从 到目标的直线距离 从 到目标的实际最短路径长度(假设你已经知道它) 从 到目标的曼哈顿距离(只允许上下左右移动时)
★★ 推导
可采纳性的代价:设计一个简单的搜索问题(画一个带边权的 5 节点图),使得可采纳的启发式
必须展开更多节点才能找到最优解,而不可采纳的 用更少的节点就找到了同一个解。给出两个 的具体数值,并追踪两种情况下的 A* 展开顺序。可采纳性保证什么,不保证什么? PAC vs. 贝叶斯:第 17 章的贝叶斯推断和本章的 PAC 学习都处理"从有限数据中泛化"。PAC 的保证对最坏情况分布成立;贝叶斯的保证依赖先验。哪种保证假设更少?在先验完全错误的情形下,哪个框架会先崩溃?
★★★ 挑战
一般旅行商问题(TSP,不满足三角不等式时)已被证明:若 P ≠ NP,则对任意常数
这个"不可近似性"的证明用的是归约:如果存在
这道练习的目标不是完整的证明;而是理解为什么允许误差并不总是让问题变简单——在某些情况下,近似和精确求解一样难。
