yrgh.txt

用Prolog求解传教士和野人问题 复习经典谓词演算中的归结原理

move(1,0).表示船上有一位牧师，没有野人。 
move(0,1). 
move(0,2). 
move(2,0). 
move(1,1). 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，合法。 ?- legal(((3,3),(0,0),1)). yes ?-
legal(((0,3),(3,0),1)). yes ?- 
legal(((2,3),(1,0),0)). no ?- legal(((3,3),(0,0),1)). yes ?-
legal(((0,3),(3,0),1)). yes ?- 
legal(((2,3),(1,0),0)). no 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). ?-
update(((3,3),(0,0),0),(1,1),X).
X = (2,2),(1,1),1 ; no ?-
update(((0,0),(3,3),0),(1,1),X).
X = (-1,-1),(4,4),1 ;
no ?-
update(((1,2),(2,3),1),(3,4),X).
X = (4,6),(-1,-1),0 ;
no 
connect(Statu,Statu1):-
move(X,Y),
update(Statu,(X,Y),Statu1),
legal(Statu1). ?- connect(((3,3),(0,0),0),X).
X = (2,2),(1,1),1 ; 一个野人与一个牧师过河 
X = (3,2),(0,1),1 ; 一个野人过河 
X = (3,1),(0,2),1 ; 两个野人过河
no 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(((0,0),(3,3),1),((3,3),(0,0),0),[((0,0),(3,3),1)],L).
L = [((3,3),(0,0),0),
((3,1),(0,2),1), 
((3,2),(0,1),0),
((3,0),(0,3),1),
((3,1),(0,2),0),
((1,1),(2,2),1),
((2,2),(1,1),0),
((0,2),(3,1),1),
((0,3),(3,0),0),
((0,1),(3,2),1),
((1,1),(2,2),0), 
((0,0),(3,3),1)]
yes 
findroad([],X,X). 
findroad(Moves,State,Crit):-
findroad(PrMoves,State,NextState),
not(member(NextState,PrMoves)),
connect(NextState,Crit),
append(PrMoves,[NextState],Moves).
?- findroad(L,((3,3),(0,0),0),((0,0),(3,3),1)).
L=[((3 , 3) ,(0 , 0) , 0), 
((2 , 2) , (1 , 1) , 1), 
((3 , 2) , (0 , 1) , 0),
((3 , 0) , (0 , 3) , 1), 
((3 , 1) , (0 , 2) , 0),
((1 , 1) , (2 , 2) , 1),
((2 , 2) , (1 , 1) , 0),
((0 , 2) , (3 , 1) , 1),
((0 , 3) , (3 , 0) , 0), 
((0 , 1) , (3 , 2) , 1),
((0 , 2) , (3 , 1) , 0)] 
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). 
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(_)
?- insert_move(3). 
yes 
?- move(X,Y). 
X = 2 Y = 1 ;
X = 1 Y = 1 ; 
X = 0 Y = 1 ; 
X = 1 Y = 0 ;
X = 0 Y = 2 ;
X = 2 Y = 0 ; 
X = 0 Y = 3 ; 
X = 3 Y = 0 ; 
no 
insert_statu(N):- asserta(inistatu(((N,N),(0,0),0))),
asserta(desstatu(((0,0),(N,N),1))). 
del_move:- retract(move(X,Y)),
fail.
del_move. del_stat:- retract(inistatu(X)), retract(desstatu(Y)),!. del_stat.
widesolve(N,M):- del_move,
del_stat, 
insert_move(M), 
insert_statu(N), 
inistatu(X), 
desstatu(Y), 
!, findroad(L,X,Y),writelist(L), nl.
deepsolve(N,M):- del_move,
del_stat, 
insert_move(M),
insert_statu(N),
inistatu(X), 
desstatu(Y), 
!,
findroad(Y,X,[Y],L),
writelist(L), nl. 
?- deepsolve(3,2). 三个牧师三个野人，船一次能装两个人 
(3 , 3) , (0 , 0) , 0 (3 , 1) , (0 , 2) , 1 (3 , 2) , (0 , 1) , 0 (3 , 0) , (0 , 3) , 1 (3 , 1) , (0 , 2) , 0 (1 , 1) , (2 , 2) , 1 (2 , 2) , (1 , 1) , 0 (0 , 2) , (3 , 1) , 1 (0 , 3) , (3 , 0) , 0 (0 , 1) , (3 , 2) , 1 (1 , 1) , (2 , 2) , 0 (0 , 0) , (3 , 3) , 1 yes
?- widesolve(3,2). (3 , 3) , (0 , 0) , 0 (2 , 2) , (1 , 1) , 1 (3 , 2) , (0 , 1) , 0 (3 , 0) , (0 , 3) , 1 (3 , 1) , (0 , 2) , 0 (1 , 1) , (2 , 2) , 1 (2 , 2) , (1 , 1) , 0 (0 , 2) , (3 , 1) , 1 (0 , 3) , (3 , 0) , 0 (0 , 1) , (3 , 2) , 1 (0 , 2) , (3 , 1) , 0 yes 
?- deepsolve(4,2). 此情况无解 
no ?- deepsolve(4,3). 必须扩大船的容量 (4 , 4) , (0 , 0) , 0 (4 , 2) , (0 , 2) , 1 (4 , 3) , (0 , 1) , 0 (4 , 1) , (0 , 3) , 1 (4 , 2) , (0 , 2) , 0 (4 , 0) , (0 , 4) , 1 (4 , 1) , (0 , 3) , 0 (1 , 1) , (3 , 3) , 1 (2 , 2) , (2 , 2) , 0 (0 , 1) , (4 , 3) , 1 (1 , 1) , (3 , 3) , 0 (0 , 0) , (4 , 4) , 1 yes 
?- widesolve(4,3). 可以看出使用广度搜索出来的答案一般比深度搜索的短 (4 , 4) , (0 , 0) , 0 (3 , 3) , (1 , 1) , 1 (4 , 3) , (0 , 1) , 0 (2 , 2) , (2 , 2) , 1 (3 , 3) , (1 , 1) , 0 (0 , 3) , (4 , 1) , 1 (0 , 4) , (4 , 0) , 0 (0 , 2) , (4 , 2) , 1 (0 , 3) , (4 , 1) , 0yes 
?- deepsolve(5,3). 五个野人与五个牧师，也可以使用可载三人的船过河 (5 , 5) , (0 , 0) , 0 (5 , 3) , (0 , 2) , 1 (5 , 4) , (0 , 1) , 0 (5 , 2) , (0 , 3) , 1 (5 , 3) , (0 , 2) , 0 (5 , 1) , (0 , 4) , 1 (5 , 2) , (0 , 3) , 0 (2 , 2) , (3 , 3) , 1 (3 , 3) , (2 , 2) , 0 (0 , 3) , (5 , 2) , 1 (0 , 4) , (5 , 1) , 0 (0 , 2) , (5 , 3) , 1 (2 , 2) , (3 , 3) , 0 (0 , 1) , (5 , 4) , 1 (1 , 1) , (4 , 4) , 0 (0 , 0) , (5 , 5) , 1
?- widesolve(5,3). 使用广度搜索找到最佳答案 (5 , 5) , (0 , 0) , 0 (4 , 4) , (1 , 1) , 1 (5 , 4) , (0 , 1) , 0 (5 , 1) , (0 , 4) , 1 (5 , 2) , (0 , 3) , 0 (2 , 2) , (3 , 3) , 1 (3 , 3) , (2 , 2) , 0 (0 , 3) , (5 , 2) , 1 (0 , 4) , (5 , 1) , 0 (0 , 2) , (5 , 3) , 1 (0 , 3) , (5 , 2) , 0 yes
?- deepsolve(6,3). 各六个人时就不能通过载三人的船过河 no ?- deepsolve(6,4). 必须扩大船的容量。 (6 , 6) , (0 , 0) , 0 (4 , 4) , (2 , 2) , 1 (5 , 5) , (1 , 1) , 0 (3 , 3) , (3 , 3) , 1 (4 , 4) , (2 , 2) , 0 (2 , 2) , (4 , 4) , 1 (3 , 3) , (3 , 3) , 0 (0 , 2) , (6 , 4) , 1 (0 , 3) , (6 , 3) , 0 (0 , 1) , (6 , 5) , 1 (2 , 2) , (4 , 4) , 0 (0 , 0) , (6 , 6) , 1 yes