1

我正在为Prolog中的经典“狼、山羊和卷心菜”问题寻找更好的算法，计算效率更高。下面的算法基于 BFS 搜索可能的情况。

问题：_

“从前，一个农夫去市场买了一头狼、一只山羊和一棵卷心菜。在回家的路上，农夫来到河边租了一条船。但乘船过河，农夫只能携带他自己和他购买的一件物品：狼、山羊或卷心菜。

如果无人看管，狼会吃山羊，或者山羊会吃白菜。

农民面临的挑战是将自己和他的购买物带到河的远处，让每件购买的东西都完好无损。他是怎么做到的呢？”

这个问题的当前解决方案是这个：

writelist([H|T]):-
       write(H), writelist(T).

empty_stack([]).
stack(Top, Stack, [Top|Stack]).
member_stack(Element, Stack):-
       member(Element, Stack).


reverse_print_stack(S):-
               empty_stack(S).
reverse_print_stack(S):-
               stack(E, Rest, S),
               reverse_print_stack(Rest),
               write(E), nl.


unsafe(state(X,Y,Y,C)):-
       opp(X, Y).
unsafe(state(X,W,Y,Y)):-
       opp(X, Y).

move(state(X,X,G,C), state(Y,Y,G,C)):-
       opp(X,Y), not(unsafe(state(Y,Y,G,C))),
       writelist(['try farmer takes wolf ',Y,Y,G,C]),nl.

move(state(X,W,X,C), state(Y,W,Y,C)):-
       opp(X,Y), not(unsafe(state(Y,W,Y,C))),
       writelist(['try farmer takes goat ',Y,W,Y,C]),nl.

move(state(X,W,G,X), state(Y,W,G,Y)):-
       opp(X,Y), not(unsafe(state(Y,W,G,Y))),
       writelist(['try farmer takes cabbage ',Y,W,G,Y]),nl.

move(state(X,W,G,C), state(Y,W,G,C)):-
       opp(X,Y), not(unsafe(state(Y,W,G,C))),
       writelist(['try farmer takes self ',Y,W,G,C]),nl.

move(state(F,W,G,C), state(F,W,G,C)):-
       writelist([' BACKTRACK from: ',F,W,G,C]),nl,fail.

path(Goal, Goal, Been_stack):-
       nl, write('Solution Path is: '), nl,
       reverse_print_stack(Been_stack).


path(State, Goal, Been_stack):-
       move(State, Next_state),
       not(member_stack(Next_state, Been_stack)),
       stack(Next_state, Been_stack, New_been_stack),
       path(Next_state, Goal, New_been_stack),!.


opp(e,w).
opp(w,e).


go(Start, Goal):-
       empty_stack(Empty_been_stack),
       stack(Start, Empty_been_stack, Been_stack),
       path(Start, Goal, Been_stack).


