Универсальный решатель задач

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

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

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

Литература

• Newell, A.; Shaw, J.C.; Simon, H.A. (1959). Report on a general problem-solving program. Proceedings of the International Conference on Information Processing. 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. Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp (англ.). — San Francisco, California: Morgan Kaufmann, 1992. — P. 109—149. — ISBN 1-55860-191-0.
• Noyes, James L. Artificial Intelligence with Common Lisp (неопр.). — Lexington: D. C. Heath, 1992. — С. 343—371. — ISBN 0-669-19473-5.