GPS：通用问题求解器
Newell 和 Simon 开发 GPS，首个尝试模拟人类问题求解过程的程序。
事件概述
1959年，Allen Newell 和 Herbert Simon 在 Carnegie Mellon 开发了通用问题求解器（General Problem Solver, GPS）。GPS 采用"手段-目的分析"(means-ends analysis) 方法，通过识别当前状态与目标状态的差异，选择能够缩小差异的操作来解决问题。GPS 能够解决逻辑定理证明、几何问题等多种任务，是早期 AI 追求"通用智能"的代表作。虽然 GPS 的能力范围有限，但其问题分解和启发式搜索的思想影响深远。
深度学习笔记
背景、原理、影响与要点，一次读懂这个事件
背景与脉络
1959 年，Newell、Shaw 与 Simon 在巴黎“信息处理国际会议”上提出 General Problem Solver（GPS）。它脱胎于 Logic Theorist，但目标更宏大：造一个不绑定特定领域的“通用”求解器。彼时自动推理多依赖穷举搜索，且问题知识与求解策略纠缠在同一份代码里——换个领域就得重写。三人想回答：能否把“通用的问题求解机制”与“领域知识”彻底分开？他们在 RAND 与卡内基理工学院用 JOHNNIAC 等机器实现，并宣称 GPS 既是一套软件，也是对“人如何解题”的计算理论。
核心要点
- 11959 年于巴黎会议提出，是 Logic Theorist 的通用化后继。
- 2核心创新：把“通用求解机制”与“领域知识”分离，换领域只换描述表。
- 3采用手段-目的分析：比较现状与目标，选能缩小最大差异的算子。
- 4用“差异表”记录哪类差异可由哪些算子消减，二者均手写、非学习所得。
- 5若算子前提不满足，则将前提设为子目标并递归求解（即递归）。
- 6在命题逻辑、三角恒等式、汉诺塔等玩具问题上成功，未解决真实大问题。
原理与技术细节
GPS 的引擎是“手段-目的分析”。给定当前状态与目标状态，它先算出二者之间最重要的差异，查一张手写的“差异表”找出能消减该差异的算子，然后尝试应用。若算子的前提未满足，这个未满足的前提就变成新子目标，GPS 对自己启动一个新实例去解它——如此递归，直到当前状态与目标再无差异。打个比方：想让 Sammy 到校，差异是“人不在校”，对应算子“开车送”，而开车前提是“车有电”；电池没电又成子目标，再找“叫修理工换电池”去消减。整个过程由一张“目标栈”管理层级子目标。其智慧全在两张手写表里：差异到算子的映射，以及差异的优先级排序——知识是给定的，不是学来的。
影响与后续
GPS 首个把“通用求解机制”与“领域知识”解耦，这一架构思想预示了后来的专家系统与知识工程。其手段-目的分析也成为认知科学对“人类解题”的标准计算模型（Newell 与 Simon 1972 年《人类解题》）。局限明显：无引导的搜索随解长指数膨胀，它只会解玩具问题，从未处理真实任务；所谓“通用”指机制通用而非能力通用。但它确立的“状态—差异—算子—递归子目标”框架，仍是现代规划器的雏形。
学习要点
- 把“机制”与“知识”分离，是让系统可复用、可扩展的关键架构原则。
- 从目标倒推、用子目标消解前提，是人类与机器共通的解题策略。
- “通用”要分清：是机制通用，还是能力通用——GPS 只是前者。
术语表
比较现状与目标之差异，选算子消减之，并以子目标递归满足前提的问题求解方法。
手写的“差异→可消减它的算子”映射，是 GPS 知识的主要载体。
Newell 与 Simon 的主张：符号操作是通用智能的必要且充分手段，GPS 是其验证。