启发式搜索
Heuristic Search — 生成-测试框架 · 搜索量 ≠ 智能量
问题的解被表示为符号结构，通过生成并递进修改符号结构直至产生满足条件的解。“启发式”意味着：不是穷举或随机，而是由信息引导的有选择性生成。已知测试条件不等于已知如何生成解。
启发式搜索（Heuristic Search）
定义
启发式搜索是物理符号系统求解问题的基本方式。Newell 与 Simon（1976）将其表述为第二条定性结构律：
“问题的解被表示为符号结构。物理符号系统通过搜索来行使其求解问题的智能——即通过生成并递进修改符号结构，直至产生满足条件的解结构。”
“启发式”（heuristic）意味着：搜索不是穷举或随机的，而是由信息引导的有选择性的生成过程。
为什么搜索是必要的
问题的本质：已知测试条件（什么算解）不等于已知如何直接生成满足条件的解。
- 已知”将死”不等于知道每局棋的最优走法
- 已知”方程成立”不等于能直接写出 X 的值
物理符号系统有限的计算资源（有限时间内只能执行有限操作）决定了它必须串行搜索——一次只能沿一条路径前进。
搜索的理论分析
问题形式化
一个问题包含：
- 生成器：产生候选符号结构的操作
- 测试：判断候选结构是否为解的条件
求解 = 使用生成器产生通过测试的结构。
暴力搜索的限制
设每节点产生 B 个分支，搜索深度为 D，则候选数为 B^D。
- B=10, D=10 → 100 亿候选
- 象棋约 B=35, D=40 → 天文数字
暴力搜索的根本瓶颈（Newell & Simon, 1976）：
“我们必须将通过蛮力搜索下好象棋的希望视为不那么有前景的——而这个希望在象棋首次被选为 AI 研究对象时曾被寄予厚望。“
搜索量不等于智能量
国际象棋大师的悖论：程序搜索数百万节点，大师往往不超过 100 个分支，但大师下得更好。
“搜索——连续生成候选解——是符号系统在问题求解中行使智能的根本方面，但搜索量不是智能量的度量。”
智能在于从问题空间中提取信息并引导搜索，避免无谓的分支。
弱方法与强方法
弱方法（Weak Methods）
在领域知识不足以避免搜索时，依赖通用启发式控制指数爆炸。
主要弱方法：
| 方法 | 描述 | 起源 |
|---|---|---|
| 最优先搜索（Best-First Search） | 从最接近目标的节点继续搜索 | 逻辑理论家（1955，隐含） |
| 手段-目的分析 | 检测差距，选择消弭差距的动作 | GPS（1957） |
| Alpha-beta 剪枝 | 剪去不影响最终评估的分支 | 象棋程序（约 1958） |
| 深度优先搜索 | 沿路径深入直至终点或回溯 | 多处同期发明 |
“弱”意味着：通用但不能从根本上避免指数增长，只能推迟或剪枝。
强方法（Strong Methods）
利用丰富的领域语义知识减少甚至避免搜索。
两种强方法途径：
语义识别系统：存储大量模式与对应动作。国际象棋大师据估算约存储 50,000 种棋盘模式，可直接识别局面特征并调用对应策略。
选择合适的表示：通过表示变换将高搜索量问题转化为可直接推断的问题。
残缺棋盘问题：62格棋盘能否用31个多米诺骨牌覆盖？
- 暴力：穷举所有排列
- 智能：注意对角格同色 → 残缺棋盘缺两格同色 → 每块骨牌覆盖一黑一白 → 不可能
合适的表示（颜色对称性）使得答案无需搜索即可得出。
不依赖（局部）搜索的三种途径
Newell & Simon 提出了超越局部搜索的三个方向：
1. 非局部信息使用
搜索过程中获取的信息通常只应用于局部节点。若能将信息传递到其他语境，可避免重复搜索。
HEARSAY 语音理解系统的”黑板”架构：多层次并行搜索共享一块公共黑板，任何层次产生的信息都可供其他层次使用，消除冗余搜索。
2. 语义丰富的识别系统
大量存储与问题空间结构紧密相关的特定模式知识。罕见但高度相关的模式可直接压缩搜索空间。
3. 表示变换
“支配表示的定性结构律仍有待发现。”
通过改变问题的表示方式，将需要搜索的问题转化为可直接推断的问题。这是一个开放的研究方向。
历史意义与当代关联
启发式搜索是 1950–1970 年代 AI 研究的核心。它解答了柏拉图”美诺悖论”——如何寻找未知：通过生成器-测试器框架，问题的未知性被转化为受控的搜索过程。
与 LLM 的对比：
- 经典启发式搜索：显式符号结构 + 形式化测试 + 明确搜索树
- LLM 的 Chain-of-Thought：隐式”搜索”嵌入自回归生成，中间步骤是非显式问题空间中的”移动”
- 系统 1 vs 系统 2 思维：LLM 的自动生成类比 System 1，显式搜索对应 System 2
关联概念
- 物理符号系统假说 — 启发式搜索存在的理论前提
- 问题空间 — 搜索发生的表示框架
- 手段-目的分析 — 最重要的弱方法之一
- 系统 1 vs 系统 2 思维 — 搜索在认知架构中的位置
- 层级系统 — Simon 的另一框架，与搜索互补
References
- Newell, A., & Simon, H. A. (1976). “Computer Science as Empirical Inquiry: Symbols and Search.” Communications of the ACM, 19(3), 113–126. 摘要:
sources/newell-simon-computer-science-empirical-inquiry-1975.md - Nilsson, N.J. (1971). Problem Solving Methods in Artificial Intelligence. McGraw-Hill.