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

文档摘要

第20章：启发式的形式合同——"差不多对"的精确数学定义可采纳性不是一个工程妥协。它是一个数学承诺。第19章的结论令人沮丧：许多推理问题在计算上是根本困难的。不是算法不够好，而是问题本身的几何形状决定了没有捷径。但人类和机器一直在解决这些"困难"问题。不精确地，不总是最优地，但通常足够好，足够快。这里隐藏着一个问题："足够好"是什么意思？如果答案是任意的，那么任何算法只要不崩溃，都可以叫做"启发式"。但如果"足够好"有精确的数学含义，那么启发式就不是工程上的将就，而是一种有合同的承诺——承诺什么，以什么为代价，在什么条件下兑现。这章要做的事，就是把这个合同写清楚。 20.0 乐观地图师游戏：启发式必须签合同第19章告诉我们，很多迷宫太大，不能指望穷举。于是我们请来一位地图师。