📑 本页目录（点开跳转）
08 · 启发式怎么设计
⏱ 29 分钟 ｜ ⭐ 好的 h 不是猜出来的，是「把规则放松，然后精确地解那个简单问题」
🎯 一句话
把原问题的某个约束删掉，得到的「松弛问题」的精确解，天然就是原问题的可容许启发式。
上一章说清了 $h$ 要满足什么（可容许、最好一致），但没说 $h$ 从哪来。这一章给出一套能机械执行的造法——不靠灵感。
🔢 一、8-数码的两个启发式，手算一遍
规则：3×3 方格里 8 个数字块和一个空格，每次把空格和相邻的块交换，每步代价 1。
起始状态（左）和目标状态（右）：
| 7 | 2 | 4 | ⟶ | 1 | 2 | 3 |
| 5 | ⬜ | 6 | 4 | 5 | 6 | |
| 8 | 3 | 1 | 7 | 8 | ⬜ |
两个候选启发式：
- $h_1$ = 错位块数（不算空格）
- $h_2$ = 曼哈顿距离之和 = 每个块「横向距离 + 纵向距离」的总和
逐块算 $h_2$：
| 块 | 7 | 2 | 4 | 5 | 6 | 8 | 3 | 1 | |
|---|---|---|---|---|---|---|---|---|---|
| 到目标位的曼哈顿距离 | 2 | 0 | 3 | 1 | 0 | 1 | 3 | 4 | = 14 |
只有 2 和 6 已经在正确位置上，所以 $h_1 = 8 - 2 = \mathbf{6}$，而 $h_2 = \mathbf{14}$。
⭐ 同一个局面，一个说「至少还要 6 步」，一个说「至少还要 14 步」。真实答案是 20 步。 $h_2$ 明显更接近。
🪢 二、松弛问题：这两个 h 是从哪冒出来的
8-数码的真实规则里藏着两条约束：
- 块只能移到相邻的格子；
- 目标格子必须是空的。
把它们分别删掉，就得到两个更简单的问题——而这两个简单问题的精确解，正好就是 $h_1$ 和 $h_2$：
| 删掉哪条约束 | 放松后的问题 | 它的精确解 |
|---|---|---|
| 删掉 ① 和 ② | 块可以瞬移到任意格子 | 每个错位的块动一次就够 → $h_1$ |
| 只删掉 ② | 块可以移到任意相邻格（不管那格有没有人） | 每个块沿最短的格路走 → $h_2$ |
⭐⭐ 为什么这样造出来的 $h$ 一定可容许？ 因为原问题的每一个合法解，在松弛问题里也是合法解（规则更少 = 更宽松）。 所以松弛问题的最优代价 $\le$ 原问题的最优代价，永远不会高估。
这是一台造启发式的机器，不是一次灵机一动。 你只要盯着问题的约束列表， 一条一条问「删掉它之后还能精确求解吗」。
同一套逻辑在别的问题上：
| 问题 | 删掉的约束 | 得到的启发式 |
|---|---|---|
| 罗马尼亚地图 | 「只能沿公路走」 | 直线距离 $h_{SLD}$（上一章那个）⭐ |
| 旅行商问题 | 「每个城市只能进出各一次」 | 最小生成树的长度 |
| 魔方 | 「一次转动会同时动 8 个块」 | 3D 曼哈顿距离 ÷ 8 |
⚠️ 魔方那个「÷ 8」不是凑数：一次转动最多让 8 个小块各前进一步，所以不除会高估、破坏可容许性。放松得不够彻底就必须除回去。
🏆 三、支配性：h₂ 凭什么更好
支配（dominance）：若 $h_1, h_2$ 都可容许，且对所有节点 $h_2(n) \ge h_1(n)$，则称 $h_2$ 支配 $h_1$。
被支配的那个更差，因为它展开的节点更多。 道理很直接：A* 会展开所有 $f(n) < C^*$ 的节点，也就是所有满足 $h(n) < C^* - g(n)$ 的节点。$h$ 越大，满足这个条件的节点越少。
极端情形是 $h \equiv 0$——它可容许（永远不高估），但被所有启发式支配，A* 退化成一致代价搜索。
在上面那个 8-数码局面上实测（$h_2 \ge h_1$ 恒成立，因为「每个错位块至少要动一步」，曼哈顿距离一定不小于错位数）：
| 启发式 | 展开的节点数 | 解的长度 |
|---|---|---|
| $h \equiv 0$（= 一致代价） | 48,389 | 20 |
| $h_1$ 错位块数 | 3,666 | 20 |
| $h_2$ 曼哈顿距离 | 282 ⭐ | 20 |
三者的解都是 20 步（都最优），但展开量差了 170 倍。
讲义还给了一组更大的对照（$d$ 是最优解的深度）：
| 解的深度 | 迭代加深 IDS | A*($h_1$) | A*($h_2$) |
|---|---|---|---|
| $d = 14$ | 3,473,941 | 539 | 113 |
| $d = 24$ | 约 $54 \times 10^9$ | 39,135 | 1,641 |
💀 看 $d=24$ 那一行：无信息搜索要 540 亿个节点——跑不完。 换成 $h_1$ 是 3.9 万，换成 $h_2$ 是 1,641。 一个好的启发式不是「快一点」，是「能跑」和「跑不完」的区别。
➕ 四、有好几个启发式的时候：取 max
有 $h_1, \dots, h_m$ 都可容许，直接定义
$$h(n) = \max\big(h_1(n),\ \dots,\ h_m(n)\big)$$
- 仍然可容许——每个都不超过 $h^*$，最大的那个当然也不超过；
- 支配它们全体——按定义就是最大的。
⭐ 所以「选哪个启发式」这个问题，很多时候答案是「全都要」。 唯一的代价是每个节点要多算几次 $h$。
⚠️ 注意不能取和。 $h_1 + h_2$ 通常会高估——两个启发式可能在数同一批步数。
🗄️ 五、子问题与模式数据库
再往上一层：只解一部分。
比如 8-数码里只关心 1、2、3、4 这四个块回到位置需要多少步（其余块和空格视为可以随便动）。这个子问题的最优代价，一定不超过原问题的——因为原问题的解顺带也把这四块放回去了。所以它是可容许的。
而子问题小到可以穷举：把所有可能的「四块 + 空格」组合的最优步数预先算好存成表，搜索时查表就行。这张表就叫模式数据库（pattern database）。
⭐ Korf 1997 用这招算出了魔方的最优解：预存所有 8 个角块组合的最短步数，以及两组各 6 个棱块的表，搜索时三张表取 max。因为表很大，他配的是内存线性的 IDA*（上一章末尾那个）而不是 A*。
⭐ 模式数据库的本质：用离线的一次性穷举，换在线的每次搜索。 表算一次，用一辈子。 这个「预计算换查询」的思路，和数据库建索引、和推荐系统离线算召回是同一件事。
📉 六、有效分支因子（知道有这个数就行）
怎么量化「这个启发式有多好」？常用的一个数是有效分支因子：若 A* 一共展开了 $N$ 个节点、解在深度 $d$，就找一个 $b^*$ 使得分支因子恒为 $b^*$ 的均匀树，深度 $d$ 时正好有 $N$ 个节点。
$b^*$ 越接近 1 越好——1 意味着算法几乎直奔目标不走弯路。好的启发式在 8-数码上能把 $b^*$ 压到 1.2 附近，而无信息搜索大约是 2.8。
⚖️ 七、启发式不是免费的
⚠️ $h$ 算得越准通常也越贵。 曼哈顿距离要遍历 8 个块，模式数据库要查表（还要把表读进内存）。真实的取舍是：
$$\text{总时间} = \text{展开的节点数} \times \text{每个节点算 } h \text{ 的时间}$$
讲义提到魔方的角块启发式时就说了这个权衡：加上角块的 3D 曼哈顿距离「会拖慢计算，收益却不大」，所以实践中只用棱块那一项。
⭐ 判据只有一个：换上更强的 $h$ 之后，端到端的墙上时间变短了吗？ 节点数少了 10 倍但每个节点慢了 20 倍，是净亏。
🔗 这一章连到哪里
| 去哪 | 为什么 |
|---|---|
| 强化学习基础 03 · 价值函数与贝尔曼方程 | 这一章造 $h$ 全靠人手工松弛约束；那里的 $V(s)$ 回答同一个问题（「从这儿还要付多少」）但是学出来的。两条路的分工，就是这个板块和其余 13 个板块的分工 |
| 推荐算法 10 · 向量检索与ANN | 模式数据库「离线穷举换在线查表」的思路，在那里叫离线建索引。同一笔交易：用一次性的算，换每次请求的省 |
| AI基础设施 index | 第七节那个权衡——「节点少 10 倍但每个慢 20 倍是净亏」——是那个板块反复强调的同一条：只认端到端的墙上时间，别认单项指标 |
✅ 检查点
- 8-数码那个起始局面里，$h_1$（错位块数）和 $h_2$（曼哈顿距离）各是多少？真实的最优步数是多少？
- 松弛问题为什么一定给出可容许的启发式？
- 8-数码的两条约束是什么？分别删掉之后得到的是 $h_1$ 还是 $h_2$？
- 罗马尼亚地图的 $h_{SLD}$ 是删掉了哪条约束得到的？
- 魔方的 3D 曼哈顿距离为什么要除以 8？
- 什么叫支配？为什么被支配的启发式更差？$h \equiv 0$ 对应什么算法？
- 那个 8-数码局面上，$h\equiv 0$、$h_1$、$h_2$ 分别展开了多少节点？解的长度一样吗？
- $d=24$ 时 IDS 和 A*($h_2$) 的节点数各是多少？这个差别意味着什么？
- 有多个可容许启发式时该怎么合成？为什么不能相加？
- 什么是模式数据库？Korf 拿它做了什么？为什么配 IDA* 而不是 A*？
- 有效分支因子 $b^*$ 越大越好还是越小越好？
- 换上更强的启发式，判断划不划算的唯一标准是什么？
👀 答案
- $h_1 = 6$（8 个块里只有 2 和 6 在位），$h_2 = 2{+}0{+}3{+}1{+}0{+}1{+}3{+}4 = 14$。真实最优是 20 步——两个都没高估，$h_2$ 更接近。
- 因为原问题的每一个合法解，在松弛问题里也合法（规则更少 = 更宽松），所以松弛问题的最优代价 $\le$ 原问题的最优代价，永远不会高估。
- ① 块只能移到相邻格 ② 目标格必须是空的。两条都删 → 块能瞬移，每个错位块动一次 → $h_1$；只删 ② → 块能移到任意相邻格，每块沿最短格路走 → $h_2$。
- 删掉「只能沿公路走」。允许直线穿越，精确解就是直线距离。
- 因为一次转动最多让 8 个小块各前进一步。不除会高估，破坏可容许性——放松得不够彻底就必须除回去。
- 两个都可容许且 $h_2(n) \ge h_1(n)$ 对所有 $n$ 成立，则 $h_2$ 支配 $h_1$。被支配的更差是因为 A* 会展开所有 $h(n) < C^* - g(n)$ 的节点，$h$ 越大满足条件的越少。$h \equiv 0$ 被所有启发式支配，A* 退化成一致代价搜索。
- $h\equiv 0$：48,389；$h_1$：3,666；$h_2$：282。解的长度都是 20（都最优），只是展开量差了 170 倍。
- IDS 约 $54 \times 10^9$（540 亿），A*($h_2$) 是 1,641。意味着不是「快一点」，是「跑不完」和「能跑」的区别。
- 取 max：$h = \max(h_1, \dots, h_m)$，仍可容许（每个都不超 $h^*$）且支配它们全体。不能相加，因为两个启发式可能在数同一批步数，$h_1+h_2$ 通常会高估。
- 把一个子问题（比如只把 1、2、3、4 四块归位）的所有情形的最优步数离线穷举好存成表，搜索时查表。Korf 1997 用它算出魔方的最优解（8 个角块一张表、两组 6 棱块各一张，取 max）。配 IDA* 是因为表很占内存，A* 还要把所有节点留在内存里会撑不住，IDA* 的内存是线性的。
- 越小越好，越接近 1 越好——1 意味着几乎直奔目标。好启发式在 8-数码上约 1.2，无信息搜索约 2.8。
- 端到端的墙上时间。总时间 = 展开节点数 × 每节点算 $h$ 的时间；节点少 10 倍但每个慢 20 倍是净亏（讲义里魔方的角块启发式就是这种情况，所以实践中不用）。
🛑 可以停在这里
⚡ 走神救援
上一章说清了 $h$ 要可容许，这一章说 $h$ 从哪来——⭐⭐ 把原问题的某条约束删掉，那个「松弛问题」的精确解就是可容许启发式，因为原问题的每个合法解在松弛问题里也合法，代价只会更小、永远不会高估。这是一台机器，不是灵感。8-数码的两条约束是「只能移到相邻格」和「目标格必须空」：两条都删 → 块能瞬移 → $h_1$ 错位块数；只删第二条 → 块能移到任意相邻格 → $h_2$ 曼哈顿距离。手算那个局面：只有 2 和 6 在位，所以 $h_1 = \mathbf{6}$；逐块曼哈顿距离 2+0+3+1+0+1+3+4 = $\mathbf{14}$；真实最优是 20 步，两个都不高估、$h_2$ 更接近。同一套造法：罗马尼亚地图删掉「只能沿公路走」就得到直线距离；旅行商删掉「每城进出各一次」得到最小生成树；魔方是 3D 曼哈顿距离除以 8（一次转动最多让 8 个块各进一步，不除会高估）。⭐ 支配：两个都可容许且 $h_2 \ge h_1$ 处处成立，则 $h_2$ 支配 $h_1$、展开的节点更少（A* 展开所有 $h(n) < C^*-g(n)$ 的节点，$h$ 越大符合的越少）；$h \equiv 0$ 被所有启发式支配，A* 退化成一致代价搜索。实测那个局面：$h\equiv 0$ 展开 48,389 个，$h_1$ 展开 3,666 个，$h_2$ 只展开 282 个，解都是 20 步——差 170 倍。讲义的大例子更狠：$d{=}24$ 时 IDS 要约 540 亿个节点，A*($h_1$) 是 39,135，A*($h_2$) 只要 1,641——💀 好启发式不是「快一点」，是「跑不完」和「能跑」的区别。有多个启发式就取 max（仍可容许、支配全体），⚠️ 绝不能相加（会高估）。再往上是模式数据库：把一个子问题的所有情形离线穷举成表，在线查表；Korf 1997 用它算出魔方最优解，配的是内存线性的 IDA*。有效分支因子 $b^*$ 越接近 1 越好（8-数码上好启发式约 1.2，无信息约 2.8）。最后一条：⚖️ $h$ 不免费，判据只有端到端的墙上时间——节点少 10 倍但每个节点慢 20 倍是净亏。
下一节 👉 09-运动规划.md