Ogólne rozwiązanie problemów
The General Problem Solver (GPS) to program komputerowy stworzony w 1957 roku przez Herberta Simona , JC Shawa i Allena Newella w celu zbudowania maszyny zdolnej do rozwiązywania ogólnych problemów. Każdy formalny problem symboliczny można w zasadzie rozwiązać za pomocą GPS. Na przykład: dowodzenie twierdzeń , rozwiązywanie problemów geometrycznych, praca z logiką zdań i gra w szachy . Opierał się na wcześniejszych pracach teoretycznych Simona i Newella dotyczących maszyn logicznych . GPS był pierwszym programem komputerowym, w którym wiedza o problemach została oddzielona od strategii ich rozwiązywania. Został zaimplementowany w języku programowania IPL ( ang. Information Processing Language ) .
GPS zdołał rozwiązać proste problemy, takie jak problem z Wieżą Hanoi , który można było wyrazić w wystarczająco sformalizowany sposób, ale nie mógł rozwiązać problemów rzeczywistych.
Użytkownik zdefiniował obiekty i operacje, które można wykonać zi na obiektach, a GPS wygenerował heurystykę poprzez analizę środków i celów w celu rozwiązania problemów. W tym celu skoncentrował się na dostępnych operacjach, ustaleniu, jakie dane wejściowe były akceptowalne i jakie wyniki zostały wygenerowane. Następnie utworzono podcele, aby coraz bardziej zbliżać się do wcześniej zdefiniowanego celu.
Paradygmat GPS ewoluował w architekturę symboliczno-poznawczą SOAR ( ang. State Operator And Result ).
Proces
Simon i Newell proponują przykład przekształcenia zdania logicznego L1= R*(-P => Q) na L2=(Q \/ P)*R (Newell i Simon, 1972, s. 420). Ta transformacja zostałaby przetworzona przez GPS w następujący sposób:
- Cel 1: Przekształć L1 w L0
- Cel 2: Zmniejszenie różnicy między L1 i L0
- Cel 3: Zastosuj R1 do L1
- Cel 4: Przekształć L1 w stan (R1)
- Produkt L2: (-P => Q) *R
- Cel 5: Przekształć L2 w L0
- Cel 6: Zmniejsz różnicę między (L2) a (L0)
- Cel 7: Zastosuj R5 do (L2)
- Cel 8: Przekształć (L2) w stan (R5)
- Cel 9: Zmniejsz różnicę między (L2) i (R5)
- Odrzucony: Nie prostsze niż Cel 6
- Cel 10: Zastosuj R6 do (L2)
- Cel 11: Przekształć (L2) w stan (R5)
- Produkt L3: (P \/ Q) *R
- Cel 12: Przekształć L3 w L0
- Cel 13: Zmniejsz różnicę między (L3) a (L0)
- Cel 14: Zastosuj R1 do (L3)
- Cel 15: Przekształć (L3) w stan (R1)
- Produkt L4: (Q \/ P)*R
- Cel 16: Przekształć L4 w L0
- Zidentyfikuj, QED
Referencje
- Newell, A.; Shaw, JC; Simon, HA (1959). Raport dotyczący ogólnego programu rozwiązywania problemów. Materiały z Międzynarodowej Konferencji Przetwarzania Informacji . s. 256-264.
- A. Newell i HA Simon (1961). GPS, program symulujący ludzką myśl , w E. Feigenbaum i J. Feldmann, Hrsg. (1995) Komputery i myśl , ISBN 0262560925 .
- Newell, A. (1963). Przewodnik po ogólnym programie rozwiązywania problemów GPS-2-2 . RAND Corporation, Santa Monica, Kalifornia. Raport techniczny nr RM-3337-PR.
- Ernst, GW i Newell, A. (1969). GPS: studium przypadku w ogólności i rozwiązywaniu problemów . Prasa akademicka. (Zmieniona wersja rozprawy Ernsta z 1966 r., Carnegie Institute of Technology.)
- Newell, A. i Simon, HA (1972) Rozwiązywanie problemów z ludźmi . Englewood Cliffs, NJ: Prentice Hall.
- Norvig, Piotr. (1992). Paradygmaty programowania sztucznej inteligencji: studia przypadków w Common Lisp . s. 109-110.
