Seven Mental · 心智七篇
中 EN
← Knowledge Atlas · Concept

问题空间（Problem Space）

问题空间：初始状态+目标状态+移动算子的符号表示框架，表示决定难度，残缺棋盘问题的核心洞察
念
CONCEPT · PROBLEM SPACE · solving = path search · Newell & Simon 1976

Problem Space

Problem Space — solving a problem = finding a path from the initial state to the goal state in a state space

A problem exists because we know the test (what the goal is) but cannot directly produce a structure that passes it. Four elements: initial state + goal state + move operators + state space. Key insight: the same problem has wildly different difficulty under different representations — representation change is meta-level search.

Representation sets difficulty — the mutilated-chessboard problem
Position spaceAstronomical permutationsUnsolvable by brute force
Color-parity spaceOne-step deductionImmediately known impossible
Problem space in modern AI
Chain-of-Thought
Intermediate steps = explicit markers of the current position in problem space, letting the model exploit spatial structure
Agent planning
Orchestrator-workers = explicit problem-space decomposition — splitting the task into sub-problems solved in parallel or series
Error cascade
Problem-space path dependence: early errors are amplified downstream — the inherent risk of deep search
LLM implicit search
Autoregressive generation = single-step search in an implicit symbol space, no explicit backtracking
→ Heuristic Search · Means-Ends Analysis · Physical Symbol SystemNewell & Simon (1976)

问题空间（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 任务中，问题空间的路径依赖性使早期错误在后续步骤被放大——这是问题空间深度搜索的固有风险。

关联概念

References