State( Фермер, Вовк, Коза, Капуста )

Проблема фермера

Width(B, Result).

Ця задача зустрічається в збірниках по цікавій математики ще з XVIII століття, і формулюється так.

Фермеру треба через річку перевезти вовка, козу й капусту. У човні може поміститись лише фермер з вовком або козою, або капустою. Якщо залишити вовка з козою без фермера, то вовк з'їсть козу; якщо залишити козу з капустою, то коза з'їсть капусту. У присутності ж фермера коза не може з'їсти капусту, а вовк - козу. Фермер все-таки перевіз свій вантаж через річку.

Як він це зробив?

Для формального опису задачі використовується модель графа простору станів, що є базовою для розв'язку задач пошуку в просторі станів. Вершини графа відповідають станам моделюємої системи. Дуга між двома вершинами існує лише тоді, коли можливий перехід між станами. Стани описуються структурою state, а дуги переходів - предикатом move. Стан системи визначається місцезнаходженням фермера, вовка, кози й капусти:

Рішення задачі полягає в пошуку шляху із заданого початкового стану в шукане кінцеве застосуванням послідовності правил переходів. Деякі із станів системи заборонені та визначаються предикатом 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

Дата добавления: 2014-01-04