LINUX.ORG.RU

[Prolog] Фермер/Волк/Коза/Капуста (поиск решения методом оценочной функции [hill climbing])

 


0

0

Вот пример решения классическо проблемы фермера ( http://rdos.h1.ru/logic.htm ,внизу страницы)
на SWI-Prolog методом оценочной функции (hill climbing): 

**код** -->

main(Moves):-
	initial_state(State),
	hill_climb(100-State,[State],Moves),
	statistics.     

/* + Current State, + Opened States List, 
   - List of Moves from Current State to Final State,  */
hill_climb(0-state(right,right,right,right),_,[]).
%	final_state(State).         
hill_climb(_-state(B,W,G,C),History,[Move|Moves]):- 
	update_boat(B,B1),
	setof(Eval-state(B1,Wi,Gi,Ci)-MoveI,
	      (	  move(state(B,W,G,C),state(B1,Wi,Gi,Ci),MoveI),
		  legal(state(B1,Wi,Gi,Ci)),
		  val_state(state(B1,Wi,Gi,Ci),MoveI,Eval),
		  Eval<100),
	      NextMoves),
	member(Val-state(B1,W1,G1,C1)-Move,NextMoves),
%	legal(state(B1,W1,G1,C1)),
%	not_member(state(B1,W1,G1,C1),History),
	hill_climb(Val-state(B1,W1,G1,C1),[state(B1,W1,G1,C1)|History],Moves).


% +Item, +Items List
%not_member(X,[X|_]):-
%	!, fail.
%not_member(A,[_|Xs]):-
%	not_member(A,Xs).
%not_member(_,[]).



               /***** Wolf-Goat-Cabbage Problem *****/
% state( ? Boat Place, ? Wolf Place, ? Goat Place, ? Cabbage Place )
initial_state(state(left,left,left,left)).
%final_state(state(right,right,right,right)).

% +Current State, -Next State
move(state(Go,Go,G,C),state(Go1,Go1,G,C),wolf - Go1).
move(state(Go,W,Go,C),state(Go1,W,Go1,C),goat - Go1).
move(state(Go,W,G,Go),state(Go1,W,G,Go1),cabbage - Go1).
move(state(_,W,G,C),state(Go1,W,G,C),alone - Go1).

% + State
legal(state(F,X,X,_)):-
	F\=X,
	!,fail.
legal(state(F,_,X,X)):-
	F\=X,
	!,fail.
legal(_).

% +From, - To
update_boat(left,right):-!.
update_boat(right,left).

% +State, + Cargo-Boat Direction, - State Value
val_state(state(_,W,G,C),Cargo-Dir,Val):-
	state_char(W,Xw),
	state_char(G,Xg),
	state_char(C,Xc),
	move_chars(Cargo,Dir,Xw,Xg,Xc,Xmove),
	Val is (Xw+Xg+Xc)*Xmove,
	!.

state_char(left,1).
state_char(right,0).


move_chars(alone,left,Xw,_,Xc,abs(Xw-Xc)*100+1):-!.	    % <--
move_chars(goat,right,Xw,_,Xc,abs(Xw-Xc)*100+1):-!.         % -->
move_chars(goat,left,Xw,_,Xc,(1-abs(Xw-Xc))*100+1):-!.	    % <--
move_chars(wolf,right,_,Xg,Xc,(1-abs(Xg-Xc))*100+1):-!.	    % -->
move_chars(cabbage,right,Xw,Xg,_,(1-abs(Xg-Xw))*100+1):-!.  % -->
move_chars(_,_,_,_,_,101).	  %    ((wolf/cabbage <--)/(alone -->))

**код** <--

Моя задача решить этим методом аналогичную задачу с большим количеством животных,
методами поиска вглубь и вширь я ее уже решил.

Собственно, я не понимаю методику оценки в конце примера, там (функция move_chars) оцениваются
движения лодки с определенным пасажиром в определенном направлении, оцениваются бинарно 
(101 - хорошо, 1 - плохо), в зависимости от расположения остальных животных.

Вот например строка:

move_chars(alone,left,Xw,_,Xc,abs(Xw-Xc)*100+1):-!.	    % <--

Значит, что фермеру в пустой лодке выгодно ехать влево, если волк и капуста на разных
берегах (abs(Xw-Xc)), я совершенно не понимаю выгодности этого и других правил.

Вопрос:

Если кто-то понимает логику написания этих оценок, прошу мне ее подсказать!
Спасибо!

Откуда следует, что если волк надыбает капусты, к нему обязательно прицепится какая-нибудь коза

bugmaker ★★★★☆
()
Ответ на: комментарий от bugmaker

Да коза и к борову прицепится, лишь бы капусты было много

anonymous
()

>Вот например строка:

>move_chars(alone,left,Xw,_,Xc,abs(Xw-Xc)*100+1):-!. % <--

>Значит, что фермеру в пустой лодке выгодно ехать влево, если волк и капуста на разных берегах (abs(Xw-Xc)), я совершенно не понимаю выгодности этого и других правил.

>Вопрос:

>Если кто-то понимает логику написания этих оценок, прошу мне ее подсказать!

по моему тут перечисленны все не правильные ходы, а последнее правило делает все оставшиеся ходы валидными. т.е. должно быть так:

>Значит, что фермеру в пустой лодке НЕ выгодно ехать влево, если волк и капуста на разных берегах (abs(Xw-Xc))...

что в данном случае (move_chars(alone,left,Xw,_,Xc,abs(Xw-Xc)*100+1):-!.) означает, что либо волк остался с козой, либо коза с капустой => :-!. :)

anonymous
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.