问题空间
Problem Space — 求解问题 = 在状态空间中找到从初始状态到目标状态的路径
问题存在是因为：我们知道测试（目标是什么）但不能直接产生满足测试的结构。四要素：初始状态 + 目标状态 + 移动算子 + 状态空间。关键洞见：同一问题在不同表示下难度差异巨大——表示变换是元级搜索。
问题空间（Problem Space）
定义
问题空间（Problem Space）是 Newell 与 Simon 对”问题”的形式化表示框架：
一个问题空间由以下部分构成：
- 初始状态（Initial State）：问题开始时的符号结构
- 目标状态（Goal State）：满足求解条件的符号结构（可能是一类状态）
- 移动算子（Move Operators / Operators）：将一个状态转变为另一个状态的操作集合
- 状态集合（State Space）：所有可能状态的空间——通常是无法枚举的天文数字
求解问题 = 在问题空间中找到从初始状态到目标状态的路径。
理论地位
问题空间概念解答了柏拉图在《美诺篇》中提出的古老悖论：如何寻找你不知道的东西？
“陈述一个问题，就是指称：(1) 符号结构类别的测试（解），以及 (2) 符号结构的生成器（候选解）。求解问题，就是用生成器产生满足测试的结构。” — Newell & Simon (1976)
关键洞察：一个问题存在，是因为我们知道测试但不能直接产生满足测试的结构。 知道测试（知道”目标是什么”）≠ 知道生成器（知道”如何到达目标”）。
结构特性
空间规模与搜索复杂性
问题空间的规模决定了求解的难度：
- 若算子每步产生 B 个后继状态，深度 D 的树有 B^D 个节点
- 大多数有趣问题的状态空间大于可穷举范围（国际象棋约 10^40 种合法局面）
表示决定难度
同一个问题在不同表示下难度差异巨大。
残缺棋盘问题：62 格棋盘能否被 31 个多米诺骨牌覆盖？
- 在”位置空间”中：需搜索天文数量的排列组合
- 在”颜色奇偶性空间”中：立即可推断不可能
“支配表示的定性结构律仍有待发现。“（Newell & Simon, 1976）
表示变换本身是一种元级搜索：在可能的表示空间中寻找能使对象级搜索最小化的表示。
问题空间的结构类型
| 类型 | 特点 | 示例 |
|---|---|---|
| 线性（无分支） | 每步只有一个合法后继 | 代数方程化简 |
| 树形 | 每步多个后继，无环 | 棋类游戏搜索 |
| 图形（有环） | 状态可重复访问 | 地图寻路 |
| 层级分解 | 子问题嵌套 | GPS 的子目标结构 |
与搜索策略的关系
问题空间是搜索发生的舞台，搜索策略是在空间中导航的方式：
- 手段-目的分析：在状态空间中，检测当前状态与目标的差距并选择减少差距的算子
- 最优先搜索：优先扩展最接近目标的状态
- Alpha-beta 剪枝：在博弈树（一种特殊问题空间）中剪去不影响最优解的分支
搜索的核心挑战：从问题空间中提取足够的结构信息，引导生成过程避开无用路径。
与当代 AI 的关联
问题空间框架在 LLM 时代以不同形式存在：
隐式问题空间：LLM 的生成过程可以理解为在隐式符号空间中的搜索——每个 token 是一步移动，概率分布是隐式的算子，训练目标是隐式的测试。但这个”搜索”是一步到位的（自回归），没有显式的回溯。
Chain-of-Thought：中间步骤可以理解为在问题空间中显式标记”当前位置”，使模型能利用空间结构信息。
Agent 规划：现代 agent 的规划步骤（编排器-工作者模式）是显式问题空间搜索的软件实现——将任务分解为子问题，并行或串行求解。
误差级联：在多步 agent 任务中，问题空间的路径依赖性使早期错误在后续步骤被放大——这是问题空间深度搜索的固有风险。
关联概念
- 启发式搜索 — 在问题空间中搜索的策略框架
- 手段-目的分析 — 问题空间中的核心导航技术
- 物理符号系统假说 — 问题空间存在的理论前提
- 误差级联 — 问题空间深度搜索的风险
- 编排器-工作者 — 问题空间分解在 agent 架构中的体现
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 - Newell, A., & Simon, H. A. (1972). Human Problem Solving. Prentice-Hall.