失眠网 > 人工智能实验二——prolog语言求解渡河问题（传教士和野人渡河农夫渡河问题）实现详解

人工智能实验二——prolog语言求解渡河问题（传教士和野人渡河农夫渡河问题）实现详解

时间：2020-02-04 06:37:28

农夫渡河问题求解

这两个问题都是渡河问题，思路和方式是一样的：给出求解Prolog代码：

问题描述

一个农夫带着一匹狼、一只羊、一颗白菜要过河，

只有一条船而且

农夫每次最多只能带一个动物或物品过河，

并且当农夫不在的时候狼会吃羊，羊会吃白菜，

列出所有安全将所有动物和物品带过河的方案。

move(1,0,0,0).% 元组保存渡河方式 move(1,1,0,0).% 分别表示农夫狼羊白菜move(1,0,1,0).% 只有农夫会开船故每种方式农夫都要渡河move(1,0,0,1).% 农夫渡河可以啥也不带也可以只带一个物品safe((F,W,S,C)):- %某个岸边安全的状态 (F=:=1); % 农夫只要在总是安全的(F=:=0,W=:=1,S=:=0); %农夫不在狼在则羊不能在白菜可在可不在(F=:=0,W=:=0,S=:=1,C=:=0); %农夫不在狼不在羊在白菜不能在(F=:=0,W=:=0,S=:=0).%均不在或只有白菜在allSafe((L,R,_)):- % 河岸两边都要安全 _表示不关心的状态即船的状态不关心safe(L),safe(R).aftermove((L,R,Ship),Move,Statu):- %移动之后两个河岸状态发生改变(Fal,Wol,Shl,Cal)=L, %先将移动前的状态赋值给变量(Far,Wor,Shr,Car)=R,(A,B,C,D)=Move,if_then_else((Ship=:=0), %根据船的位置判断河岸两边的改变情况( Tl1 is Fal-A, Tl2 is Wol-B, Tl3 is Shl-C, Tl4 is Cal-D,Tr1 is Far+A, Tr2 is Wor+B, Tr3 is Shr+C, Tr4 is Car+D,Statu = ((Tl1,Tl2,Tl3,Tl4),(Tr1,Tr2,Tr3,Tr4),1)),( Tl1 is Fal+A, Tl2 is Wol+B, Tl3 is Shl+C, Tl4 is Cal+D,Tr1 is Far-A, Tr2 is Wor-B, Tr3 is Shr-C, Tr4 is Car-D,Statu = ((Tl1,Tl2,Tl3,Tl4),(Tr1,Tr2,Tr3,Tr4),0))).valid(Statu,Statu1):-move(F,W,S,C), %某种渡河方式aftermove(Statu,(F,W,S,C),Statu1), %移动之后状态改变allSafe(Statu1). %检测移动后是一个安全的状态% 下同野人和传教士自己去理解下吧first_one(A,X):-append([A],_,X). if_then_else(Condition,Then,Else) :- %定义if_then_else的执行逻辑在下面使用call(Condition) -> call(Then) ; call(Else).last_part(A,X):-first_one(B,X),append([B],A,X). show(L):-if_then_else((length(L,X),X>0),(first_one(A,L) , last_part(B,L) ,write('['),write(A),write(']'),nl,show(B)),fail).nfgh(X,Y,L):- % Lif_then_else(X=Y,(write('***********************'),nl,show(L),nl),(valid(X,Z), not(member(Z,L)),nfgh(Z,Y,[Z|L]))).

查询命令为：

nfgh(((1,1,1,1),(0,0,0,0),0),((0,0,0,0),(1,1,1,1),1),[((1,1,1,1),(0,0,0,0),0)]).

运行结果如下：

表明有两种合法的渡河方式。

传教士和野人渡河问题

问题描述

在河的左岸有N个传教士、N个野人和一条船，传教士们想用这条船把所有人都运过河去，但有以下条件限制：

（1）修道士和野人都会划船，但船每次最多只能运K个人；

（2）在任何岸边野人数目都不能超过修道士，否则修道士会被野人吃掉。

假定野人会服从任何一种过河安排，请规划出一个确保修道士安全过河的计划。

move(1,0).%元组列出渡河方式 1个传教士 0个野人move(0,1).%元组列出渡河方式 0个传教士 1个野人move(0,2).%元组列出渡河方式 0个传教士 2个野人move(2,0).% 2个传教士 0个野人move(1,1).% 1个传教士 1个野人safe((X,Y)):- %某岸安全的条件(X=:=0,Y>=0,!); %条件1 传教士人数为0 野人数不论(X>=Y,X>=0,Y>=0). %条件2 传教士人数大于野人人数，且均大于0allsafe((X,Y,_)):- % 左右岸都要安全下划线表示船的状态不心关safe(X),safe(Y).if_then_else(Condition,Then,Else) :- %定义if_then_else的执行逻辑在下面使用call(Condition) -> call(Then) ; call(Else).aftermove((X,Y,Q),Move,Statu):-(A,B)=X,(C,D)=Y,(E,F)=Move,if_then_else(Q=:=0, % if 注意船的位置要变(C1 is C+E, D1 is D+F, A1 is A-E, B1 is B-F, Statu=((A1,B1),(C1,D1),1)), % then 对应左岸和右岸人数的改变注意船的位置要变(C1 is C-E, D1 is D-F, A1 is A+E, B1 is B+F, Statu=((A1,B1),(C1,D1),0)) % else).valid(Statu,Statu1):- %有效转移move(X,Y),aftermove(Statu,(X,Y),Statu1),allsafe(Statu1).% 移动之后要求都是合法的first_one(A,X):- append([A],_,X). %记录转移的状态开始 A等于表X的第一个元素last_part(A,X):- first_one(B,X),append([B],A,X). %AX A等于表X的除第一个元素的后部分表show(L):- %输出过程if_then_else((length(L,X),X>0),(first_one(A,L),last_part(B,L),write('['),write(A),write(']'),nl,show(B)),fail).cjsyyr(X,Y,L):- % Lif_then_else(X=Y, % 开始状态到达目标状态就输出否则就递归(write('================'),nl,show(L),nl),(valid(X,Z), not(member(Z,L)),cjsyyr(Z,Y,[Z|L]))).

运行结果：

在prolog框中输入：

cjsyyr(((0,0),(3,3),1),((3,3),(0,0),0),[((0,0),(3,3),1)]).

解释一下这个查询语句：

初始状态是 (0,0),(3,3),1)：表示

左岸 0个传教士，0个野人

右岸3个传教士，3个野人

船在右岸

目标状态是((3,3),(0,0),0)：表示

右岸 0个传教士，0个野人

左岸3个传教士，3个野人

船在左岸

[((0,0),(3,3),1)]表示输出的一个最终状态

回车后查询，运行结果如下：

?- cjsyyr(((0,0),(3,3),1),((3,3),(0,0),0),[((0,0),(3,3),1)]).================[(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][(0,0),(3,3),1]================[(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][(0,2),(3,1),0][(0,0),(3,3),1]================[(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][(1,1),(2,2),0][(0,0),(3,3),1]================[(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]

也就是说当有3个野人 3个传教士时会有4种渡河方式。