test:-go(state(w,w,w,w), state(e,e,e,e)). ```
4

1 回答 1

0

这是一个清理/简化版本（恕我直言）。

总的来说，没有太多需要优化的地方。

这是标准的深度优先搜索通过状态空间的路径。

对于广度优先搜索，需要另一种方法。

可以尝试比线性扫描（即某种哈希表）更快地查找访问状态，但是对于长度为 8 的历史记录，这真的不值得。

% The state indicates the position of: Farmer, Wolf, Goat, Cabbage
% which is always one of east ('e') or west ('w').

unsafe(state(e,w,w,_)).  % Wolf and Goat are on the same border and the farmer ain't there
unsafe(state(w,e,e,_)).  % Wolf and Goat are on the same border and the farmer ain't there

unsafe(state(e,_,w,w)).  % Goat and Cabbage are on the same border and the farmer ain't there
unsafe(state(w,_,e,e)).  % Goat and Cabbage are on the same border and the farmer ain't there

opp(e,w).
opp(w,e).
       
% Valid next state generation

move(state(X,X,G,C), state(Y,Y,G,C)):-
   opp(X,Y), 
   \+ unsafe(state(Y,Y,G,C)),
   format("try farmer takes wolf ~q -> ~q\n",[state(X,X,G,C), state(Y,Y,G,C)]).

move(state(X,W,X,C), state(Y,W,Y,C)):-
   opp(X,Y),
   \+ unsafe(state(Y,W,Y,C)),
   format("try farmer takes goat ~q -> ~q\n",[state(X,W,X,C), state(Y,W,Y,C)]).

move(state(X,W,G,X), state(Y,W,G,Y)):-
   opp(X,Y),
   \+ unsafe(state(Y,W,G,Y)),   
   format("try farmer takes cabbage ~q -> ~q\n",[state(X,W,G,X), state(Y,W,G,Y)]).
   
move(state(X,W,G,C), state(Y,W,G,C)):-
   opp(X,Y),
   \+ unsafe(state(Y,W,G,C)),
   format("try farmer takes self ~q -> ~q\n",[state(X,W,G,C), state(Y,W,G,C)]).

not_yet_seen(State,History) :-                       % will fail if  member(State, History) 
   member(State, History),
   !,
   format("State ~q already seen\n",[State]),
   fail.

not_yet_seen(_,_).                                   % the replacement: success if \+ member(State, History)
   
path(State, State, History) :-                       % found a solution! (but maybe not the BEST solution)
   !,                                                % don't continue the search down this history
   reverse(History,RevHistory),
   maplist(term_to_atom,RevHistory,RevHistoryAtoms),
   atomic_list_concat(RevHistoryAtoms, '->', OutputAtom),
   length(History,L),
   format("A solution of length ~d: ~q\n",[L,OutputAtom]).

path(CurState, FinalState, History) :-
   move(CurState, NextState),                        % generate a safe next state
   not_yet_seen(NextState, History),                 % that hasn't been seen yet
   (true;(format("Backtracking from using ~q\n",[NextState]),fail)),
   path(NextState, FinalState, [NextState|History]). % add it to the visited states and recurse

go(StartState, FinalState) :- 
   path(StartState, FinalState, [StartState]). % 3rd arg is "history"

test :- 
   go(state(w,w,w,w),  % first everything is west 
      state(e,e,e,e)). % then everything is east

它找到了两个历史长度为 8 的解：

?- test.
try farmer takes goat state(w,w,w,w) -> state(e,w,e,w)
try farmer takes goat state(e,w,e,w) -> state(w,w,w,w)
State state(w,w,w,w) already seen
try farmer takes self state(e,w,e,w) -> state(w,w,e,w)
try farmer takes wolf state(w,w,e,w) -> state(e,e,e,w)
try farmer takes wolf state(e,e,e,w) -> state(w,w,e,w)
State state(w,w,e,w) already seen
try farmer takes goat state(e,e,e,w) -> state(w,e,w,w)
try farmer takes goat state(w,e,w,w) -> state(e,e,e,w)
State state(e,e,e,w) already seen
try farmer takes cabbage state(w,e,w,w) -> state(e,e,w,e)
try farmer takes wolf state(e,e,w,e) -> state(w,w,w,e)
try farmer takes wolf state(w,w,w,e) -> state(e,e,w,e)
State state(e,e,w,e) already seen
try farmer takes goat state(w,w,w,e) -> state(e,w,e,e)
try farmer takes goat state(e,w,e,e) -> state(w,w,w,e)
State state(w,w,w,e) already seen
try farmer takes cabbage state(e,w,e,e) -> state(w,w,e,w)
State state(w,w,e,w) already seen
Backtracking from using state(e,w,e,e)
Backtracking from using state(w,w,w,e)
try farmer takes cabbage state(e,e,w,e) -> state(w,e,w,w)
State state(w,e,w,w) already seen
try farmer takes self state(e,e,w,e) -> state(w,e,w,e)
try farmer takes goat state(w,e,w,e) -> state(e,e,e,e)
A solution of length 8: 'state(w,w,w,w)->state(e,w,e,w)->state(w,w,e,w)->state(e,e,e,w)->state(w,e,w,w)->state(e,e,w,e)->state(w,e,w,e)->state(e,e,e,e)'
true ;


Backtracking from using state(e,e,e,e)
try farmer takes self state(w,e,w,e) -> state(e,e,w,e)
State state(e,e,w,e) already seen
Backtracking from using state(w,e,w,e)
Backtracking from using state(e,e,w,e)
Backtracking from using state(w,e,w,w)
Backtracking from using state(e,e,e,w)
try farmer takes cabbage state(w,w,e,w) -> state(e,w,e,e)
try farmer takes goat state(e,w,e,e) -> state(w,w,w,e)
try farmer takes wolf state(w,w,w,e) -> state(e,e,w,e)
try farmer takes wolf state(e,e,w,e) -> state(w,w,w,e)
State state(w,w,w,e) already seen
try farmer takes cabbage state(e,e,w,e) -> state(w,e,w,w)
try farmer takes goat state(w,e,w,w) -> state(e,e,e,w)
try farmer takes wolf state(e,e,e,w) -> state(w,w,e,w)
State state(w,w,e,w) already seen
try farmer takes goat state(e,e,e,w) -> state(w,e,w,w)
State state(w,e,w,w) already seen
Backtracking from using state(e,e,e,w)
try farmer takes cabbage state(w,e,w,w) -> state(e,e,w,e)
State state(e,e,w,e) already seen
Backtracking from using state(w,e,w,w)
try farmer takes self state(e,e,w,e) -> state(w,e,w,e)
try farmer takes goat state(w,e,w,e) -> state(e,e,e,e)
A solution of length 8: 'state(w,w,w,w)->state(e,w,e,w)->state(w,w,e,w)->state(e,w,e,e)->state(w,w,w,e)->state(e,e,w,e)->state(w,e,w,e)->state(e,e,e,e)'
true ;


Backtracking from using state(e,e,e,e)
try farmer takes self state(w,e,w,e) -> state(e,e,w,e)
State state(e,e,w,e) already seen
Backtracking from using state(w,e,w,e)
Backtracking from using state(e,e,w,e)
try farmer takes goat state(w,w,w,e) -> state(e,w,e,e)
State state(e,w,e,e) already seen
Backtracking from using state(w,w,w,e)
try farmer takes cabbage state(e,w,e,e) -> state(w,w,e,w)
State state(w,w,e,w) already seen
Backtracking from using state(e,w,e,e)
try farmer takes self state(w,w,e,w) -> state(e,w,e,w)
State state(e,w,e,w) already seen
Backtracking from using state(w,w,e,w)
Backtracking from using state(e,w,e,w)
false.
于 2020-07-19T21:13:50.323 回答