Логический подход к задаче о фермере, волке, козе и капусте
Задача заключается в следующем:
Фермер (Farmer), волк (Wolf), коза (Goat) и капуста (Cabbidge) находятся на одном берегу. Надо перебраться на другой берег на лодке. Лодка перевозит не более двоих. Нельзя оставлять на одном берегу козу и капусту, козу и волка.
Главная проблема в формировании алгоритма - найти эффективное представление структурой данных Пролога информации о задаче. | |||
Процесс перевозки может быть представлен последовательностью состояний. Состояние представляется отношением state c 4 аргументами, каждый из которых отражает размещение обьектов F, W, G, S:
Farmer | Wolf | Goat | Cabbidge |
· самого себя
· W
· G
· C
Предикат opposite определяет новое размещение объектов, которые пересекли реку.
/* (1) - FARMER + WOLF */ move(state(X,X,G,C),state(Y,Y,G,C)):-opposite(X,Y). /* (2) - FARMER + CABBIDGE */ move(state(X,W,G,X),state(Y,W,G,Y)):-opposite(X,Y). /* (3) - FARMER + GOAT */ move(state(X,W,X,C),state(Y,W,Y,C)):-opposite(X,Y). /* (4) - ONLY FARMER */ move(state(X,W,G,C),state(Y,W,G,C)):-opposite(X,Y). | ||
Теперь можно определить предикат opposite, который определяет другую сторону.
|
|
opposite(east,west).
opposite(west,east).
Предикат unsafe определен для проверки двух опасных состояний:
- F находится на противоположном берегу от W, G
- F находится на противоположном берегу от G, C.
unsafe(state(F,X,X,_)):- opposite(F,X). /* The wolf eats the goat */ | ||
unsafe(state(F,_,X,X)):- opposite(F,X). /* The goat eats the cabbage */ | |
path теперь определяется:
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):-!. /*The final state is reached */ | ||
Для решения можно использовать цель:
go:- go(state(east,east,east,east),state(west,west,west,west)). go(S,G):- path(S,G,[S],L), nl,write('A solution is:'),nl, write_path(L), fail. go(_,_). | ||
Для организации удобной формы вывода использованы следующие процедуры:
member(X,[X|_]). member(X,[_|L]):-member(X,L). write_move(state(X,W,G,C), state(Y,W,G,C)):-!, write('The farmer crosses the river from '), write(X), write(' to '), write(Y),nl. write_move(state(X,X,G,C), state(Y,Y,G,C)):-!, write('The farmer takes the Wolf from '), write(X), write(' of the river to '), write(Y),nl.write_move(state(X,W,G,X), state(Y,W,G,Y)):-!, write(' The farmer takes the cabbage from '), write(X), write(' of the river to '), write(Y),nl. write_move(state(X,W,X,C), state(Y,W,Y,C)):-!, write('The farmer takes the Goat from'), write(X), write(' of the river to '), write(Y),nl. write_path([H1,H2|T]):-!, write_move(H1,H2),write_path([H2|T]). write_path(_). | ||