通用问题求解器（GPS）

是什么

通用问题求解器（General Problem Solver，GPS）是一个旨在充当通用问题求解机器的程序^[1]。它被称作第一个把「关于问题的知识」（以输入规则的形式表示）与「求解策略」（一个通用的求解引擎）分开的计算机程序^[1]。这个区分正是它的要点：与其为每一个任务单独写一个程序，设计者想要的是一个引擎，只要把某个问题的对象和操作描述给它，它就能针对那个问题工作。

由来

GPS 由兰德公司（RAND Corporation）的赫伯特·西蒙（Herbert A. Simon）、J. C. Shaw 和艾伦·纽厄尔（Allen Newell）于 1957 年创建，而对该程序的一段简短介绍则把时间定在 1959 年^[1]。它建立在西蒙与纽厄尔关于逻辑机器的理论研究之上，用三阶编程语言 IPL 实现^[1]。这个程序脱胎于更早的逻辑理论家（Logic Theorist），后者为命题演算（sentential calculus）中的定理寻找证明^[2]。兰德公司的报告 P-1584 标注日期为 1958 年 12 月 30 日、1959 年 2 月 9 日修订，其中描述了一个名为 GPS-I（General Problem Solving Program I）的程序^[2]。兰德公司自己的文献目录把纽厄尔、Shaw 与西蒙的《Report on a General Problem-Solving Program》列为 1959 年 2 月的兰德论文 P-1584^[3]；关于该程序的参考文献中，还列有这三位作者 1959 年的一份报告^[1]。

从逻辑理论家到 GPS，是从单一任务走向通用性主张的一步。逻辑理论家证明定理；GPS 则希望被交给一个关于问题领域的描述，然后自己找到通往解答的路。

怎么工作

与更早的逻辑理论家不同，GPS 使用手段—目的分析（means-ends analysis）^[1]。它的思路是比较现在有什么和想要什么，找出两者之间的差异，再去找能缩小这个差异的操作；如果该操作暂时无法执行，它的前提条件就变成一个新的子目标。兰德公司的报告把手段—目的分析与规划列为当时构成该程序技术储备的两种通用问题求解技术^[2]。

使用者定义对象和操作，GPS 则生成启发式（heuristics），考察各个操作接受什么输入、产生什么输出，并建立子目标以逐步逼近总目标^[1]。报告把问题内容与求解技术的分离，列为提高程序通用性的一种办法^[2]。

GPS 能求解河内塔（Towers of Hanoi）之类可以被充分形式化的简单问题^[1]。这类谜题很适合它的设计：对象、合法操作和目标状态都能被精确写下来，求解器因此有确切的东西可以推理。

局限

它无法求解现实世界中的问题，因为搜索很容易陷入组合爆炸（combinatorial explosion）：在推理有向图上需要走过的路径数量变得在计算上无法承受^[1]。推理图每走一步都会分叉，缺少足够引导时，待考察路径的增长远远超出机器能跟上的程度。通用同时意味着引导很弱，而弱引导恰恰是大搜索空间最惩罚的东西。

在发展中的位置

GPS 这一范式后来演变为人工智能中的 Soar 架构^[1]。人们记住这个程序，与其说是因为它解出的那些谜题，不如说是因为它提出的架构：一边是某个领域的知识，另一边是通用的求解引擎，两者之间的分离为后来的工作提供了可以继续搭建的基础。