2. Проблема фермера
Ця задача зустрічається в збірниках по цікавій математики ще з XVIII століття, і формулюється так.
Фермеру треба через річку перевезти вовка, козу й капусту. У човні може поміститись лише фермер з вовком або козою, або капустою. Якщо залишити вовка з козою без фермера, то вовк з'їсть козу; якщо залишити козу з капустою, то коза з'їсть капусту. У присутності ж фермера коза не може з'їсти капусту, а вовк - козу. Фермер все-таки перевіз свій вантаж через річку.
Як він це зробив?
Для формального опису задачі використовується модель графа простору станів, що є базовою для розв'язку задач пошуку в просторі станів. Вершини графа відповідають станам моделюємої системи. Дуга між двома вершинами існує лише тоді, коли можливий перехід між станами. Стани описуються структурою state, а дуги переходів - предикатом move. Стан системи визначається місцезнаходженням фермера, вовка, кози й капусти:
state( Фермер, Вовк, Коза, Капуста ).
Рішення задачі полягає в пошуку шляху із заданого початкового стану в шукане кінцеве застосуванням послідовності правил переходів. Деякі із станів системи заборонені та визначаються предикатом unsafe.
Особливістю задачі є вимога однократного проходження довільного з дозволених станів у процесі пошуку рішення. Для контролю цієї вимоги пройдені стани накопичуються у списку Path і перевіряються предикатом path.
Наведену нижче програму вважають базовою для рішення задач методом пошуку на графах простору станів. Для даного випадку використовується чотиривимірний простір станів, об'єкти в якому описуються структурою
STATE(LOC,LOC,LOC,LOC).
Тип даних LOC визначає цифровий код осей координат простору і в даному випадку має два значення, відповідні лівому й правому берегам ріки.
Додаткові предикати мають наступні значення:
opposite - фіксує протилежність берегів та використається в правилі переходу між станами;
member - фіксує приналежність стана списку пройденого шляху;
go - визначає ціль для розділу goal.
Інші предикати використаються для відображення процесу рішення на екран монітора у чотирьох вікнах, визначених в розділі goal. Рішення формується по кроках, для виконання яких слід натиснути будь-яку клавішу. Нижче наведено текст програми LOGTASK1.PRO.
DOMAINS LOC = right ; left % Два береги - правий і лівий STATE=state(LOC,LOC,LOC,LOC) %Розташування об'єктів PATH = STATE* % Послідовність пройдених станів PREDICATES nondeterm go(STATE,STATE) %Початок рішення задачі nondeterm path(STATE,STATE,PATH,PATH) % Перехід
з одного стану в інший з модифікацією шляху
nondeterm move(STATE,STATE) % Переміщення об'єкта з
одного берега на інший opposite(LOC,LOC) % Положення на протилежних берегах nondeterm unsafe(STATE) % Неприпустимий стан nondeterm member(STATE,PATH) % Приналежність стана
пройденому шляху CLAUSES go(S,G):- path(S,G,[S],L), nl, write(" Послідовність перевезень :"),nl, write(L), nl, nl, fail. go(_,_).
path(S,G,L,L1) :- move(S,S1), not( unsafe(S1) ), not( member(S1,L) ), path( S1,G,[S1|L],L1),!. path(G,G,T,T):- !. % Шуканий стан досягнуто,
список L копіюється в L1
% Можливі варіанти перевезень об'єктів move(state(X,X,G,C),state(Y,Y,G,C)):-opposite(X,Y).
% Фермер з Вовком move(state(X,W,X,C),state(Y,W,Y,C)):-opposite(X,Y).
% Фермер з Козою move(state(X,W,G,X),state(Y,W,G,Y)):-opposite(X,Y).
% Фермер з Капустою move(state(X,W,G,C),state(Y,W,G,C)):-opposite(X,Y).
% Фермер наодинці % граф не орієнтований
opposite(right,left). opposite(left,right):-!.
% Заборонені стани системи об'єктів unsafe(state(F,X,X,_)):-opposite(F,X). % Вовк з'їдає Козу unsafe(state(F,_,X,X)):-opposite(F,X). %Коза з'їдає капусту
member(X,[X|_]). member(X,[_|L]):-member(X,L).
GOAL go(state(right,right,right,right),state(left,left,left,left)).
Рішення:
[state(left, left, left, left), 1
state(right, left, right, left), 2
state(left, left, right, left), 3
state(right, left, right, right), 4
state(left, left, left, right), 5
state(right, right, left, right), 6
state(left, right, left, right), 7
state(right, right, right, right)] 8
Рішення:
[state(left, left, left, left), 1
state(right, left, right, left), 2
state(left, left, right, left), 3
state(right, right, right, left), 9
state(left, right, left, left), 10
state(right, right, left, right), 6
state(left, right, left, right), 7
state(right, right, right, right)] 8
yes
Визначення розв'язку задачі на графі станів
1
2
3
4 9
5 10
6
7
8