人工智能：野人与修道士问题

1、野人与修道士问题(Missionaries-and-CannibalsProbl(修道士与野人问题三个野人与三个传教士來到河边，打算乘一只到左岸去，该船的最人负载能力为两个人。在任何时候，如果野人人匚士人数，那么野人就会把传教士吃掉。用状态空间法表示修道士与野人问题并设计编写计算机程序求问题滋问题分析：修道士M野人cAAA从上图可知，修道士、野人和船一共有六种可能，Ml、Cl、Bl、Mr、Cr、示为q=(M,C,B),其中m表示修道士的数冃(0、1、2、3)、c:数冃(0、1、2、3)、b表示船在左岸(1)或右岸(0)o1、定义状态的描述形式：(m,c,b)题状态的改变是通过划船渡河來引发的，

2、所以合理的渡河操作就成了:算符，根据题冃要求，可以得出以下5个算符（按照渡船方向的不理解为10个算符）：2、表示所有可能的状态,并确定初始状态集和目标状态集s0(3,3,l)sl(3z2zl)s2(3zlzl)s3(3z0zl)s4(2,3J)s5(2,2zl)s6(2丄1)s8(l,3zl)s9(lz2zl)sl0(lzlzl)sll(lAl)sl2(0z3,l)S13(O,2Z1)sl4(0丄1)sl6(3z3z0)sl7(3z2z0)sl8(3zl,0)sl9(3z0z0)s20(2z3,0)s21(2z2z0)s22(2丄0)s24(lz3z0)s25(lz2z0)s26(lzlz0)

3、s27(lz0z0)s28(0,3,0)s29(0z2,0)s30(0丄0)渡1野人、渡1牧师、渡1野人1牧师、渡2野人、渡2牧！h即：L01或R01,L10或RIO,L11或Rll,L02或R02,L2054、状态空间图：5、设计编写计算机程序求问题的解：算法：在应用状态空间表示和搜索方法时，用（M,C,B）来:述，其中M和C分别表示在左岸的传教士与野人数。B为1表示船:0表示在右岸。于是初始状态为（0,0,0）,冃标状态为（3,3,1）问题用图表示出来，首先牛成各种安全状态结点，存放在顶点向量中图的邻接矩阵存储结构后，利用深度优允搜萦思想从顶点、（0,0,0）3,1）的一条简单路径。#in

4、clude/*最大顶点个数/*定义图的顶点刁#include#defineVEX_NUM18tvpedefstruct!intpathVEX_NUM;/*查找顶点(M,C,B)在顶点向量中的位置*/intlocate(AdjGraph*G,intM,intC,intB)inti；for(i=O;ivexnum;i+)if(G-vcxsi.Missionary=M&G-vcxsi.Cannibal=C&G-vcxsi.Boat=B)return(i);return(-l);/*判断状态(M,C,B)是否合理犁intis_safe(intM.intCJntB)if(M=C)if(M=3)if(B=

5、0)return(0);elsereturn(1);elseif(MO)if(B=l)return(0);elsereturn(1);elsereturn(1);elseif(M=0)|(M=3)return(1);elsereturn(0);G-vexsj.Cannibal-G-vexsi.Cannibal=-1)k+;if(G-vcxsj.Missionary-G-vcxsi.Missionary=-2&G-vexsj.Cannibal=G-vexsi.Cannibal)k+;if(G-vexsj.Missionary=G-vexsi.Missionary&G-vexsj.Cannibal

6、-G-vexsi.Canniba1=2)k+;if(G-vcxsj.Missionary-G-vcxsi.Missionary=-1&G-vexsj.Canniba1-G-vexsi.Cannibal=J)k+;if(G-vexsj.Boat=0&k=1)return(1);elsereturn(0);while(G-vexsi.BoatO)if(G-vexsj.MissionaryG-vexsi.Missionary=l&G-vcxsj.Cannibal=G-vcxsi.Cannibal)k+;if(G-vcxsj.Missionary=G-vcxsi.Missionary&G-vexsj.

7、Cannibal-G-vexsi.Cannibal=1)k+;if(G-vexsj.Missionary-G-vexsi.Missionary=2&G-vexsj.Cannibal=G-vexsi.Cannibal)k+;if(G-vexsj.Missionary=G-vexsi.Missionary&G-vexsj.Cannibal-G-vexsi.Cannibal=2)k+;if(G-vexsj.Missionary-G-vexsi.Missionary=1&G-vexsj.Cannibal-G-vexsi.Cannibal=1)k+;if(G-vexsj.Boat=1&k=l)retur

8、n(1);elsereturn(0):for(C=0;Cv=3;C+)fbr(B=O;Bvexsi.Missionary=M;G-vexsi.Cannibal=C;G-vexsi.Boat=B;i卄；Gvcxnum=i;for(i=O;ivexnum;i+)/*生成邻接矩阵*/for(j=O;jvexnum;j+)if(is_connected(G,ij)G-adjij=G-adjji=l；elseG-adjij=G-adjji=O;return;voidDFS_path(AdjGraph*G,intujntv)/*求从U到V的简单路彳罕intj;visitedu=l;for(j=O;jvexnum;j+)if(G-adjuj=l&visitedj=O&visitedv=O)pathu=j;DFS_path(GJ?v);/*深度优先搜索*/voidprint_path(AdjGraph*G,intu9intv)/*输出从U到V的简单intk=u;while(k!=v)printf(%d,%d,%d)nn,G-vexsk.Missionary,G-vexsk.CannibalG-vexsk.Boat);koathrkl:/*主程序如下：*/main()inti,j；AdjGraphgraph;CreateG(&g