Главная > Интеллектуальные системы > Системы искусственного интеллекта
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

5.12. Универсальная программа решения задач

GPS (General Problem Solver) - известная программа, предложенная Алэном Ньюэллом, Клиффом Шоу и Гербертом Саймоном в конце 50-х (одна из самых первых программ искусственного интеллекта) и способная решать однотипным способом такие непохожие задачи, как подсчет интеграла, логические головоломки, доказательство теорем методом исчисления предикатов, грамматический анализ фразы.

Задачи, предлагаемые программе GPS, всегда представляются в следующем виде: исходный объект, конечный объект, множество операторов. Операторы позволяют осуществлять преобразования над объектами и благодаря этому дают возможность постепенно достичь конечного объекта, который и является целью всей работы.

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

5.12.1. Общая стратегия GPS: разбиение на подзадачи

В соответствии с «методом редукции» программа GPS всегда разбивает поставленную задачу на более простые подзадачи. Чтобы осуществить разбиение адекватным образом, программа пользуется различиями, существующими между обрабатываемым объектом и объектом, который мы хотим получить. Различием между двумя объектами считается любое свойство, присутствующее в одном из них и отсутствующее полностью или частично в другом. GPS выбирает только те операции, которые могут уменьшить различия, отмеченные на данном этапе поиска. Таким образом, используемый в программе метод ориентирован на средства, позволяющие достичь цели (анализ «цели — средства»), и в этом отношении он близок к способам действий, которые применяет в тех же условиях человек.

Цели. GPS различает три главные цели:

(см. скан)

Таким образом, все задачи в исходный момент ориентированы на первую цель:

Методы. Для каждой из трех целей в программе предусмотрены специальные методы, которые задаются для всех них одновременно в следующем виде:

(см. скан)

Чтобы повысить эффективность, авторы GPS предлагают учесть относительную значимость возможных различий (под этим подразумевается то, насколько сложно уменьшить различия), хотя это и не является необходимым. Кроме того, они дают таблицу зависимостей, в которой указываются операторы, пригодные для уменьшения каждого типа различий (см. приводимые ниже примеры). В соответствии с описанными выше методами и в зависимости от характера исходного объекта и первой цели GPS подыскивает одну или несколько целей

В свою очередь благодаря действию подходящих операторов эти цели раскрываются до тех пор, пока не будет получен конечный объект и пока остаются не полностью раскрытые объекты.

Стратегия, которой мы воспользовались, может быть представлена в виде дерева, называемого «деревом поиска» (рис. 5.29).

Рис. 5.29. Дерево поиска программы GPS.

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

<< Предыдущий параграф Следующий параграф >>
Оглавление