1、实验目的

复习经典谓词演算中的归结原理，掌握人工智能程序设计语言Prolog，理解通过搜索求解问题实现人工智能的思想。

2、实验原理

谓词演算中的消解法，

3、实验内容

设有3个传教士和3个野人同在河的左岸，他们都要到对岸去；河里只有一条船，他们都会划船，但每次渡船至多只能乘两人；如果在任何一边河岸上，野人的数量超过传教士，野人就要吃掉传教士，问怎样才能用船将3个传教士和3个野人从左岸都渡到右岸，又不会发生传教士被吃的事件呢？通过Prolog程序，给出乘船过河的动作序列。

4、实验步骤

（1）       设计该问题的状态。例如：((左岸牧师数，左岸野人数),(右岸牧师数，右岸野人数),船的位置)。

（2）       定义目标状态。这里是：((0,0),(3,3),1)

（3）       描述可能的动作。船上所能够载人的状态就是可能的操作。用谓词move/2表示。

（4）       判断合法状态

（5）       深度优先搜索

 

三个传教士和三个野人的示例程序如下：

move(1,0).

move(0,1).

move(0,2).

move(2,0).

move(1,1).

legal((X,Y,_)):-legal1(X),legal1(Y).

legal1((X,Y)):-X=:=0,Y>=0,!.

legal1((X,Y)):-Y=:=0,X>=0,!.

legal1((X,Y)):-X>=Y,X>=0,Y>=0.

update((X,Y,0),Move,Statu1):-

(A,B)=X,

(C,D)=Y,

(E,F)=Move,

C1 is C+E,

D1 is D+F,

A1 is A-E,

B1 is B-F,

Statu1=((A1,B1),(C1,D1),1).

update((X,Y,1),Move,Statu1):-

(A,B)=X,

(C,D)=Y,

(E,F)=Move,

C1 is C-E,

D1 is D-F,

A1 is A+E,

B1 is B+F,

Statu1=((A1,B1),(C1,D1),0).

connect(Statu,Statu1):-

move(X,Y),

update(Statu,(X,Y),Statu1),

legal(Statu1).

findroad(X,X,L,L):-write(L).

findroad(X,Y,L,L1):-

connect(X,Z),

not(member(Z,L)),

findroad(Z,Y,[Z|L],L1).

 

 

 

以下是prolog程序  只显示了有没有解决办法  没显示具体解决的路径

 

get_integer(L,H,X):-L>H,!,fail.
get_integer(L,H,L).
get_integer(L,H,X):-L1 is L+1,get_integer(L1,H,X).

append([],X,X).
append([A|X],Y,[A|Z]):-append(X,Y,Z).

member(A,[A|X]).
member(A,[B|X]):-member(A,X).

del_move:-
retract(move(X,Y)),
fail.
del_move.

del_stat:-
retract(inistatu(X)),
retract(desstatu(Y)),!.
del_stat.

insert_move(N):-
insert_move0(N),
insert_move1(N).

insert_move0(0). %野人或牧师有一方人数为0，则另一方的人数可以是0--N.
insert_move0(N):-
asserta(move(N,0)),
asserta(move(0,N)),
N1 is N-1,
insert_move0(N1).

insert_move1(N):-%人数都不为0时，则野人的人数不能多于牧师的人数，并且总人数不能多于N.
 
get_integer(1,N,X),
get_integer(X,N,Y),
X+Y=<N,
asserta(move(Y,X)),
fail.
insert_move1(_).

legal((X,Y,_)):- %X为左岸状态，Y为右岸状态。
   legal1(X), %分别判断两岸的状态是否合法。
legal1(Y).

legal1((X,Y)):-
X=:=0,Y>=0,!. %牧师人数为0，野人的人数大于0，合法。
legal1((X,Y)):-
Y=:=0,X>=0,!. %野人人数为0，牧师的人数大于0，合法。
legal1((X,Y)):-
X>=Y,X>=0,Y>=0. %牧师数大于或等于野人数，且都大于0，合法。

update((X,Y,0),Move,Statu1):- %船在左岸时
   (A,B)=X,
(C,D)=Y,
(E,F)=Move,
C1 is C+E,
D1 is D+F,
A1 is A-E,
B1 is B-F,
Statu1=((A1,B1),(C1,D1),1).

update((X,Y,1),Move,Statu1):- %船在右岸时
(A,B)=X,
(C,D)=Y,
(E,F)=Move,
C1 is C-E,
D1 is D-F,
A1 is A+E,
B1 is B+F,
Statu1=((A1,B1),(C1,D1),0).

connect(Statu,Statu1):-
move(X,Y),
update(Statu,(X,Y),Statu1),
legal(Statu1).

findroad(X,X,L,L).% 递归的边界条件。
findroad(X,Y,L,L1):-  % L为储存的路由表。
connect(X,Z),
not(member(Z,L)), % X所连接的节点Z不在已经储存的路由表中。
findroad(Z,Y,[Z|L],L1).

findroad([],X,X).
findroad(Moves,State,Crit):-
findroad(PrMoves,State,NextState),
        not(member(NextState,PrMoves)),
connect(NextState,Crit),
append(PrMoves,[NextState],Moves).

insert_statu(N1,N2):-
asserta(inistatu(((N1,N2),(0,0),0))),
asserta(desstatu(((0,0),(N1,N2),1))).

writelist([]).
writelist([X|L]):-
write(X),
nl,
writelist(L).

widesolve(N1,N2,M):-
del_move,
del_stat,
insert_move(M),
insert_statu1,(N1,N2),
inistatu(X),
desstatu(Y),
!,
findroad(L,X,Y),
writelist(L),
nl.