📄 subject_35570.htm
字号:
<p>
序号：35570 发表者：天涯另类人 发表日期：2003-04-07 22:53:07
<br>主题：大虾们看过来,这个问题有点难(对我而已)
<br>内容：问题:有6只狼,A,a,B,b,C,c.<BR>A,B,C是狼老爸,相应的a,b,c是它们的狼孩.<BR>现在它们要过一条河,只有一只船(限载两狼,不限大小)<BR>只有A,B,C,a会划船,且当狼老爸离开小狼时,该小狼会被其他狼老爸吃掉(除非因位置关系,吃不了)<BR>6只狼怎么样全部安全过河.<BR>用C++怎么实现啊,请大虾们给我个大概思想方法(算法)吧.
<br><a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p>
<hr size=1>
<blockquote><p>
<font color=red>答案被接受</font><br>回复者：Anu 回复日期：2003-04-07 23:16:38
<br>内容：有点类似于人工智能的“传教士与野人问题”，看看这对你有帮助吗？<BR>{转贴http://test.2hu.com/lyc/school/ai/m-c.htm]<BR>传教士和野人问题<BR><BR>编者：李钰澄<BR><BR>课堂上有这样一道题：<BR><BR>有三个牧师和三个野人过河，只有一条能装下两个人的船，在河的任何一方或者船上，如果野人的人数大于牧师的人数，那么牧师就会有危险。你能不能找出一种安全的渡河方法呢？ <BR><BR>这个问题还可以扩展为N1个牧师和N2个野人，而船一次可以装下M个人的情况。我们使用Amzi Prolog解决上面的问题。 <BR><BR>这是个典型的状态图搜索问题，所以我们首先需要解决的问题就是使用Prolog的数据结构表达两岸的状态，以及对这些状态可能的操作。我们用下面的复合结构来表达问题的某个状态。 <BR><BR>((左岸牧师数，左岸野人数),(右岸牧师数，右岸野人数),船的位置) <BR><BR>上面的结构中，船的位置为0表示船在左岸，为1表示在右岸。一开始，所有的人都在左岸。 <BR><BR>所以初始状态如下： <BR><BR>((3,3),(0,0),0) <BR><BR>而我们的目标状态则是： <BR><BR>((0,0),(3,3),1) <BR><BR>当然，这里只是为了方便起见，才使用了上面的结构，实际上是没有必要包括右岸的人数的，因为可以通过左岸的人数算出右岸的人数来。不过我们这里所选用的数据结构也有其优点，它可以是程序更加容易理解。 <BR><BR>船上所能够载人的状态就是可能的操作。用谓词move/2表示。 <BR><BR>move(1,0).表示船上有一位牧师，没有野人。<BR>move(0,1).<BR>move(0,2).<BR>move(2,0).<BR>move(1,1). <BR><BR>有了上面的表达状态的数据结构以及移动的方法，我们还需要判断状态是否合法。下面的legal/1就是完成这个任务。 <BR><BR>legal((X,Y,_)):- %X为左岸状态，Y为右岸状态。<BR> legal1(X), %分别判断两岸的状态是否合法。<BR> legal1(Y).<BR><BR><BR>legal1((X,Y)):- <BR> X=:=0,Y>=0,!. %牧师人数为0，野人的人数大于0，合法。<BR>legal1((X,Y)):-<BR> Y=:=0,X>=0,!. %野人人数为0，牧师的人数大于0，合法。<BR>legal1((X,Y)):-<BR> X>=Y,X>=0,Y>=0. %牧师数大于或等于野人数，且都大于0，合法。<BR><BR>下面是使用legal/1的几个例子： <BR><BR>?- legal(((3,3),(0,0),1)).<BR><BR>yes<BR>?- legal(((0,3),(3,0),1)).<BR><BR>yes<BR>?- legal(((2,3),(1,0),0)).<BR>no<BR><BR>legal/1只判断牧师与野人的人数是否会造成牧师受到伤害，而不判断左右岸的人数之和是否正确。所以((2,1),(1,1),0)也是合法的状态。不过不用担心，在我们后面的程序中会避免这种情况出现的。<BR><BR>下面的update/3谓词能够完成把合理的移动作用的某个状态上，从而到达新的状态。 <BR><BR>update((X,Y,0),Move,Statu1):- %船在左岸时<BR> (A,B)=X,<BR> (C,D)=Y,<BR> (E,F)=Move,<BR> C1 is C+E,<BR> D1 is D+F,<BR> A1 is A-E,<BR> B1 is B-F,<BR> Statu1=((A1,B1),(C1,D1),1).<BR><BR><BR>update((X,Y,1),Move,Statu1):- %船在右岸时<BR> (A,B)=X,<BR> (C,D)=Y,<BR> (E,F)=Move,<BR> C1 is C-E,<BR> D1 is D-F,<BR> A1 is A+E,<BR> B1 is B+F,<BR> Statu1=((A1,B1),(C1,D1),0).<BR><BR><BR>?- update(((3,3),(0,0),0),(1,1),X).<BR><BR>X = (2,2),(1,1),1 ;<BR>no<BR>?- update(((0,0),(3,3),0),(1,1),X).<BR><BR>X = (-1,-1),(4,4),1 ;<BR>no<BR>?- update(((1,2),(2,3),1),(3,4),X).<BR><BR>X = (4,6),(-1,-1),0 ;<BR>no<BR><BR>注意update只是简单地进行加减运算，它并不判断所得的新的状态是否合法。 <BR> <BR>有了以上的三个谓词move/2，update/3，legal/1我们就可以很容易的做出判断两个合法的状态相邻的谓词，当然，此谓词也可以用来寻找某个状态的相邻状态。<BR><BR>connect(Statu,Statu1):-<BR> move(X,Y),<BR> update(Statu,(X,Y),Statu1),<BR> legal(Statu1).<BR><BR>没什么好解释的，这是非常符合逻辑的谓词。 我们来看看功能：<BR><BR><BR>?- connect(((3,3),(0,0),0),X).<BR><BR>X = (2,2),(1,1),1 ; 一个野人与一个牧师过河<BR><BR>X = (3,2),(0,1),1 ; 一个野人过河<BR><BR>X = (3,1),(0,2),1 ; 两个野人过河<BR>no<BR><BR>再使用典型的深度搜索方法就可以找到答案了：<BR><BR>findroad(X,X,L,L).% 递归的边界条件。<BR>findroad(X,Y,L,L1):- % L为储存的路由表。<BR> connect(X,Z),<BR> not(member(Z,L)), % X所连接的节点Z不在已经储存的路由表中。<BR> findroad(Z,Y,[Z|L],L1).<BR><BR><BR>?- findroad(((0,0),(3,3),1),((3,3),(0,0),0),[((0,0),(3,3),1)],L).<BR><BR>L = [((3,3),(0,0),0),<BR> ((3,1),(0,2),1),<BR> ((3,2),(0,1),0),<BR> ((3,0),(0,3),1),<BR> ((3,1),(0,2),0),<BR> ((1,1),(2,2),1),<BR> ((2,2),(1,1),0),<BR> ((0,2),(3,1),1),<BR> ((0,3),(3,0),0),<BR> ((0,1),(3,2),1),<BR> ((1,1),(2,2),0),<BR> ((0,0),(3,3),1)] <BR><BR>yes<BR><BR>findroad/4的第三个参数是初始路由表，在此我们把终点状态放到其中，上面的findroad是从终点向起点寻找，由于是对称的，这并不影响结果。 <BR><BR>使用广度搜索也能完成相同的任务：<BR><BR>findroad([],X,X).<BR>findroad(Moves,State,Crit):-<BR> findroad(PrMoves,State,NextState),<BR> not(member(NextState,PrMoves)),<BR> connect(NextState,Crit),<BR> append(PrMoves,[NextState],Moves).<BR><BR>?- findroad(L,((3,3),(0,0),0),((0,0),(3,3),1)).<BR><BR><BR>L=[((3 , 3) , (0 , 0) , 0),<BR> ((2 , 2) , (1 , 1) , 1),<BR> ((3 , 2) , (0 , 1) , 0),<BR> ((3 , 0) , (0 , 3) , 1),<BR> ((3 , 1) , (0 , 2) , 0),<BR> ((1 , 1) , (2 , 2) , 1),<BR> ((2 , 2) , (1 , 1) , 0),<BR> ((0 , 2) , (3 , 1) , 1),<BR> ((0 , 3) , (3 , 0) , 0),<BR> ((0 , 1) , (3 , 2) , 1),<BR> ((0 , 2) , (3 , 1) , 0)]<BR><BR>好了，到此为止过河问题已经基本上解决了。不过为了能够使用本程序分析一般情况，即牧师与野人的人数和船的载客量为其它值的情况，我们来稍微改写一下这个程序。 谓词insert_move(N)，动态地向内存中加入船的载客量为N时，船上载客的所有可能情况。我们可以试试借用谓词leagal(X,Y)来实现：<BR><BR>insert_move(N):- <BR> X+Y is N,<BR> legal(X,Y),<BR> asserta(move(X,Y)).<BR><BR>上面的asserta/1谓词把它的参数作为子句加入到内存中。这个程序看似简洁，其实错了，为什么呢？因为 X＋Y is N 有无穷组解。所以要用以下方法： <BR><BR><BR>get_integer(L,H,X):-L>H,!,fail.<BR>get_integer(L,H,L). <BR>get_integer(L,H,X):-L1 is L+1,get_integer(L1,H,X).<BR><BR>insert_move(N):-<BR> insert_move0(N), <BR> insert_move1(N).<BR><BR>insert_move0(0). %野人或牧师有一方人数为0，则另一方的人数可以是0--N.<BR>insert_move0(N):-<BR> asserta(move(N,0)),<BR> asserta(move(0,N)),<BR> N1 is N-1,<BR> insert_move0(N1).<BR><BR>insert_move1(N):-%人数都不为0时，则野人的人数不能多于牧师的人数，并且总人数不能多于N.<BR> <BR> get_integer(1,N,X),<BR> get_integer(X,N,Y),<BR> X+Y=<N,<BR> asserta(move(Y,X)),<BR> fail.<BR>insert_move1(_).<BR>来试一下功能。<BR><BR>?- insert_move(3).<BR><BR>yes<BR><BR><BR>?- move(X,Y).<BR><BR>X = 2<BR>Y = 1 ;<BR><BR>X = 1<BR>Y = 1 ;<BR><BR>X = 0<BR>Y = 1 ;<BR><BR>X = 1<BR>Y = 0 ;<BR><BR>X = 0<BR>Y = 2 ;<BR><BR>X = 2<BR>Y = 0 ;<BR><BR>X = 0<BR>Y = 3 ;<BR><BR>X = 3<BR>Y = 0 ;<BR>no<BR><BR>谓词insert_statu(N1,N2)，动态地加入初始状态与目标状态，当然是N个牧师与N个野人的情况。<BR><BR>insert_statu(N1,N2):-<BR> asserta(inistatu(((N1,N2),(0,0),0))),<BR> asserta(desstatu(((0,0),(N1,N2),1))).<BR><BR>下面的谓词用来从内存中删除以上的动态信息。<BR><BR>del_move:-<BR> retract(move(X,Y)),<BR> fail.<BR>del_move.<BR><BR>del_stat:-<BR> retract(inistatu(X)),<BR> retract(desstatu(Y)),!.<BR>del_stat.<BR><BR>这些谓词的第二个子句是为了保证谓词永远能够成功，以免再调用它们时出现问题。<BR><BR>最后我们再分别编写使用广度搜索与深度搜索的主程序。<BR><BR>widesolve(N1,N2,M):-<BR> del_move,<BR> del_stat,<BR> insert_move(M),<BR> insert_statu1,(N1,N2),<BR> inistatu(X),<BR> desstatu(Y),<BR> !,<BR> findroad(L,X,Y),<BR> writelist(L),<BR> nl.<BR><BR><BR>deepsolve(N1,N2,M):-<BR> del_move,<BR> del_stat,<BR> insert_move(M),<BR> insert_statu(N1,N2),<BR> inistatu(X),<BR> desstatu(Y),<BR> !,<BR> findroad(Y,X,[Y],L),<BR> writelist(L),<BR> nl.<BR> <BR><BR>第一个参数为野人与牧师的人数，第二个参数为船的最大载人量。它们分别调用findroad/3（广度搜索）findroad/4（深度搜索）来完成搜索任务。（在Prolog中参数数目不同的谓词，是不同的谓词）<BR><BR>我们在深度搜索中加入的截断，因为我们想通过deepsolve判断问题是否有解，而通过widesolve寻找出最优解，这是因为广度搜索先总是找出最短路径。<BR><BR>下面是完整的源程序：<BR><BR>go.txt (解决过河问题的Prolog程序）<BR><BR>有了上面的程序，我们将使用它来分析一般的过河情况，并给出过河问题的一般解答。<BR><BR>?- deepsolve(3,3,2). 三个牧师三个野人，船一次能装两个人<BR>(3 , 3) , (0 , 0) , 0<BR>(3 , 1) , (0 , 2) , 1<BR>(3 , 2) , (0 , 1) , 0<BR>(3 , 0) , (0 , 3) , 1<BR>(3 , 1) , (0 , 2) , 0<BR>(1 , 1) , (2 , 2) , 1<BR>(2 , 2) , (1 , 1) , 0<BR>(0 , 2) , (3 , 1) , 1<BR>(0 , 3) , (3 , 0) , 0<BR>(0 , 1) , (3 , 2) , 1<BR>(1 , 1) , (2 , 2) , 0<BR>(0 , 0) , (3 , 3) , 1<BR>yes<BR><BR><BR>?- widesolve(3,3,2).<BR>(3 , 3) , (0 , 0) , 0<BR>(2 , 2) , (1 , 1) , 1<BR>(3 , 2) , (0 , 1) , 0<BR>(3 , 0) , (0 , 3) , 1<BR>(3 , 1) , (0 , 2) , 0<BR>(1 , 1) , (2 , 2) , 1<BR>(2 , 2) , (1 , 1) , 0<BR>(0 , 2) , (3 , 1) , 1<BR>(0 , 3) , (3 , 0) , 0<BR>(0 , 1) , (3 , 2) , 1<BR>(0 , 2) , (3 , 1) , 0<BR>yes<BR><BR><BR>?- deepsolve(4,4,2). 此情况无解<BR>no<BR><BR><BR>?- deepsolve(4,4,3). 必须扩大船的容量<BR>(4 , 4) , (0 , 0) , 0<BR>(4 , 2) , (0 , 2) , 1<BR>(4 , 3) , (0 , 1) , 0<BR>(4 , 1) , (0 , 3) , 1<BR>(4 , 2) , (0 , 2) , 0<BR>(4 , 0) , (0 , 4) , 1<BR>(4 , 1) , (0 , 3) , 0<BR>(1 , 1) , (3 , 3) , 1<BR>(2 , 2) , (2 , 2) , 0<BR>(0 , 1) , (4 , 3) , 1<BR>(1 , 1) , (3 , 3) , 0<BR>(0 , 0) , (4 , 4) , 1<BR>yes<BR><BR><BR>?- widesolve(4,4,3). 可以看出使用广度搜索出来的答案一般比深度搜索的短<BR>(4 , 4) , (0 , 0) , 0<BR>(3 , 3) , (1 , 1) , 1<BR>(4 , 3) , (0 , 1) , 0<BR>(2 , 2) , (2 , 2) , 1<BR>(3 , 3) , (1 , 1) , 0<BR>(0 , 3) , (4 , 1) , 1<BR>(0 , 4) , (4 , 0) , 0<BR>(0 , 2) , (4 , 2) , 1<BR>(0 , 3) , (4 , 1) , 0<BR>yes<BR><BR><BR>?- deepsolve(5,5,3). 五个野人与五个牧师，也可以使用可载三人的船过河<BR>(5 , 5) , (0 , 0) , 0<BR>(5 , 3) , (0 , 2) , 1<BR>(5 , 4) , (0 , 1) , 0<BR>(5 , 2) , (0 , 3) , 1<BR>(5 , 3) , (0 , 2) , 0<BR>(5 , 1) , (0 , 4) , 1<BR>(5 , 2) , (0 , 3) , 0<BR>(2 , 2) , (3 , 3) , 1<BR>(3 , 3) , (2 , 2) , 0<BR>(0 , 3) , (5 , 2) , 1<BR>(0 , 4) , (5 , 1) , 0<BR>(0 , 2) , (5 , 3) , 1<BR>(2 , 2) , (3 , 3) , 0<BR>(0 , 1) , (5 , 4) , 1<BR>(1 , 1) , (4 , 4) , 0<BR>(0 , 0) , (5 , 5) , 1<BR><BR><BR>?- widesolve(5,5,3). 使用广度搜索找到最佳答案<BR>(5 , 5) , (0 , 0) , 0<BR>(4 , 4) , (1 , 1) , 1<BR>(5 , 4) , (0 , 1) , 0<BR>(5 , 1) , (0 , 4) , 1<BR>(5 , 2) , (0 , 3) , 0<BR>(2 , 2) , (3 , 3) , 1<BR>(3 , 3) , (2 , 2) , 0<BR>(0 , 3) , (5 , 2) , 1<BR>(0 , 4) , (5 , 1) , 0<BR>(0 , 2) , (5 , 3) , 1<BR>(0 , 3) , (5 , 2) , 0<BR>yes<BR><BR><BR>?- deepsolve(6,6,3). 各六个人时就不能通过载三人的船过河<BR>no<BR><BR><BR>?- deepsolve(6,6,4). 必须扩大船的容量。<BR>(6 , 6) , (0 , 0) , 0<BR>(4 , 4) , (2 , 2) , 1<BR>(5 , 5) , (1 , 1) , 0<BR>(3 , 3) , (3 , 3) , 1<BR>(4 , 4) , (2 , 2) , 0<BR>(2 , 2) , (4 , 4) , 1<BR>(3 , 3) , (3 , 3) , 0<BR>(0 , 2) , (6 , 4) , 1<BR>(0 , 3) , (6 , 3) , 0<BR>(0 , 1) , (6 , 5) , 1<BR>(2 , 2) , (4 , 4) , 0<BR>(0 , 0) , (6 , 6) , 1<BR>yes<BR><BR><BR>?-widesolve(5,3,2). 对传教士和野人的人数不同时的广度搜索。<BR>(5 , 3) , (0 , 0) , 0<BR>(4 , 2) , (1 , 1) , 1<BR>(4 , 3) , (1 , 0) , 0<BR>(3 , 2) , (2 , 1) , 1<BR>(3 , 3) , (2 , 0) , 0<BR>(2 , 2) , (3 , 1) , 1<BR>(3 , 2) , (2 , 1) , 0<BR>(2 , 1) , (3 , 2) , 1<BR>(2 , 2) , (3 , 1) , 0<BR>(1 , 1) , (4 , 2) , 1<BR>(2 , 1) , (3 , 2) , 0<BR>(1 , 0) , (4 , 3) , 1<BR>(1 , 1) , (4 , 2) , 0<BR>yes<BR><BR><BR>?- deepsolve(5,3,2).对传教士和野人的人数不同时的广度搜索。<BR>(5 , 3) , (0 , 0) , 0<BR>(4 , 2) , (1 , 1) , 1<BR>(4 , 3) , (1 , 0) , 0<BR>(3 , 2) , (2 , 1) , 1<BR>(4 , 2) , (1 , 1) , 0<BR>(3 , 1) , (2 , 2) , 1<BR>(3 , 2) , (2 , 1) , 0<BR>(2 , 1) , (3 , 2) , 1<BR>(3 , 1) , (2 , 2) , 0<BR>(2 , 0) , (3 , 3) , 1<BR>(2 , 1) , (3 , 2) , 0<BR>(1 , 0) , (4 , 3) , 1<BR>(1 , 1) , (4 , 2) , 0<BR>(0 , 0) , (5 , 3) , 1<BR>yes<BR><BR>再往后就没有什么意义了，因为如果船能够载四个人的话，任意多的野人与牧师都可以过河的。解法很简单，就是每次都两个野人两个牧师过河，回渡时则使用一个野人一个牧师。<BR><BR> <BR>?-widesolve(5,3,2). 对传教士和野人的人数不同时的广度搜索。<BR>(5 , 3) , (0 , 0) , 0<BR>(4 , 2) , (1 , 1) , 1<BR>(4 , 3) , (1 , 0) , 0<BR>(3 , 2) , (2 , 1) , 1<BR>(3 , 3) , (2 , 0) , 0<BR>(2 , 2) , (3 , 1) , 1<BR>(3 , 2) , (2 , 1) , 0<BR>(2 , 1) , (3 , 2) , 1<BR>(2 , 2) , (3 , 1) , 0<BR>(1 , 1) , (4 , 2) , 1<BR>(2 , 1) , (3 , 2) , 0<BR>(1 , 0) , (4 , 3) , 1<BR>(1 , 1) , (4 , 2) , 0<BR>yes<BR><BR><BR>?- deepsolve(5,3,2).对传教士和野人的人数不同时的广度搜索。<BR>(5 , 3) , (0 , 0) , 0<BR>(4 , 2) , (1 , 1) , 1<BR>(4 , 3) , (1 , 0) , 0<BR>(3 , 2) , (2 , 1) , 1<BR>(4 , 2) , (1 , 1) , 0<BR>(3 , 1) , (2 , 2) , 1<BR>(3 , 2) , (2 , 1) , 0<BR>(2 , 1) , (3 , 2) , 1<BR>(3 , 1) , (2 , 2) , 0<BR>(2 , 0) , (3 , 3) , 1<BR>(2 , 1) , (3 , 2) , 0<BR>(1 , 0) , (4 , 3) , 1<BR>(1 , 1) , (4 , 2) , 0<BR>(0 , 0) , (5 , 3) , 1<BR>yes<BR><BR>好了，到此为止，过河问题可以说是圆满的解决了。下面是完整的源程序：<BR><BR>m-c.txt (解决过河问题的Prolog程序）<BR><BR>编者注：本程序根据垂钓听竹轩的过桥问题改编 <BR>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -