ЛИСТИНГ 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(door_t 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. Порядок в данном случае (к счастью) оказался вполне приемле­мым. Но возможны и менее удачные варианты упорядочения. Согласно правилам этой игры, обезьяна вполне может также переходиться с места на место, не прикаса­ясь к ящику, или бесцельно передвигать ящик по комнате. Как показано в следую­щем разделе, при более тщательном исследовании обнаруживается, что в случае рас­сматриваемой программы порядок расположения предложений фактически имеет решающее значение.