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

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

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

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

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

 ход( S1, М, S2),

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

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

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

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

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

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

% Разрешенные ходы

ход( состояние( середина, на ящике, середина, неимеет),

 схватить,           % Схватить банан

 состояние( середина, наящике, середина, имеет)).

ход( состояние( P, наполу, P, H),

 залезть,            % Залезть на ящик

 состояние( P, наящике, P, H) ).

ход( состояние( P1, наполу, P1, H),

 подвинуть( P1, Р2), % Подвинуть ящик с P1 на Р2

 состояние( Р2, наполу, Р2, H) ).

ход( состояние( P1, наполу, В, H),

 перейти( P1, Р2),   % Перейти с P1 на Р2

 состояние( Р2, наполу, В, H) ).

% можетзавладеть(Состояние): обезьяна может завладеть

% бананом, находясь в состоянии Состояние

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

% может 1:  обезьяна уже его имеет

можетзавладеть( Состояние1) :-

 % может 2:  Сделать что-нибудь, чтобы завладеть им

 ход( Состояние1, Ход, Состояние2),

 % сделать что-нибудь

 можетзавладеть( Состояние2).

 % теперь может завладеть

Рис. 2.14.  Программа для задачи об обезьяне и банане.

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

Рис. 2.15.  Поиск банана обезьяной. Перебор начинается в верхнем узле и распространяется вниз, как показано. Альтернативные ходы перебираются слева направо. Возврат произошел только один раз.

2.6. Порядок предложений и целей

2.6.1. Опасность бесконечного цикла

Рассмотрим следующее предложение:

p :- p.

В нем говорится: "p истинно, если p истинно". С точки зрения декларативного смысла это совершенно корректно, однако в процедурном смысле оно бесполезно. Более того, для пролог-системы такое предложение может породить серьезную проблему. Рассмотрим вопрос:

?-  p.