维基百科

通用解难器

通用解难器（英語：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”