5.12. Универсальная программа решения задач
GPS (General Problem Solver) - известная программа, предложенная Алэном Ньюэллом, Клиффом Шоу и Гербертом Саймоном в конце 50-х 
(одна из самых первых программ искусственного интеллекта) и способная решать однотипным способом такие непохожие задачи, как подсчет интеграла, логические головоломки, доказательство теорем методом исчисления предикатов, грамматический анализ фразы.
Задачи, предлагаемые программе GPS, всегда представляются в следующем виде: исходный объект, конечный объект, множество операторов. Операторы позволяют осуществлять преобразования над объектами и благодаря этому дают возможность постепенно достичь конечного объекта, который и является целью всей работы.
Отметим, что GPS сразу же оказывается в более благоприятном положении, чем студент, сидящий перед чистым листом бумаги, поскольку у студента обычно не бывает списка законных операций: он, наоборот, должен их подобрать сам, а иногда даже изобрести в процессе решения.
5.12.1. Общая стратегия GPS: разбиение на подзадачи
В соответствии с «методом редукции» программа GPS всегда разбивает поставленную задачу на более простые подзадачи. Чтобы осуществить разбиение адекватным образом, программа пользуется различиями, существующими между обрабатываемым объектом и объектом, который мы хотим получить. Различием между двумя объектами считается любое свойство, присутствующее в одном из них и отсутствующее полностью или частично в другом. GPS выбирает только те операции, которые могут уменьшить различия, отмеченные на данном этапе поиска. Таким образом, используемый в программе метод ориентирован на средства, позволяющие достичь цели (анализ «цели — средства»), и в этом отношении он близок к способам действий, которые применяет в тех же условиях человек.
Цели. GPS различает три главные цели:
(см. скан)
Таким образом, все задачи в исходный момент ориентированы на первую цель:
Методы. Для каждой из трех целей в программе предусмотрены специальные методы, которые задаются для всех них одновременно в следующем виде:
(см. скан)
Чтобы повысить эффективность, авторы GPS предлагают учесть относительную значимость возможных различий (под этим подразумевается то, насколько сложно уменьшить различия), хотя это и не является необходимым. Кроме того, они дают таблицу зависимостей, в которой указываются операторы, пригодные для уменьшения каждого типа различий (см. приводимые ниже примеры). В соответствии с описанными выше методами и в зависимости от характера исходного объекта и первой цели GPS подыскивает одну или несколько целей
В свою очередь благодаря действию подходящих операторов эти цели раскрываются до тех пор, пока не будет получен конечный объект и пока остаются не полностью раскрытые объекты.
Стратегия, которой мы воспользовались, может быть представлена в виде дерева, называемого «деревом поиска» (рис. 5.29).
Рис. 5.29. Дерево поиска программы GPS.
В каждый момент времени GPS выбирает на этом дереве среди еще не обработанных до конца вершин наиболее многообещающую, т. е. такую, в которой различия между обрабатываемым и конечным объектом минимальны.
