Иван Братко - Программирование на языке Пролог для искусственного интеллекта
ход( состояние( P1, наполу, В, H),
перейти( P1, Р2), % Перейти из P1 в Р2
состояние( Р2, наполу, В, H) ).
Заметим, что в этом предложении делается много утверждений и, в частности:
• выполненный ход состоял в том, чтобы "перейти из некоторой позиции 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 изображен процесс перебора.
% Разрешенные ходы
ход( состояние( середина, на ящике, середина, неимеет),
схватить, % Схватить банан
состояние( середина, наящике, середина, имеет)).
ход( состояние( 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.
При использовании вышеприведенного предложения цель p будет заменена на ту же самую цель p; она в свою очередь будет заменена снова на p и т.д. В этом случае система войдет в бесконечный цикл, не замечая, что никакого продвижения в вычислениях не происходит.
Данный пример демонстрирует простой способ ввести пролог-систему в бесконечный цикл. Однако подобное зацикливание могло встретиться и в некоторых наших предыдущих программах, если бы мы изменили порядок предложений, или же порядок целей в них. Будет полезно рассмотреть несколько примеров.
В программе об обезьяне и банане предложения, касающиеся отношения ход, были упорядочены следующим образом: схватить, залезть, подвинуть, перейти (возможно, для полноты следует добавить еще "слезть"). В этих предложениях говорится, что можно схватить, можно залезть и т.д. В соответствии с процедурной семантикой Пролога порядок предложений указывает на то, что обезьяна предпочитает схватывание залезанию, залезание — передвиганию и т.д. Такой порядок предпочтений на самом деле помогает обезьяне решить задачу. Но что могло случиться. если бы этот порядок был другим? Предположим, что предложение с "перейти" оказалось бы первым. Процесс вычисления нашей исходной цели из предыдущего раздела
?- можетзавладеть( состояние( удвери, наполу, уокна, неимеет) ).
протекал бы на этот раз так. Первые четыре списка целей (с соответствующим образом переименованными переменными) остались бы такими же, как и раньше:
(1) можетзавладеть( состояние( удвери, наполу, уокна, неимеет) ).
Применение второго предложения из можетзавладеть ("может2") породило бы
(2) ход( состояние( удвери, наполу, уокна, неимеет), М', S2'),
можетзавладеть( S2')
С помощью хода перейти( уокна, Р2') получилось бы
(3) можетзавладеть( состояние( Р2', наполу, уокна, неимеет) )
Повторное использование предложения "может2" превратило бы список целей в
(4) ход( состояние(Р2', наполу, уокна, неимеет), М'', S2''),
можетзавладеть( S2'')
С этого момента начались бы отличия. Первым предложением, голова которого сопоставима с первой целью из этого списка, было бы теперь "перейти" (а не "залезть", как раньше). Конкретизация стала бы следующей:
S2'' = состояние( Р2'', наполу, уокна, неимеет).
Поэтому список целей стал бы таким:
(5) можетзавладеть( состояние( Р2'', наполу, уокна, неимеет) )
Применение предложения "может2" дало бы
(6) ход( cocтояниe( P2'', наполу, yoкнa, неимeeт), M''', S2'''),
можетзавладеть( S2''')
Снова первый было бы попробовано "перейти" и получилось бы
(7) можетзавладеть( состояние( Р2''', наполу, уокна, неимеет) )
Сравним теперь цели (3), (5) и (7). Они похожи и отличаются лишь одной переменной, которая по очереди имела имена Р', Р'' и P'''. Как мы знаем, успешность цели не зависит от конкретных имен переменных в ней. Это означает, что, начиная со списка целей (3), процесс вычислений никуда не продвинулся. Фактически мы замечаем, что по очереди многократно используются одни и те же два предложения: "может2" и "перейти". Обезьяна перемещается, даже не пытаясь воспользоваться ящиком. Поскольку продвижения нет, такая ситуация продолжалась бы (теоретически) бесконечно: пролог-система не сумела бы осознать, что работать в этой направлении нет смысла.
