Алгоритм поиска на Прологе

 Логический подход к задаче о фермере, волке, козе и капусте

Задача заключается в следующем:

Фермер (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(_).