用Prolog求解传教士和野人问题

用Prolog求解传教士和野人问题实验七用Prolog求解传教士和野人问题1、实验目的复习经典谓词演算中的归结原理，掌握人工智能程序设计语言Prolog，理解通过搜索求解问题实现人工智能的思想。2、实验原理谓词演算中的消解法，3、实验内容设有3个传教士和3个野人同在河的左岸，他们都要到对岸去;河里只有一条船，他们都会划船，但每次渡船至多只能乘两人;如果在任何一边河岸上，野人的数量超过传教士，野人就要吃掉传教士，问怎样才能用船将3个传教士和3个野人从左岸都渡到右岸，又不会发生传教士被吃的事件呢,通过Prolog程序，给出乘船过河的动作序列。4、实验步骤(1)设计该问题的状态。例如:((左岸牧师数，左岸野人数),(右岸牧师数，右岸野人数),船的位置)。(2)定义目标状态。这里是:((0,0),(3,3),1)3)描述可能的动作。船上所能够载人的状态就是可能的操作。用谓词(move表示。(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,C1isC+E,D1isD+F,A1isA-E,B1isB-F,Statu1=((A1,B1),(C1,D1),1).update((X,Y,1),Move,Statu1):-(A,B)=X,(C,D)=Y,(E,F)=Move,C1isC-E,D1isD-F,A1isA+E,B1isB+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).传教士和野人问题有三个牧师和三个野人过河，只有一条能装下两个人的船，在河的任何一方或者船上，如果野人的人数大于牧师的人数，那么牧师就会有危险。你能不能找出一种安全的渡河方法呢,这个问题还可以扩展为N1个牧师和N2个野人，而船一次可以装下M个人的情况。我们使用AmziProlog解决上面的问题。这是个典型的状态图搜索问题，所以我们首先需要解决的问题就是使用Prolog的数据结构表达两岸的状态，以及对这些状态可能的操作。我们用下面的复合结构来表达问题的某个状态。((左岸牧师数，左岸野人数),(右岸牧师数，右岸野人数),船的位置)上面的结构中，船的位置为0表示船在左岸，为1表示在右岸。一开始，所有的人都在左岸。所以初始状态如下:((3,3),(0,0),0)而我们的目标状态则是:((0,0),(3,3),1)当然，这里只是为了方便起见，才使用了上面的结构，实际上是没有必要包括右岸的人数的，因为可以通过左岸的人数算出右岸的人数来。不过我们这里所选用的数据结构也有其优点，它可以是程序更加容易理解。船上所能够载人的状态就是可能的操作。用谓词move表示。move(1,0).表示船上有一位牧师，没有野人。move(0,1).move(0,2).move(2,0).move(1,1).有了上面的表达状态的数据结构以及移动的方法，我们还需要判断状态是否合法。下面的legal就是完成这个任务。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/1的几个例子:?-legal(((3,3),(0,0),1)).yes?-legal(((0,3),(3,0),1)).yes?-legal(((2,3),(1,0),0)).nolegal只判断牧师与野人的人数是否会造成牧师受到伤害，而不判断左右岸的人数之和是否正确。所以((2,1),(1,1),0)也是合法的状态。不过不用担心，在我们后面的程序中会避免这种情况出现的。下面的update谓词能够完成把合理的移动作用的某个状态上，从而到达新的状态。update((X,Y,0),Move,Statu1):-%船在左岸时(A,B)=X,(C,D)=Y,(E,F)=Move,C1isC+E,D1isD+F,A1isA-E,B1isB-F,Statu1=((A1,B1),(C1,D1),1).update((X,Y,1),Move,Statu1):-%船在右岸时(A,B)=X,(C,D)=Y,(E,F)=Move,C1isC-E,D1isD-F,A1isA+E,B1isB+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注意update只是简单地进行加减运算，它并不判断所得的新的状态是否合法。有了以上的三个谓词move，update，legal我们就可以很容易的做出判断两个合法的状态相邻的谓词，当然，此谓词也可以用来寻找某个状态的相邻状态。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)]yesfindroad/4的第三个参数是初始路由表，在此我们把终点状态放到其中，上面的findroad是从终点向起点寻找，由于是对称的，这并不影响结果。使用广度搜索也能完成相同的任务: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)]好了，到此为止过河问题已经基本上解决了。不过为了能够使用本程序分析一般情况，即牧师与野人的人数和船的载客量为其它值的情况，我们来稍微改写一下这个程序。谓词insert_move(N)，动态地向内存中加入船的载客量为N时，船上载客的所有可能情况。我们可以试试借用谓词leagal(X,Y)来实现:insert_move(N):-X+YisN,legal(X,Y),asserta(move(X,Y)).上面的asserta谓词把它的参数作为子句加入到内存中。这个程序看似简洁，其实错了，为什么呢,因为X，YisN有无穷组解。所以要用以下方法:get_integer(L,H,X):-L>H,!,fail.get_integer(L,H,L).get_integer(L,H,X):-L1isL+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)),N1isN-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=2Y=1;X=1Y=1;X=0Y=1;X=1Y=0;X=0Y=2;X=2Y=0;X=0Y=3;X=3Y=0;no谓词insert_statu(N1,N2)，动态地加入初始状态与目标状态，当然是N个牧师与N个野人的情况。insert_statu(N1,N2):-asserta(inistatu(((N1,N2),(0,0),0))),asserta(desstatu(((0,0),(N1,N2),1))).下面的谓词用来从内存中删除以上的动态信息。del_move:-retract(move(X,Y)),fail.del_move.del_stat:-retract(inistatu(X)),retract(desstatu(Y)),!.del_stat.这些谓词的第二个子句是为了保证谓词永远能够成功，以免再调用它们时出现问题。最后我们再分别编写使用广度搜索与深度搜索的主程序。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.deepsolve(N1,N2,M):-del_move,del_stat,insert_move(M),insert_statu(N1,N2),inistatu(X),desstatu(Y),!,findroad(Y,X,[Y],L),writelist(L),nl.第一个参数为野人与牧师的人数，第二个参数为船的最大载人量。它们分别调用findroad/3(广度搜索)findroad/4(深度搜索)来完成搜索任务。(在Prolog中参数数目不同的谓词，是不同的谓词)我们在深度搜索中加入的截断，因为我们想通过deepsolve判断问题是否有解，而通过widesolve寻找出最优解，这是因为广度搜索先总是找出最短路径。下面是完整的源程序:go.txt(解决过河问题的Prolog程序)get_integer(L,H,X):-L>H,!,fail.get_integer(L,H,L).get_integer(L,H,X):-L1isL+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).insert_move0(N):-asserta(move(N,0)),asserta(move(0,N)),N1isN-1,insert_move0(N1).insert_move1(N):-get_integer(1,N,X),get_integer(X,N,Y),X+Y=<N,asserta(move(Y,X)),fail.insert_move1(_).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,C1isC+E,D1isD+F,A1isA-E,B1isB-F,Statu1=((A1,B1),(C1,D1),1).update((X,Y,1),Move,Statu1):-(A,B)=X,(C,D)=Y,(E,F)=Move,C1isC-E,D1isD-F,A1isA+E,B1isB+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_statu(N1,N2),inistatu(X),desstatu(Y),!,findroad(L,X,Y),writelist(L),nl.deepsolve(N1,N2,M):-del_move,del_stat,insert_move(M),insert_statu(N1,N2),inistatu(X),desstatu(Y),!,findroad(Y,X,[Y],L),writelist(L),nl.go(Start,Target):-path(Start,Target,[Start],Path),write(‘Asolutionis:’),nl,write_path(Path).path(Start,Target,Visited,Path):-move(Start,NextNode),%Generateamovenot(unsafe(NextNode)),%Checkthatitissafenot(member(NextNode,Visited)),%Checkforrecurrencepath(NextNode,Target,[NextNode|Visited],Path),!.path(Target,Target,Path,Path).%Reachedthegoalmove(state(X,X,G,C),state(Y,Y,G,C)):-opposite(X,Y).%FARMER&WOLF