ЛИСТИНГ 2.3. Программа решения задачи с обезьяной и бананом
%move( Statel, Move, State2) - выполнение действия Move в состоянии Statel % Обеспечивает переход в состояние State2; состояние представлено термом: % State{ MonkevHorizontal, MonkeyVertical,BoxPosition, KasBanana)
move! state) middle, onbox, middle, hasnot), % До выполнения действия
grasp, % Схватить банан
state) middle, onbox,middle, has) ) . % После выполнения действия
move ( statel P, onfloor, P, H) ,
clinb, % Забраться на ящик
statel. P, onbox, P, H) ) .
move [ state ( PI. onfloor, Pi, H},
push! Pi, P2) , % Передвинуть ящк из позиции Р1 в позицию Р2
state[ Р2, onfloor, P2, Н) ).
movet state С PI, onfloor, В, Hi,
walk! PI, P2), % Перейти из позиции Р1 в позицию Р2
state( P2, onfloor, В, И) ).
% canget) State) - обезьяна может получить банан в состоянии State
canget) state! _, _, _, has) ). k Предложение canl - обезьяна уже получила банан
canget) statel) :- % Предложение сап2 - обезьяна выполняет
Ч определенное действие, чтобы его получить
move( Statel, Move, State2), 4 Выполнить определенное действие
cangetf Etate2). % Теперь получить банан
Итак, программа решения задачи с обезьяной и бананом разработана непроцедурным способом. Теперь рассмотрим ее процедурное поведение на примере следующего вопроса к программе: ?- canget( state) atdoor, onfloor, atwindow, hasnot))-
Система Prolog на этот вопрос отвечает "yes" . Процесс, осуществляемый системой Prolog для достижения этого ответа, проходит, согласно процедурной семантике Prolog, через последовательность списков целей. Он предусматривает выполнение определенного поиска правильных шагов среди возможных альтернативных шагов. В некоторый момент времени этот поиск может привести к выбору неправильного действия, которое ведет к тупиковой ветви. На этом этапе возобновить работу программы поможет возврат к предыдущему этапу. Такой процесс поиска иллюстрируется на рис. 2.12 .
Глава 2. Синтаксис и значение программ Prolog
| с |
| 5) |
£tato( a(doort onflow, otwindow, hasno
walk(nldoo[,P2J
(state! P2, onfloor, atwlndow, hasnot) I
|
| posh{P2,P2'l P2 = atwindow |
| climb/ • возврат |
| 3) Q |
| $ |
| sloto{ P2', onfloor, P2', hasnot) |
state{ atwindow, onbox, atwlndow, hasnot)
)
Дальнейшие действия невозможны
climb
| t |
state! P2", onbox, P2', hasnot}
grasp
P2' = middle
| J> |
statet middle, onbox, middle, has)
Рис. 212 Поиск обезьяной способа получения банана. Поиск начинается с верхнего узла и проходит в направлении вниз, как показано на рисунке. По пытки выполнения альтернативных действий предпринимаются в последовательности слева направо. Возврат к предыдущему этапу выполняется только один раз
Для ответа на этот вопрос системе Prolog пришлось вернуться к предыдущему этапу только один раз. Правильная последовательность действий была найдена почти сразу же. Причиной такой высокой эффективности программы послужил правильный выбор порядка, в котором в программе представлены предложения, касающиеся отношения move. Порядок в данном случае (к счастью) оказался вполне приемлемым. Но возможны и менее удачные варианты упорядочения. Согласно правилам этой игры, обезьяна вполне может также переходиться с места на место, не прикасаясь к ящику, или бесцельно передвигать ящик по комнате. Как показано в следующем разделе, при более тщательном исследовании обнаруживается, что в случае рассматриваемой программы порядок расположения предложений фактически имеет решающее значение.