通用解难器
维基百科,自由的 encyclopedia
通用解难器(英语:General Problem Solver,简称 G.P.S.,又称一般性问题解决程式)是由赫伯特·亚历山大·西蒙、约翰·克里夫·肖(英语:John Clifford Shaw)和艾伦·纽厄尔三人于1957年编写的电脑程式,旨在作为解决通用问题的机器。任何可以表示为良式公式(WFFs)或霍恩子句,并构成一个以上源点(source,即公理)或汇点(sink,即期望结论)的有向图问题,原则上可以透过通用解难器来解决。谓词逻辑和欧几里德几何问题空间中的证明,是通用解难器适用领域的主要例子。通用解难器是基于西蒙和纽厄尔关于逻辑机器的理论工作,也是首先将问题知识(将规则表示为输入数据)与问题解决策略(通用求解器引擎)分离开来的电脑程式。通用解难器是以三阶编程语言“资讯处理语言”(IPL)来实现。
虽然通用解难器能够解决一些诸如河内塔等可被充分形式化的简单问题,但无法用来解决现实世界中的问题,这是因为搜索很容易在组合爆炸(英语:Combinatorial explosion)中丢失。换句话说,透过推断有向图的“走访”次数在计算上变得难以为继。(在实践中,即使像河内塔这样直截了当的状态空间搜索,在计算上也可能变得不可行,虽然透过像 A *和IDA *这样基础的人工智慧技术,仍可以对状态空间进行明智的修剪)
用户定义的对象、可在对象执行的操作,以及通用解难器可透过均值-端点分析生成启发式算法来解决问题。它著重于可用的操作,找出哪些输入是可接受的,以及生成了哪些输出。然后会创建子目标,以便越来越靠近目标。