Вот пример решения классическо проблемы фермера ( 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)), я совершенно не понимаю выгодности этого и других правил.
Вопрос:
Если кто-то понимает логику написания этих оценок, прошу мне ее подсказать!
Спасибо!