跳转到内容

通用解难器

维基百科，自由的百科全书

通用解难器（英语：General Problem Solver，简称 G.P.S.，又称一般性问题解决程式）是由赫伯特·亚历山大·西蒙、约翰·克里夫·肖（英语：John Clifford Shaw）和艾伦·纽厄尔三人于1957年编写的计算机程序，旨在作为解决通用问题的机器。任何可以表示为良式公式（WFFs）或霍恩子句，并构成一个以上源点（source，即公理）或汇点（sink，即期望结论）的有向图问题，原则上可以透过通用解难器来解决。谓词逻辑和欧几里德几何问题空间中的证明，是通用解难器适用领域的主要例子。通用解难器是基于西蒙和纽厄尔关于逻辑机器的理论工作，也是首先将问题知识（将规则表示为输入数据）与问题解决策略（通用求解器引擎）分离开来的计算机程序。通用解难器是以三阶编程语言“资讯处理语言”（IPL）来实现。

虽然通用解难器能够解决一些诸如河内塔等可被充分形式化的简单问题，但无法用来解决现实世界中的问题，这是因为搜索很容易在组合爆炸（英语：Combinatorial explosion）中丢失。换句话说，透过推断有向图的“走访”次数在计算上变得难以为继。（在实践中，即使像河内塔这样直截了当的状态空间搜索，在计算上也可能变得不可行，虽然透过像 A *和IDA *这样基础的人工智能技术，仍可以对状态空间进行明智的修剪）

用户定义的对象、可在对象执行的操作，以及通用解难器可透过均值-端点分析生成启发式算法来解决问题。它着重于可用的操作，找出哪些输入是可接受的，以及生成了哪些输出。然后会创建子目标，以便越来越靠近目标。

通用解难器范式后来演变为人工智能的Soar架构。


基本解决方案的规则

  1. 一个对象变换成另一种。
  2. 降低的两个对象之间的不同。
  3. 适用于操作者的一个对象。其中的关键要素需要透过通用解难器解决的问题是运营商差异表，指定哪些转换是可能的。

伪代码

  1. Goal 1: Transform L1 into LO
  2. Goal 2: Reduce difference between L1 and L0
  3. Goal 3: Apply R1 to L1
  4. Goal 4: Transform L1 into condition (R1)
  5. Produce L2: (-P => Q) *R
  6. Goal 5: Transform L2 into L0
  7. Goal 6: Reduce difference between left(L2) and left(L0)
  8. Goal 7: Apply R5 to left(L2)
  9. Goal 8: Transform left(L2) into condition(R5)
  10. Goal 9: Reduce difference between left(L2) and condition(R5)
  11. Rejected: No easier than Goal 6
  12. Goal 10: Apply R6 to left(L2)
  13. Goal 11: Transform left(L2) into condition(R5)
  14. Produce L3: (P \/ Q) *R
  15. Goal 12: Transform L3 into L0
  16. Goal 13: Reduce difference between left(L3) and left(L0)
  17. Goal 14: Apply R1 to left(L3)
  18. Goal 15: Transform left(L3) into condition(R1)
  19. Produce L4: (Q \/ P)*R
  20. Goal 16: Transform L4 into L0
  21. Identical, QED

外部链接

检索自“https://zh.wikipedia.org/w/index.php?title=通用解难器&oldid=70487997”