Проблема мавпи

Ця задача відноситься до задач пошуку в просторі станів. Вона широко відома у штучному інтелекті й часто використовується для ілюстрації задач моделювання поведінки об'єктів. Уперше задача була запропонована Дж.Маккарти в 1963 році й звучить вона в такий спосіб.

Постановка задачі.

§ Біля дверей кімнати стоїть мавпа.

§ У середині цієї кімнати до стелі підвішений банан.

§ Мавпа голодна й хоче з'їсти банан, однак не може дотягтись до нього, перебуваючи на підлозі.

§ Біля вікна цієї ж кімнати на підлозі лежить ящик, яким мавпа може скористатись.

§ Мавпа може вживати наступні дії:

o ходити по підлозі,

o залазити на ящик,

o пересувати ящик (якщо вже перебуває біля нього),

o схопити банан, якщо стоїть на ящику під бананом.

Чи може мавпа добратись до банана?

У більш загальному випадку ця задача може вважатись як задача визначення поведінки самоврядного об'єкта, перед яким поставлено завдання й описана поточна ситуація
(керування роботом).

Задача "про мавпу і банани" була однією з перших, використаних у тестуваннях універсального вирішувача задач GPS (General Problem Solver).

Вказівки до рішення задачі.

Простір станів задачі можна описати структурою

state(ПоложенняМавпи_В_Кімнаті, % значення: двері,

вікно, середина

МавпаНаЯщикуАбо_Ні, % значення: ящик, підлога

ПоложенняЯщикаВ_Кімнаті, % значення: двері, вікно,

середина

МаєЧиНеМаєБанан)% значення: так, ні

Існує 4 типи ходів:

1) схопити банан - якщо мавпа на ящику в середині кімнати й не має банана;

2) залізти на ящик, якщо мавпа перебуває на підлозі, поруч із ящиком;

3) підсунути ящик з одного дозволеного місця на інше, якщо мавпа на підлозі поруч із ящиком;

4) перейти по підлозі з одного дозволеного місця на інше.

Початковий стан: state('двері','підлога','вікно','ні') - мавпа біля дверей на підлозі, ящик біля вікна, банана у мавпи нема.

Кінцевий стан: state(_,_,_,'так')– банан у мавпи.

Вихідний код програми «пошук вшир»:

?- width_search(state(door,floor,window,no),state(_,_,_,yes)).

%перші 4 можливі кроки: від дверей чи вікна в середину

% і навпаки
step(state(door,floor,C,D),state(middle,floor,C,D)).
step(state(middle,floor,C,D),state(window,floor,C,D)).
step(state(window,floor,C,D),state(middle,floor,C,D)).
step(state(middle,floor,C,D),state(door,floor,C,D)).

% якщо мавпа поряд із ящиком, то може залізти на нього
step(state(A,floor,A,no),state(A,box,A,no)).

% якщо мавпа на підлозі поряд із ящиком, то може його

% пересунути
step(state(door,floor,door,D),state(middle,floor,middle,D)).
step(state(middle,floor,middle,D),state(window,floor,window,D)).
step(state(window,floor,window,D),state(middle,floor,middle,D)).
step(state(middle,floor,middle,D),state(door,floor,door,D)).

%якщо мавпа в середині на ящику і ще не має банан, то може %його схопити
step(state(middle,box,middle,no),state(middle,box,middle,yes)).

% для виводу стану в словесній форміprint_station(state(A,B,C,D)):-write('мавпа стоїть'),
(A=door,write(' біля дверей '); A=middle,write('в середині кімнати'); A=window,write('біля вікна')),
(B=floor,write('на підлозі, ');B=box,write(' на ящику, ')),
(B=floor,(C=door,write('ящик стоїть біля дверей,'); C=middle,write('ящик стоїть в середині кімнати, '); C=window,write('ящик стоїть біля вікна, ')); B=box,(D=yes, write('вже взяла банан');D=no,write('ще не взяла банан')),nl.

%для виводу всього шляху
print_way([]).
print_way([A|Tail]) :- print_station(A),nl,print_way(Tail).

% перевірка, чи не входить стан у вже пройдений шлях, щоб %запобігти зацикленню
proverka(A,B,Way) :- step(A,B), not(member(B,[A|Way])).

% якщо результат отримано, то кінець пошуку і вивід відповіді

width( [[Result | Way ]|_], Result) :-

reverse([Result|Way], RWay),print_way(RWay).

% інакше відшукуємо всі стани, в які можна перейти з

% поточного, додаємо у список шляхів новий шлях вже з

% урахуванням нового стану і рекурсивно викликаємо пошук.
%Якщо щось не вийшло, то переходимо до розгляду наступного %шляху із списку.

%Предикат setof( X, P, L) породжує список L об'єктів X, що %задовольняють Р.

width([[Temp|Way]|B],Result):- setof([Next,Temp|Way],

proverka(Temp,Next,Way) , A),
append(B, A, Way1), !, width( Way1, Result);