跳至內容

通用解難器

維基百科，自由的百科全書

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