Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
General Problem Solver (GPS) — компьютерная программа, созданная в 1957 году Гербертом А. Саймоном, Дж. К. Шоу и Алленом Ньюэллом (RAND Corporation), предназначенная для работы как универсальная машина решения проблем. В отличие от предыдущего проекта «Логический теоретик», GPS использует анализ «средств и целей».
General Problem Solver (GPS) is a computer program created in 1957 by Herbert A. Simon, J. C. Shaw, and Allen Newell (RAND Corporation) intended to work as a universal problem solver machine. In contrast to the former Logic Theorist project, the GPS works with means–ends analysis.
Обзор
Любая проблема, которую можно выразить в виде набора корректно сформированных формул (WFF) или клауз Хорна, и которая представляет собой ориентированный граф с одним или несколькими источниками (то есть гипотезами) и стоками (то есть желаемыми заключениями), в принципе, может быть решена с помощью GPS. Области применения GPS наглядно демонстрируют доказательства в пространствах задач предикатной логики и евклидовой геометрии. GPS была основана на теоретических работах Саймона и Ньюэлла по логическим машинам. GPS стала первой компьютерной программой, отделившей знания о проблемах (правила, представленные в виде входных данных) от стратегии их решения (универсальный решающий механизм). GPS была реализована на языке программирования третьего порядка IPL. Хотя GPS успешно решала простые задачи, такие как задача о башнях Ханоя, которые можно было достаточно формализовать, она не могла справиться с реальными проблемами, поскольку поиск легко терялся в комбинаторном взрыве. Иными словами, количество "путей" в инференциальном диграфе становилось вычислительно непосильным. (На практике даже прямой поиск в пространстве состояний, например, для задачи о башнях Ханоя, может оказаться вычислительно невыполнимым, хотя разумное сокращение пространства состояний возможно с помощью таких элементарных методов ИИ, как A* и IDA*). Пользователь определял объекты и операции, которые можно выполнять над ними, а GPS генерировала эвристики посредством анализа "средств-целей" для решения задач. Она фокусировалась на доступных операциях, определяя допустимые входные данные и генерируемые выходные данные, а затем создавала подцели для последовательного приближения к конечной цели. Парадигма GPS в конечном итоге эволюционировала в архитектуру Soar для искусственного интеллекта.
Any problem that can be expressed as a set of well formed formulas (WFFs) or Horn clauses, and that constitute a directed graph with one or more sources (that is, hypotheses) and sinks (that is, desired conclusions), can be solved, in principle, by GPS Proofs in the predicate logic and Euclidean geometry problem spaces are prime examples of the domain of applicability of GPS. It was based on Simon and Newell's theoretical work on logic machines. GPS was the first computer program that separated its knowledge of problems (rules represented as input data) from its strategy of how to solve problems (a generic solver engine). GPS was implemented in the third order programming language, IPL. While GPS solved simple problems such as the Towers of Hanoi that could be sufficiently formalized, it could not solve any real world problems because the search was easily lost in the combinatorial explosion. Put another way, the number of "walks" through the inferential digraph became computationally untenable. (In practice, even a straightforward state space search such as the Towers of Hanoi can become computationally infeasible, albeit judicious prunings of the state space can be achieved by such elementary AI techniques as A* and IDA*). The user defined objects and operations that could be done on the objects, and GPS generated heuristics by means–ends analysis in order to solve problems. It focused on the available operations, finding what inputs were acceptable and what outputs were generated. It then created subgoals to get closer and closer to the goal. The GPS paradigm eventually evolved into the Soar architecture for artificial intelligence.