5.12.2. Задача об обезьяне и бананах

Эта задача, предложенная Дж. Маккарти в 1963 г., формулируется следующим образом: обезьяна и ящик находятся в комнате, к потолку которой подвешена связка бананов. Обезьяна может перемещаться по комнате, переносить ящик и забираться на него. Достать бананы она сможет только в том случае, если она заберется на ящик, расположенный в точности под бананами. Как она решает эту задачу, которая взрослому человеку кажется тривиальной?

1. Внешние условия

(см. скан)

(см. скан)

2. Задание задачи

(см. скан)

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

с одной стороны, общие характеристики, остающиеся значимыми для семейства задач, а с другой — точные данные по интересующей нас задаче.

Комментарии и замечания. В программе предыдущая таблица задается практически в такой же форме, поскольку она легко воспринимается машиной. Значением одноместных предикатов — «Место» и «Содержимое» — являются соответственно место и содержимое указанных переменных. Часть задает относительную сложность таких действий, как изменение места обезьяны 5 и ящика С или, наконец, изменение содержимого руки обезьяны. В таблице, приведенной в части Е, крест соответствует тем операторам, которые заведомо могут быть эффективно использованы для уменьшения различий данного типа. Как уже было сказано, две последние части описания не являются необходимыми: они ускоряют поиск и сокращают запись.

Решение. Программа должна последовательно уменьшить различия между исходным объектом, который мы обозначим и конечным объектом, который мы обозначим действуя в том порядке, который был ей уже задан. Для этого она будет строить промежуточные цели и объекты, связанные друг с другом естественным образом отношениями преемственности в соответствии с «генеалогическим деревом», организованным так, как показано на рис. 5.30.

На этом рисунке номера целей соответствуют порядку их создания. Сначала мы отмечаём три различия между Цель, обладающая приоритетом, состоит в уменьшении различия поэтому вновь созданная цель-2 есть

Это различие может уменьшить только оператор 4 и, чтобы попытаться применить его к исходному объекту, создается новая цель: цель - Однако из-за того, что оба требуемых оператором 4 условия в настоящий момент не удовлетворены (ящик находится не на том месте — различие обезьяна находится не на том месте — различие достижение этой цели непосредственно невозможно. Поэтому программа вводит новую цель, благодаря которой исчезнет различие, считающееся наиболее важным (т. е. цель - которая в свою очередь порождает цель-5, как только будет найден подходящий оператор.

Данная цель тоже не может быть пока достигнута непосредственно, так как нужно еще уменьшить различие . К этому сводится роль целей 6 и 7, которые позволяют сделать

Рис. 5.30. (см. скан) Дерево поиска программы GPS для задачи об обезьяне и бананах.

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

Отсюда программа возвращается назад к списку целей, отметив при этом, что нам удалось уменьшить различие Теперь первая невыполненная цель — это цель-5, в соответствии с которой нужно поставить на место и тогда новая цель введет новый объект

Таким же образом возвращение к цели-3 порождает еще три подцели: цель-9, 10 и 11. В цели-11 различие уменьшается с помощью единственного уместного оператора , наконец, в цели-12 обезьяна достает себе бананы.

Ценность этого примера состоит в том, что, с его помощью можно подробно показать, как несложное обыденное рассуждение можно полностью разложить на последовательность элементарных действий.

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

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

(см. скан)

повторное появление в процессе поиска некоторой промежуточной цели. Запоминать ее в этом случае бесполезно, а следуя описанной ниже общей процедуре, циклов можно избежать.

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