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

实验七 用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, 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). 传教士和野人问题 有三个牧师和三个野人过河，只有一条能装下两个人的船，在河的任何一方或者船上，如果野人的人数大于牧师的人数，那么牧师就会有危险。你能不能找出一种安全的渡河方法呢？ 这个问题还可以扩展为N1个牧师和N2个野人，而船一次可以装下M个人的情况。我们使用Amzi Prolog解决上面的问题。 这是个典型的状态图有哪些信誉好的足球投注网站问题，所以我们首先需要解决的问题就是使用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