如何用A星算法解决传教士与野人过河问题

求大神们指教，最好有代码有注释，小的看过A星算法的原理，但在Prolog不知从何入手。

问题是:三个传教士，三个野人，一条船可以载两个人，当一边岸上出现野人多于传教士时，传教士会被吃掉.

求大神们指教，不胜感激！

可以参考《AI Algorithms Data Structures and Idioms in Prolog, Lisp and.Java》第4章的算法。后面的习题3与这个问题类似，只不过教士多于野人的时候，野人会被转化。下面是我的程序，供参考：

adt.prolog代码:（有些部分不需要）

empty_stack([]).
member_stack(A,Stack):-
member(A,Stack).
stack(A,Old_Stack,[A|Old_Stack]).
add_list_to_stack(List,Old_Stack,New_Stack):-
append(List,Old_Stack,New_Stack).
reverse_print_stack([]).
reverse_print_stack([H|T]):-
reverse_print_stack(T),
write(H),nl.

empty_queue([]).
member_queue(A,Queue):-
member(A,Queue).
enqueue(A,[],[A]).
enqueue(A,[H|T0],[H|T1]):-
enqueue(A,T0,T1).
dequeue(A,[A|T],T).
add_list_to_queue(List,Old_Queue,New_Queue):-
append(Old_Queue,List,New_Queue).

empty_pq([]).
member_pq(A,Queue):-
member(A,Queue).
precedes(X,Y):-
X<Y.
insert_pq(A,[],[A]):-!.
insert_pq(A,[H|T],[A,H|T]):-
precedes(A,H),!.
insert_pq(A,[H|T],[H|Tnew]):-
insert_pq(A,T,Tnew).

dequeue_pq(A,[A|T],T).

insert_list_to_pq([],Q,Q).
insert_list_to_pq([H|T],Q,Qnew):-
insert_pq(H,Q,Qnew1),
insert_list_to_pq(T,Qnew1,Qnew).

empty_set([]).
member_set(A,Set):-
member(A,Set).
add_if_not_in_set(A,Set,Set):-
member(A,Set).
add_if_not_in_set(A,Set,[A|Set]):-!.
delete_if_in_set(_,[],[]).
delete_if_in_set(A,[A|T],T):-!.
delete_if_in_set(A,[H|T],[H|Tnew]):-
delete_if_in_set(A,T,Tnew),!.

union([],S,S).
union([H|T],S,Snew):-
add_if_not_in_set(H,S,Snew1),
union(T,Snew1,Snew),!.

subset([],_).
subset([H|T],S):-
member(H,S),
subset(T,S).
intersection([],_,[]).
intersection([H|T],S,[H|Tnew]):-
member(H,S),
intersection(T,S,Tnew),!.
intersection([_|T],S,Snew):-
intersection(T,S,Snew),!.
set_difference([],_,[]).
set_difference([H|T],S,Snew):-
member(H,S),
set_difference(T,S,Snew),!.
set_difference([H|T],S,[H|Tnew]):-
set_difference(T,S,Tnew),!.
equal_set(S1,S2):-
subset(S1,S2),
subset(S2,S1),!.

missionary_and_cannibal_multi.prolog代码:

:- [adt].

num(N):-
total_m(Tm),
n_list(Tm,L),
reverse(L,RL),!,
member(N,RL).

n_list(0,[0]):-!.
n_list(A,[A|T]):-
B is A-1,
n_list(B,T),!.

total_m(3).
total_c(N):-
total_m(N).

boat_can_take(2).

boat_takes(M,C):-
boat_can_take(P),
num(M),num(C),
S is M+C,
S > 0,
S =< P.

move(state(LeftM,LeftC,Side),state(NewLeftM,NewLeftC,NewSide)):-
%% Side: -1 -> boat on left bank; 1 -> boat on right bank
num(LeftM),num(LeftC),
boat_takes(NM,NC),
NewLeftM is LeftM + NM * Side,
NewLeftC is LeftC + NC * Side,
num(NewLeftM),num(NewLeftC),
NewSide is 0 - Side,
not(unsafe([NewLeftM,NewLeftC])).

write_list([]).
write_list([H|T]):-
write(H),tab(1),
write_list(T).


go(Start, Goal) :-
empty_queue(Empty_open_queue),
enqueue([Start, nil], Empty_open_queue, Open_queue),
empty_set(Closed_set),
path(Open_queue, Closed_set, Goal).
test:-
total_m(Tm),total_c(Tc),
go(state(Tm,Tc,-1),state(0,0,_)).


path(Open_queue, _, _) :-
empty_queue(Open_queue),
write('No solution found with these rules').
path(Open_queue, Closed_set, Goal) :-
dequeue([State, Parent], Open_queue,_),
State = Goal,
write('A Solution is Found!'),nl,
printsolution([State, Parent], Closed_set).
path(Open_queue, Closed_set, Goal) :-
dequeue([State, Parent], Open_queue,Rest_open_queue),
get_children(State, Rest_open_queue, Closed_set, Children),
add_list_to_queue(Children, Rest_open_queue, New_open_queue),
union([[State, Parent]], Closed_set, New_closed_set),
path(New_open_queue, New_closed_set, Goal), !.

get_children(State, Rest_open_queue, Closed_set, Children) :-
(bagof(Child, moves(State, Rest_open_queue, Closed_set, Child), Children);Children=[]),
write('CHILDREN<<'),write(Children),write('>>'),nl.

moves(State, Rest_open_queue, Closed_set, [Next, State]) :-
move(State, Next),
not(unsafe(Next)),
not(member_queue([Next,_], Rest_open_queue)),
not(member_set([Next,_], Closed_set)).

printsolution([State, nil], _) :-
write(State), nl.
printsolution([State, Parent], Closed_set) :-
member_set([Parent, Grandparent], Closed_set),
printsolution([Parent, Grandparent], Closed_set),
write(State), nl.

unsafe([Lm,Lc]):-
total_m(Tm),
total_c(Tc),
Rm is Tm-Lm,
Rc is Tc-Lc,
( tobe_converted(Lm,Lc);tobe_converted(Rm,Rc)),!.

tobe_converted(M,C):-
C>0,
M>C.


运行结果：
1 ?- test.
CHILDREN<<[[state(2,3,1),state(3,3,-1)],[state(2,2,1),state(3,3,-1)],[state(1,3,1),state(3,3,-1)]]>>
CHILDREN<<[]>>
CHILDREN<<[[state(2,3,-1),state(2,2,1)]]>>
CHILDREN<<[]>>
CHILDREN<<[[state(0,3,1),state(2,3,-1)]]>>
CHILDREN<<[[state(1,3,-1),state(0,3,1)]]>>
CHILDREN<<[[state(1,1,1),state(1,3,-1)]]>>
CHILDREN<<[[state(2,2,-1),state(1,1,1)]]>>
CHILDREN<<[[state(2,0,1),state(2,2,-1)]]>>
CHILDREN<<[[state(3,0,-1),state(2,0,1)]]>>
CHILDREN<<[[state(1,0,1),state(3,0,-1)]]>>
CHILDREN<<[[state(1,1,-1),state(1,0,1)],[state(2,0,-1),state(1,0,1)]]>>
CHILDREN<<[[state(0,0,1),state(1,1,-1)]]>>
CHILDREN<<[]>>
A Solution is Found!
state(3,3,-1)
state(2,2,1)
state(2,3,-1)
state(0,3,1)
state(1,3,-1)
state(1,1,1)
state(2,2,-1)
state(2,0,1)
state(3,0,-1)
state(1,0,1)
state(1,1,-1)
state(0,0,1)
true .