Универсальный решатель задач ( англ. General Problem Solver , GPS ) — компьютерная программа , созданная в 1957 году Гербертом Саймоном , ( англ. ) и Алленом Ньюэллом , предназначенная для работы в качестве универсальной машины для решения задач, сформулированных на языке хорновских дизъюнктов . В качестве примеров использования приводились доказательства теорем евклидовой геометрии и логики предикатов , решение шахматных задач .

Программа основана на теоретической работе Саймона и Ньюэлла о логических машинах. Считается первой компьютерной программой, в которой предпринята стратегия разделения знаний о задачах (правила, которые подавались на вход программы) от стратегии решения задач (общий решающий движок). Решающий алгоритм был реализован на низкоуровневом языке программирования (англ.) ( .

Хотя GPS была способна решать простые задачи, как например головоломку о ханойских башнях , она не могла справиться со многими реальными задачами, поскольку поиск цепи решения приводил к комбинаторному взрыву числа промежуточных шагов.

Примечания

Литература

• Newell, A.; Shaw, J.C.; Simon, H.A. (1959). pp. 256–264.
• Newell, A. (1963). A guide to the general problem-solver program GPS-2-2. RAND Corporation, Santa Monica, California. Technical Report No. RM-3337-PR.
• Ernst, G.W. and Newell, A. (1969). GPS: a case study in generality and problem solving. Academic Press. (revised version of Ernst’s 1966 dissertation, Carnegie Institute of Technology.)
• Newell, A., and Simon, H. A. (1972) Human problem solving Englewood Cliffs, NJ: Prentice-Hall
• Norvig, Peter. (англ.) . — San Francisco , California : Morgan Kaufmann , 1992. — P. 109—149. — ISBN 1-55860-191-0 .
• Noyes, James L. (неопр.) . — Lexington : D. C. Heath, 1992. — С. 343—371. — ISBN 0-669-19473-5 .