1 历史背景
1.1 逻辑理论家（LT）的启发
通用问题求解器（GPS）的诞生直接源于其前身——逻辑理论家（Logic Theorist，简称LT）程序。LT由纽厄尔、西蒙和克利夫·肖（Cliff Shaw）于1956年共同开发，是第一个被公认的人工智能程序。LT能够自动证明《数学原理》（Principia Mathematica）中的逻辑定理，其方法是通过搜索可能的证明步骤，匹配前提与结论。LT的成功展示了计算机模拟人类推理的可能性，但纽厄尔和西蒙很快意识到：LT仅针对逻辑证明这一狭窄领域，而他们希望创造一个能解决“任何”问题的通用框架。LT中的“手段-目的”思想雏形——比较当前状态与目标状态的差异，并寻找减少差异的操作——成为GPS的核心基因。
1.2 纽厄尔与西蒙的研究路径
艾伦·纽厄尔（1927–1992）与赫伯特·西蒙（1916–2001）当时均在美国兰德公司（RAND Corporation）和卡内基理工学院（现卡内基·梅隆大学）工作。他们聚焦于人类问题解决的心理机制，认为思维本质上是对符号结构的操作。两人在1956年达特茅斯会议上介绍了LT，随后申请了美国空军的研究资助，专注于构建“一般性”的问题求解模型。西蒙还是一位经济学家与政治学家，他坚信“问题求解”是可形式化的，并提出了“有限理性”理论来支撑他关于人类认知资源有限的观点。两人的合作紧密，常同时出现在同一篇论文中，以至于学术界戏称“纽厄尔和西蒙”为一个复合名词。
1.3 开发时间线与版本迭代
GPS的开发跨越了1957年至1959年，期间经历了多个版本。第一个可运行的版本于1957年发布，能够解决简单的智力谜题如“汉诺塔”。1958年推出了优化版，增加了差异表和操作符选择机制。1959年的最终版本（GPS-59）在卡内基理工学院完成，其程序用IBM 704计算机的汇编语言实现，能够处理更复杂的逻辑证明和谜题。尽管GPS从未达到“通用”的承诺，但这些迭代证明了符号主义AI的可行性，也为后来的规划系统提供了架构灵感。
2 核心原理
2.1 手段-目的分析（MEA）
2.1.1 目标栈与差异表
手段-目的分析（Means-Ends Analysis，简称MEA）是GPS的核心策略。其基本思路是：任意时刻，系统维护一个“当前状态”与一个或多个“目标状态”。系统会计算两者之间的“差异”，并从一个预定义的“差异表”中查找能够减少这种差异的操作符。为了实现多层次的子目标，GPS使用一个目标栈来记录当前正在解决的目标以及被暂时搁置的父目标。当某个操作符无法直接应用于当前环境时，系统会生成一个子目标（例如“使条件X成立”），并将当前目标压入栈中，转而处理子目标。
2.1.2 操作符选择与子目标生成
每个操作符有前提条件和效果。在MEA中，系统首先找出当前状态与目标状态之间的差异类型（如“位置不同”“大小不同”）。然后遍历所有操作符，找出那些效果能够减少该差异的操作符。若某个操作符的前提条件不满足，系统会为“使前提成立”生成一个新的子目标，并递归应用MEA。这一过程可能会产生一系列嵌套的子目标，直到所有前提条件均为当前状态所满足。
2.2 问题空间表征
2.2.1 状态与操作符的定义
GPS基于问题空间（Problem Space）理论工作。一个“状态”是问题中所有相关变量的一个特定赋值（例如，在汉诺塔中，三个圆盘在三个柱上的位置构成一个状态）。一个“操作符”是将一个状态转变为另一个状态的规则（例如“移动最上面的圆盘从A到B”）。GPS要求所有状态和操作符必须被预先符号化地定义，且操作符只能是确定性的、有限数量的。
2.2.2 目标与当前状态的差异类型
差异表是MEA的关键组件。用户需要针对每个问题领域手动定义哪些差异是可识别的，以及哪些操作符可以消除每种差异。例如，在汉诺塔中，“大圆盘在小圆盘之上”是一个差异类型，对应的操作符可能是“移动上方的圆盘到另一个柱子”。GPS本身不学习新的差异类型，所有差异依赖于设计者的预编码。
2.3 控制结构
2.3.1 递归分解机制
GPS的控制结构本质上是一个递归函数。给定当前状态和目标状态，函数按以下步骤执行：
- 如果当前状态等于目标状态，成功并返回。
- 计算差异，选择操作符，若无法选择则失败。
- 若操作符的前提条件不成立，则递归地设置子目标为“使前提成立”，处理完毕后再回到步骤2。
- 应用操作符，更新当前状态，递归调用自身。
这种递归分解使得GPS能够处理多层次的复杂度，但也极易陷入无限递归——如果子目标得不到解决。
2.3.2 回溯与死胡同处理
当递归的某个分支无法找到可行操作符（即所有候选操作均导致相同或更糟的差异），GPS会回溯至上一个决策点，尝试另一个操作符。如果所有路径均失败，系统报告问题无解。由于GPS没有学习或启发式剪枝机制（除了预定义的差异表顺序），它很容易在复杂问题中陷入无休止的搜索。后来的版本引入了深度限制，但效果有限。
3 典型应用事例
3.1 逻辑证明（如罗素《数学原理》中的命题）
GPS继承了LT的逻辑证明能力。例如，它可以证明如“(p ∧ q) → p”之类的命题。GPS通过设定初始公理与推理规则（如“分离规则”）作为操作符，将待证命题作为目标状态。MEA会找出当前已知命题与目标之间的差异（如缺少某个子公式），并尝试应用合适的推理规则来减少差异。尽管GPS能完成LT能做的所有证明，但速度往往更慢，因为其通用策略未针对逻辑领域优化。
3.2 智力谜题（汉诺塔、传教士与食人魔）
汉诺塔是GPS最著名的演示案例。在汉诺塔中，状态由三个柱子上圆盘的位置表示，操作符是“将一个圆盘从柱X移到柱Y，前提是目标柱顶部圆盘大于要移动的圆盘”。差异表包括“圆盘顺序错误”“圆盘位置不对”等。GPS能求解3层或4层的汉诺塔。另一个经典例题是“传教士与食人魔”过河谜题（3个传教士、3个食人魔、一艘船需两人划）。GPS同样能用MEA找到解，但需要精心定义操作符（如“一个传教士和一个食人魔过河”），以避免陷入循环。
3.3 微积分符号积分
西蒙等人尝试将GPS用于微积分中的不定积分求解。他们将积分规则（如“分部积分”“换元积分”）定义为操作符，并设定“被积函数形式”为状态。MEA试图将待积函数与已知积分表中的标准形式匹配，差异表现为“缺少某个项”“幂次过高”等。然而，GPS只能处理非常简单的积分（如∫x dx, ∫sin x dx），一旦遇到需要复杂代数变换的积分（如∫e^x sin x dx），搜索空间就会急剧膨胀。这个应用更多地展示了GPS的局限性而非优势。
4 局限性分析
4.1 知识表示的贫乏
4.1.1 仅由操作符构成的封闭世界
GPS的知识完全由操作符及其前提条件和效果组成。它无法利用任何外部常识或领域背景。例如，在汉诺塔中，GPS不知道“圆形比方形更适合滚动”这样的事实——因为它根本不理解“形状”的概念。一切都被简化为符号重排，导致系统无法处理任何非形式化的知识。
4.1.2 缺乏常识与语义理解
由于GPS没有语义网络或本体，它无法理解操作符的真正含义。例如，在逻辑证明中，它不知道“蕴含”是一种逻辑关系，而只是将“→”视为一个无意义的符号，按照语法规则操作。这意味着GPS无法进行类比推理，也无法解释为什么某个步骤是合理的。
4.2 搜索空间爆炸
4.2.1 目标堆栈膨胀问题
MEA生成子目标的过程可能导致堆栈无限增长。例如，在汉诺塔中，为了移动一个大圆盘，可能需要先移动所有上方小圆盘，这又会要求进一步移动更小的圆盘。虽然人类可以直观地按层分解，但GPS会机械地为每个前提创建子目标，且可能反复生成相同的子目标（如“将小圆盘移到缓冲柱”），导致搜索空间呈指数增长。在实际测试中，5层汉诺塔就足以让当时的内存耗尽。
4.2.2 对“组合爆炸”的脆弱性
任何操作符数量大于10、状态数量大于100的问题都可能使GPS陷入组合爆炸。因为GPS没有启发式评估函数来引导搜索（除非差异表中预先包含了优先级），它只能盲目枚举可用的操作符。在微积分积分中，换元法的一个分支可能产生数十种可能的代数变换，每种又生成更多子目标。因此，GPS只在最简问题上有实用价值。
4.3 非通用性悖论
4.3.1 名称与实际的落差
“通用问题求解器”这个名称极具野心，但现实却讽刺：GPS几乎无法处理任何稍微复杂或开放的真实世界问题，如“如何修理漏水的水龙头”“如何规划一个会议日程”。这些日常问题涉及不确定、不完全信息以及常识推理，而GPS完全无法建模。纽厄尔和西蒙后来承认，“通用”是指其方法形式上的通用性，而非内容上的广泛适用。
4.3.2 为何被戏称为“特定问题求解器”
由于GPS只能解决预先定义好所有操作符和差异表的、玩具级的明确定义的问题，且其性能极度依赖于用户的设计质量，计算机科学家们很快开玩笑地将GPS称为“特定问题求解器”（Special Problem Solver）。这一绰号在AI圈内流传甚广，常被用来调侃早期AI的过度承诺。事实上，任何想要让GPS处理一个新领域的人，都必须手工构建整个问题空间和差异表——这与“通用”背道而驰。
5 影响与遗产
5.1 对认知科学的贡献
GPS是首个将人类问题解决的认知过程模型化为符号搜索的程序。西蒙和纽厄尔基于GPS发表了大量认知心理学论文，提出了“信息加工心理学”理论。他们用GPS模拟人类在解谜时的思维步骤，并通过对比人类的“有声思维”协议来验证模型。这一路径深刻影响了后来的认知架构如SOAR（State, Operator, And Result）。尽管GPS作为AI程序并不通用，但它作为认知模型，成功证明了有限规则可以产生复杂行为。
5.2 对AI规划系统（如STRIPS）的启发
1971年，斯坦福研究所的理查德·菲克斯（Richard Fikes）和尼尔·尼尔森（Nils Nilsson）开发了STRIPS（Stanford Research Institute Problem Solver），该系统直接继承了GPS的MEA思想和目标栈结构。STRIPS将其用于机器人规划，在简化的“积木世界”中控制机械臂。STRIPS的操作符引入了“添加表”和“删除表”，更清晰地表达了状态变化，其算法成为现代规划器的基石。可以说，GPS是STRIPS和几乎所有后续经典规划系统的理论祖父。
5.3 现代继承者：启发式搜索与智能规划
当代的自动规划系统（如PDDL规划器）很大程度上改进了GPS的弱点：它们使用启发式函数（如h值的放大）来剪枝搜索空间，并采用更强大的知识表示（如时态逻辑、概率推理）。GPS的“差异-操作符”思想也演化为“领域依赖启发式”和“抽象层次规划”。一些现代规划系统甚至直接继承了“目标栈”，只不过用更高效的算法（如双向搜索、图规划）替代了笨拙的递归。此外，GPS对“子目标交互”的早期认识——即一个子目标的解决可能破坏另一个子目标——直接催生了“约束规划”和“最小冲突”算法。
6 相关趣闻与梗文化
6.1 “通用”之名的营销段子
据说，命名GPS时，纽厄尔和西蒙半是野心半是幽默地决定用“General”一词，因为他们认为“如果叫‘特定问题求解器’，谁还会资助研究呢？”这个段子后来经常被引用，用于嘲讽AI领域内“标题党”传统。事实上，在1950年代末，“通用AI”的概念远比现在更受追捧，GPS不过是那个时代无数低成功率的PPT型项目之一。
6.2 西蒙关于“十年内电脑下棋赢人类”的预言反转
1958年，赫伯特·西蒙在接受采访时曾预言：“在十年内，一台数字计算机将成为国际象棋世界冠军。”这一预言基于他对GPS等程序的乐观评估。然而，直到1997年（近40年后），IBM的“深蓝”才击败卡斯帕罗夫。这段乌龙预言经常与GPS一起被提及，作为“AI预测不准”的经典案例。西蒙后来辩解说，他指的是“程序将能下赢大多数人”，而非绝对的世界冠军，但听众显然更喜欢夸张版本。
6.3 GPS在AI历史教材中的“万年背景板”地位
在几乎所有人工智能入门教材中，GPS都出现在“历史回顾”章节，篇幅通常不超过两页。它被描述为“早期的、有影响力的但失败的尝试”。在许多教学漫画中，GPS常作为“纸上谈兵”的象征：一个巨大的、优雅的框图，旁边写着“通用问题求解器”，下面用小字标注“实际只能解汉诺塔”。这种“万年背景板”的地位让GPS成为AI专业的文化符号，偶尔会出现在计算机学院学生自制的meme中，例如“GPS解决不了你的期末论文，但可以帮你规划如何移除书桌上的咖啡杯”。