Программирование на языке Пролог для искусственного интеллекта | страница 37

• выполненный ход состоял в том, чтобы "перейти из некоторой позиции P1 в некоторую позицию Р2";

• обезьяна находится на полу, как до, так и после хода;

• ящик находится в некоторой точке В, которая осталась неизменной после хода;

• состояние "имеет банан" остается неизменным после хода.

Рис. 2.13. Рекурсивная формулировка отношения >можетзавладеть.

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

Два других типа ходов: "подвинуть" и "залезть" — легко определить аналогичным способом.

Главный вопрос, на который должна ответить наша программа, это вопрос: "Может ли обезьяна, находясь в некотором начальном состоянии S, завладеть бананом?" Его можно сформулировать в виде предиката

>можетзавладеть( S)

где аргумент S — состояние обезьяньего мира. Программа для >можетзавладеть может основываться на двух наблюдениях:

(1) Для любого состояния S, в которой обезьяна уже имеет банан, предикат >можетзавладеть должен, конечно, быть истинным; в этом случае никаких ходов не требуется. Вот соответствующий прологовский факт:

>можетзавладеть( состояние( _, _, _, имеет) ).

(2) В остальных случаях требуется один или более ходов. Обезьяна может завладеть бананом в любом состоянии S1, если для него существует ход из состояния P1 в некоторое состояние S2, такое, что, попав в него, обезьяна уже сможет завладеть бананом (за нуль или более ходов). Этот принцип показан на рис. 2.13. Прологовская формула, соответствующая этому правилу, такова:

>можетзавладеть( S1) :-

> ход( S1, М, S2),

> можетзавладеть( S2).

Теперь мы полностью завершили нашу программу, показанную на рис. 2.14.

Формулировка >можетзавладеть рекурсивна и совершенно аналогична формулировке отношения >предок из гл. 1 (ср. рис. 2.13 и 1.7). Этот принцип используется в Прологе повсеместно.

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

>?- можетзавладеть( состояние( удвери, наполу, уокна, неимеет) ).

Ответом пролог-системы будет "да". Процесс, выполняемый ею при этом, обрабатывает, в соответствии с процедурной семантикой Пролога, последовательность списков целей. Для этого требуется некоторый перебор ходов, для отыскания верного из нескольких альтернативных. В некоторых точках при таком переборе будет сделан неверный ход, ведущий в тупиковую ветвь процесса вычислений. На этом этапе автоматический возврат позволит исправить положение. На рис. 2.15 изображен процесс перебора.