修道士与野人问题
实验课名称：数据结构实验五
实验名称：修道士与野人问题
班级：20130612 学号：2013061213 姓名：李寅龙时间：2015-6-8
1.问题描述
河的左岸有N个野人和N个修道士以及一条小船，修道士们想用这条小船把所有的人都运到河的右岸，但又受到以下限制：
●修道士和野人都会划船，但船一次只能载C人。
●在任何岸边，为了防止野人侵犯修道士，野人数不能超过修道士数，否
则修道士将会被野人吃掉。
假定野人愿意服从任何一种过河的安排，本设计的主要任务是规划出一种确保修道士安全的过河方案。
②设计要求
●设计表示野人、修道士、船的位置信息等数据的逻辑结构和存储结构。
●从键盘输入修道士与野人的人数N和船可容纳的人数C。
●设计检测某一时刻两岸修道士是否安全的算法。
●输出安全过河的详细路径。
界面友好，操作简单。
2.数据结构设计
（1）采用图的邻接表存储结构搜索。
typedef struct
{
int xds; //修道士个数
int yr; //野人个数
int cw; //船的位置
}DataType;
typedef struct node//结构体定义
{
DataType data;
struct node *son;//儿子
struct node *bro;//兄弟
struct node *par;//双亲
struct node *next;
}Link;
3.算法设计
（1）对所有的可能渡河情况进行安全检测，，以减去修道士少于野人的情况：
int safe(DataType x,int n)
{
if ((x.xds>=x.yr||x.xds==0)&&((n-x.xds)>=(n-x.yr)
||x.xds==n)&&x.xds>=0&&x.xds<=n&&x.yr>=0&&x.yr<=n)
return 1;
else
return 0;
}
（2）用广度搜索法搜索边数最少的一条通路：
void guangdu(Link *p,int n,int c)
{
Link *q,*t;
DataType tem;
int i,flag1,flag2,g=0,j,count=0;
q=p->son;
while (q!=NULL)/
{
flag1=0;
j=boatcase(q->data,c);
for (i=0;i tem.xds=q->data.xds-array[i].xds; tem.yr=q->data.yr-array[i].yr; tem.cw=1-q->data.cw; t=q; if (safe(tem,n)) { flag2=1;//1 while (t!=p) { if(tem.xds== t->data.xds&&tem.yr==t->data.yr&&tem.cw==t->data.cw) { flag2=0; break; } t=t->par; } if(flag2==1) { if (flag1==0) { insertson(q, tem); flag1=1; } else insertbro(q,tem); if (tem.xds==0&&tem.yr==0&&tem.cw==0) { print(q,p); count++ ；} } } } q=q->next; } if (count==0) printf("无法成功渡河!\n"); else printf("有%d种渡河方式。\n",count);} 3）、生成所有的可能渡河情况： int boatcase(DataType x,int n) { int i=0,a,b,t=0; if(x.cw) { a=0;b=n-a; while (a+b>=1) { t++; while (b>=0) { array[i].xds=a; array[i].yr=b; i++; a++; b--; } a=0; b=n-a-t; } } else { a=1;b=0;t=0; while (a+b<=n) { t++; while (a>=0) { array[i].xds=a*(-1); array[i].yr=b*(-1); i++; a--; b++; } a=array[0].xds*(-1)+t; b=0; } } return i; } 4）、输出所有安全渡河结果： void print(Link *q,Link *p) { DataType a[100]; int i=1; a[0].cw=0; a[0].xds=0; a[0].yr=0; while (q!=p) { a[i++]=q->data; q=q->par; } while ((--i)>-1) { printf("( %d %d %d )",a[i].xds,a[i].yr,a[i].cw); if (!(a[i].xds==0&&a[i].yr==0&&a[i].cw==0)) { if(a[i].cw==1) printf("-->(%d %d)-->(%d %d 0)\n",a[i].xds-a[i-1].xds,a[i].yr-a[i-1].yr,a[i-1].xds,a[i-1].yr); else printf(" <-- ( %d %d ) <-- ( %d %d 1 )\n",(a[i].xds-a[i-1].xds)*(-1),(-1)*(a[i].yr-a[i-1].yr),a[i-1].xds,a[i-1].yr ); } } printf("渡河成功!\n");} 4. 运行、测试与分析 （1）运行程序，显示画面 （2）输入 （3）输出所有渡河方法、 （4）输入错误有提示并且可重新输入 5.实验收获及思考 通过这次实验，我对图的知识以及相关的数据结构有了一定的了解。为了更好的掌握相关的知识，还是要多加练习。同时，编程的时候要考虑全面，顾及各种可能的情况以及作出相应的提示。 教师评分： 教师签名： 源代码： #include #include #include typedef struct { int xds; //修道士个数 int yr; //野人个数 int cw; //船的位置 }DataType; DataType array[50000]; typedef struct node//结构体定义 { DataType data; struct node *son;//儿子 struct node *bro;//兄弟 struct node *par;//双亲 struct node *next; }Link; void Linkinit(Link **head) //初始化操作 { *head=(Link *)malloc(sizeof (Link)); //申请动态空间 (*head)->son=NULL; (*head)->bro=NULL; (*head)->par=NULL; (*head)->next=NULL; } void insertson(Link *head, DataType x) //在邻接表中插入儿子结点的操作{ Link *q,*s; q=(Link *)malloc(sizeof (Link)); q->data=x; head->son=q;//将x插入给头结点的儿子指针 s=head; while (s->next!=NULL) s=s->next; q->par=head; q->son=NULL; q->bro=NULL; s->next=q; q->next=NULL; void insertbro(Link *head,DataType x)//在邻接表中插入兄弟结点的操作，//所有的兄弟结点都指向他们右边的结点 { Link *q,*s; q=(Link *)malloc(sizeof (Link)); s=head->son; q->data=x; while (s->bro!=NULL) s=s->bro; s->bro=q; s->next=q; q->next=NULL; q->bro=NULL; q->par=head; q->son=NULL; } int boatcase(DataType x,int n) //生成所有情况； { int i=0,a,b,t=0; if(x.cw) //在此岸,上船的人多优先 { a=0;b=n-a; //a为修道士b为野人 while (a+b>=1)//当船上有人时 { t++; while (b>=0)//当野人个数不为负数 { array[i].xds=a; array[i].yr=b; i++; a++; b--; } a=0;//船上空位个数 b=n-a-t; } } else//在对岸,上船的人少优先 { a=1;b=0;t=0; while (a+b<=n) { t++;//船上的人数 while (a>=0) { array[i].xds=a*(-1); array[i].yr=b*(-1); i++; a--; b++; } a=array[0].xds*(-1)+t; b=0; } } return i; //i为总数量 } int safe(DataType x,int n)//安全性检测 { // 起始目的if ((x.xds>=x.yr||x.xds==0)&&((n-x.xds)>=(n-x.yr)||x.xds==n)&&x.xds>=0&&x.xds<=n&&x.yr>= 0&&x.yr<=n) return 1;//船上修道士 else return 0; } void print(Link *q,Link *p) //打印安全渡河的过程,当船到对岸时,把对岸当作其始岸,此岸当作彼岸 { DataType a[100]; int i=1; a[0].cw=0; a[0].xds=0; a[0].yr=0; while (q!=p)//避免出现相同情况而循环 { a[i++]=q->data;//将一次过河的情况给b[i] q=q->par; } while ((--i)>-1) //输出过河图 { if (!(a[i].xds==0&&a[i].yr==0&&a[i].cw==0)) { if(a[i].cw==1) printf("( %d %d %d ) --> ( %d %d ) --> ( %d %d 0 )\n",a[i].xds,a[i].yr,a[i].cw,a[i].xds-a[i-1].xds,a[i].yr-a[i-1].yr,a[i-1].xds,a[i-1].yr); //a[i].xds-a[i-1].xds表示过河过程中船上的修道士数,a[i].yr-a[i-1].yr表示过河 过程中船上的野人数 else printf("( %d %d 1 ) <-- ( %d %d ) <-- ( %d %d %d )\n",a[i-1].xds,a[i-1].yr,(a[i].xds-a[i-1].xds)*(-1),(-1)*(a[i].yr-a[i-1].yr),a[i].xds,a[i].y r,a[i].cw); } } printf("渡河成功!\n\n\n"); } void guangdu(Link *p,int n,int c)//广度搜索 { Link *q,*t; DataType tem; int i,flag1,flag2,g=0,j,count=0; q=p->son; while (q!=NULL)//逐个搜索儿子结点 { flag1=0;//等于0表示插入儿子结点,1表示插入兄弟结点 j=boatcase(q->data,c);//可能过河的情况 for (i=0;i { tem.xds=q->data.xds-array[i].xds; tem.yr=q->data.yr-array[i].yr; tem.cw=1-q->data.cw; t=q; if (safe(tem,n))//是否安全 { flag2=1;//1表示没有死循环 while (t!=p)//保证不会出现循环 { if(tem.xds== t->data.xds&&tem.yr==t->data.yr&&tem.cw==t->data.cw) {//出现相当情况时候 flag2=0; break; } t=t->par; } if(flag2==1) { if (flag1==0)//插入儿子结点 { insertson(q, tem); flag1=1; } else//插入兄弟结点 insertbro(q,tem); if (tem.xds==0&&tem.yr==0&&tem.cw==0) { print(q,p); count++; } } } } q=q->next; } if (count==0) printf("无法成功渡河!\n\n"); else printf("有%d种渡河方式。\n\n",count); } int main() { int n,c,back; Link *p; DataType tem; while (back) { printf("请输入修道士与野人的人数n:\n"); scanf("%d",&n); if (n==0) break; printf("请输入船可容纳的人数c:\n"); scanf("%d",&c); printf("< 修道士野人1（左岸）> -- 船< 修道士野人> -- <修道士野人0（左岸) >\n\n"); tem.xds=n; tem.yr=n; tem.cw=1; Linkinit(&p); //初始化邻接表; insertson(p, tem); //将初始状态作为头结点的孩子结点； guangdu(p,n,c); //进行广度搜索； printf("是否继续?(继续1 ,退出0 )\n"); scanf("%d",&back); } } 实验课名称：数据结构实验五 实验名称：修道士与野人问题 班级：20130612 学号：2013061213 姓名：李寅龙时间：2015-6-8 1.问题描述 河的左岸有N个野人和N个修道士以及一条小船，修道士们想用这条小船把所有的人都运到河的右岸，但又受到以下限制： ●修道士和野人都会划船，但船一次只能载C人。 ●在任何岸边，为了防止野人侵犯修道士，野人数不能超过修道士数，否 则修道士将会被野人吃掉。 假定野人愿意服从任何一种过河的安排，本设计的主要任务是规划出一种确保修道士安全的过河方案。 ②设计要求 ●设计表示野人、修道士、船的位置信息等数据的逻辑结构和存储结构。 ●从键盘输入修道士与野人的人数N和船可容纳的人数C。 ●设计检测某一时刻两岸修道士是否安全的算法。 ●输出安全过河的详细路径。 界面友好，操作简单。 2.数据结构设计 （1）采用图的邻接表存储结构搜索。 typedef struct { int xds; //修道士个数 int yr; //野人个数 int cw; //船的位置 }DataType; typedef struct node//结构体定义 { DataType data; struct node *son;//儿子 struct node *bro;//兄弟 struct node *par;//双亲 struct node *next; }Link; 3.算法设计 （1）对所有的可能渡河情况进行安全检测，，以减去修道士少于野人的情况： int safe(DataType x,int n) { if ((x.xds>=x.yr||x.xds==0)&&((n-x.xds)>=(n-x.yr) ||x.xds==n)&&x.xds>=0&&x.xds<=n&&x.yr>=0&&x.yr<=n) return 1; else return 0; } （2）用广度搜索法搜索边数最少的一条通路： void guangdu(Link *p,int n,int c) { Link *q,*t; DataType tem; int i,flag1,flag2,g=0,j,count=0; q=p->son; while (q!=NULL)/ { flag1=0; j=boatcase(q->data,c); for (i=0;i 第2章知识表示方法部分参考答案 2.8设有如下语句，请用相应的谓词公式分别把他们表示出来： (1)有的人喜欢梅花，有的人喜欢菊花，有的人既喜欢梅花又喜欢菊花。 解：定义谓词 P(x)：x是人 L(x,y)：x喜欢y 其中，y的个体域是{梅花，菊花}。 将知识用谓词表示为： (?x )(P(x)→L(x, 梅花)∨L(x, 菊花)∨L(x, 梅花)∧L(x, 菊花)) (2) 有人每天下午都去打篮球。 解：定义谓词 P(x)：x是人 B(x)：x打篮球 A(y)：y是下午 将知识用谓词表示为： (?x )(?y) (A(y)→B(x)∧P(x)) (3)新型计算机速度又快，存储容量又大。 解：定义谓词 NC(x)：x是新型计算机 F(x)：x速度快 B(x)：x容量大 将知识用谓词表示为： (?x) (NC(x)→F(x)∧B(x)) (4) 不是每个计算机系的学生都喜欢在计算机上编程序。 解：定义谓词 S(x)：x是计算机系学生 L(x, pragramming)：x喜欢编程序 U(x,computer)：x使用计算机 将知识用谓词表示为： ?(?x) (S(x)→L(x, pragramming)∧U(x,computer)) (5)凡是喜欢编程序的人都喜欢计算机。 解：定义谓词 P(x)：x是人 L(x, y)：x喜欢y 将知识用谓词表示为： (?x) (P(x)∧L(x,pragramming)→L(x, computer)) 2.9用谓词表示法求解机器人摞积木问题。设机器人有一只机械手，要处理的世界有一张桌子，桌上可堆放若干相同的方积木块。机械手有4个操作积木的典型动作：从桌上拣起一块积木；将手中的积木放到桌之上；在积木上再摞上一块积木；从积木上面拣起一块积木。积木世界的布局如下图所示。 图机器人摞积木问题 解：(1) 先定义描述状态的谓词 CLEAR(x)：积木x上面是空的。 ON(x, y)：积木x在积木y的上面。 ONTABLE(x)：积木x在桌子上。 HOLDING(x)：机械手抓住x。 HANDEMPTY：机械手是空的。 其中，x和y的个体域都是{A, B, C}。 问题的初始状态是： ONTABLE(A) ONTABLE(B) ON(C, A) CLEAR(B) CLEAR(C) HANDEMPTY 问题的目标状态是： ONTABLE(C) ON(B, C) ON(A, B) CLEAR(A) HANDEMPTY (2) 再定义描述操作的谓词 在本问题中，机械手的操作需要定义以下4个谓词： Pickup(x)：从桌面上拣起一块积木x。 Putdown(x)：将手中的积木放到桌面上。 Stack(x, y)：在积木x上面再摞上一块积木y。 Upstack(x, y)：从积木x上面拣起一块积木y。 其中，每一个操作都可分为条件和动作两部分，具体描述如下： 一、将下面的公式化成Skolem标准型 (?x) ((?y) P(x,y)→～(?y)(Q(x,y)→R(x,y))) 将下式化为Skolem标准形： ～(?x)(?y)P(a, x, y) →(?x)(～(?y)Q(y, b)→R(x)) 解：第一步，消去→号，得： ～(～(?x)(?y)P(a, x, y)) ∨(?x) (～～(?y)Q(y, b)∨R(x)) 第二步，～深入到量词内部，得： (?x)(?y)P(a, x, y) ∨(?x) ((?y)Q(y, b)∨R(x)) 第三步，变元易名，得 (?x)((?y)P(a, x, y) ∨(?u) (? v)(Q(v, b) ∨R(u)) 第四步，存在量词左移，直至所有的量词移到前面，得： (?x) (?y) (?u) (? v)P(a, x, y) ∨(Q(v, b) ∨R(u)) 由此得到前束范式 第五步，消去“?”（存在量词），略去“?”任意量词 消去(?y)，因为它左边只有(?x)，所以使用x的函数f(x)代替之，这样得到：(?x)(?z)( P(a, x, f(x)) ∧～Q(z, b)∧～R(x)) 消去(?z)，同理使用g(x)代替之，这样得到： (?x) ( P(a, x, f(x)) ∧～Q(g(x), b)∧～R(x)) 则，略去任意变量，原式的Skolem标准形为： P(a, x, f(x)) ∧～Q(g(x), b)∧～R(x) 二、谓词表示法表示修道士和野人渡河问题 修道士和野人渡河问题：在河左岸有三个修道士、三个野人河一条船，修道士要把所有的人都运到河对岸，但是 a) 修道士和野人都会划船，但是船一次只能装两个人 b) 在两个岸边，野人数目不能超过修道士的数目，否则后者被吃掉野人完全服从修道士的任何渡河方案。试图求出一种确保修道士安全的渡河方案。要写出谓词的定义，功能和变量的个体域。（提示：写出必须的谓词和初始状态，修道士cenobite野人wildness） 三、下列子句是否可以合一，如果可以，写出最一般合一置换 a) P(x, B, B) 和 P(A, y, z) b) P( g( f (v)) , g(u) ) 和 P(x , x) c) P( x , f(x) ) 和 P(y, y) d) P(y, y , B) 和 P( z, x , z) e) P(f(a) , g(x)) 和 P(y , y) 不能合一 f) P(a , x , f(g(y))) 和 P(z , h(z , u) , f(u)) 可以合一，最一般合一置换σ3＝{a/z , h(a , g(y))/x , g(y)/u} 1.上机内容 传教士与野人问题求解（宽度搜索算法） 二问题背景： 从前有一条河，河的左岸有m个传教士(Missionary)和m个野人(Cannibal)，和一艘最多可乘n人的小船。约定左岸，右岸和船上或者没有传教士，或者野人数量少于传教士，否则野人会把传教士吃掉。 三实验内容： 编程，接收m和n，搜索一条可让所有的野人和传教士安全渡到右岸的方案，例如下图: （M表示传教士(Missionary)，C 表示野人(Cannibal)） 初态目标 Left Bank River Right bank Left Bank River Right bank M…. M…. C…. C…. 注：本实验的举例均以3个传教士和3个野人同在左岸作为初始状态。 四实验方案和算法： 1．数据结构： 本实验需要用到的数据结构主要是队列和堆栈，其实现均包含于dso.h头文件中，分别命名为class stack和class queue。 2．宽度搜索算法： (1)结点结构： class Move { public: int missionary; //要移动的传教士数量 int cannibal; //野人 }; class ElemType : Move { //继承Move类，获得传教士，野人数据成员。 private: bool boat; //船是否在左岸？ public: ElemType* flag; //标示前一状态即扩展出本结点的父结点信息 ElemType(int MAX_PEOPLE) { //创建初始状态 missionary = cannibal = MAX_PEOPLE; boat = true; flag = NULL; } …… 在这里，Elemtype集成了Move，从而获得Move类的传教士和野人数据成员。以上两个类的数据成员用于保存所有扩展生成的结点。其中missionary表示表示左岸上传教士的树目，cannibal表示左岸上野人的树目，boat表示船在哪个岸上（其中true表示在左岸，这是船的初始状态，表示false在右岸）， flag 用于标示前一状态即扩展出本结点的父结点信息，以便最后回搜找出解的 路径。 举例说明：假设左岸有3个传教士和3个野人，小船最多可乘2人。把当前左岸的状态抽象为：(3,3,1)，前两个"3"代表左岸有3个传教士和3个野人，1代表船在左岸。很明显，目标状态为(0,0,0),表示左岸的传教士和也人数目都是0，而船在右岸。 (2)船的行动规则（successor function）: 把每一次可行的渡船方案作为行动规则，用Move类的（m,c）表示。行动规则的两位数分别代表要移动的传教士，野人的数量。对于固定大小的船，其装载能力是一定的，所以它的行动规则空间也是一定的。在这里，用MoveGroup类的构造函数构造出所有的行动规则。 注意，这里MoveGroup类中的Move对象只有500的可用空间，所以，输入的传教士和野人数目构成的行动规则不能超过500种。 (3)宽度优先算法： 实验的主要搜索算法由ANSWER类的构造函数实现，这里主要用到了OPEN和CLOSED队列，以及一个临时的TEMP堆栈。其中，OPEN表用于存放扩展结点，CLOSED表用于存放被扩展结点，TEMP则用于用于记录成功搜索的路径。 搜索过程大致如下描述：先构造初始结点以及船的行动规则，初始结点入OPEN队列，以宽度优先依次搜索OPEN队列头结点的子结点，同时保存受访问结点的父结点信息，知道搜索到目标结点或者无解为止。 算法框图如下所示： 江南大学物联网工程学院实验报告 课程名称人工智能实验名称A*算法解决8数码问题实验日期2018.3.20 班级计科1501 姓名周启航学号1030415127 一、实验目的： 问题描述：设有3个传教士和3个野人来到河边，打算乘一只船从左岸渡到右岸去。该船的负载能力为两人。在任何时候，如果野人人数超过传教士人数，那么野人就会把传教士吃掉。他们怎样才能用这条船安全地把所有人都渡河过去？试采用A*算法编一程序实现这一搜索过程。 二、算法描述： 1.状态描述 以河岸左边传教士的数目M，野人的数目C，船是否在B作为一个三元组作为一个状态即（M，C，B）。 2.启发函数设计 以现在的状态到目的状态所需的最少步数作为启发函数，即为h()=M+C-2*B。 3.规则的判断条件 岸边传教士不能少于野人个数，即M>=C,或者M=0，船在左岸时B=1。 4.算法流程图 5.核心代码 操作算子： void Astar() { while(!Q.empty()) Q.pop(); PathNode.clear(); memset(st, -1, sizeof(st)); PathNode.push_back(Node(M, C, B, 0, -1)); Q.push(AstarNode(0, PathNode[0])); st[M][C][B] = 0; int m, c, b, flag, id; while(!Q.empty()) { AstarNode as = Q.top(); Q.pop(); //printf("----%d %d %d %d %d----\n", as.f, as.g, as.node.m, as.node.c, as.node.b); if(as.node.m == 0 && as.node.c == 0) { printf("渡河方案如下：\n"); printf(" (M, C, B)\n"); printPath(as.node.id); printf("可以安全渡河，来回最少需%d 次便可!\n", as.g); Safe = true; return; } if(as.node.b == 1) flag = -1; else flag = 1; b = 1 - as.node.b; id = PathNode.size() - 1; for(int i = 0; i < 5; ++i) { m = as.node.m + flag * add[i][0]; c = as.node.c + flag * add[i][1]; if(OK(m, c, b)) { ++id; st[m][c][b] = as.g + 1; PathNode.push_back(Node(m, c, b, id, as.node.id)); Q.push(AstarNode(as.g + 1, PathNode[id])); } } } } 主函数： int main(int argc, char *argv[]) { int i=3; 修道士与野人问题 6．修道士与野人问题 这是一个古典问题。假设有n个修道士和n个野人准备渡河，但只有一条能容纳c人的小船，为了防止野人侵犯修道士，要求无论在何处，修道士的个数不得少于野人的人数（除非修道士个数为0）。如果两种人都会划船，试设计一个算法，确定他们能否渡过河去，若能，则给出一个小船来回次数最少的最佳方案。 要求： （1）用一个三元组（x1,x2,x3）表示渡河过程中各个状态。其中，x1表示起始岸上修道士个数，x2表示起始岸上野人个数，x3表示小船位置（0——在目的岸，1——在起始岸）。例如（2,1,1）表示起始岸上有两个修道士，一个野人，小船在起始岸一边。 采用邻接表做为存储结构，将各种状态之间的迁移图保存下来。 （2）采用广度搜索法，得到首先搜索到的边数最少的一条通路。 （3）输出数据 若问题有解（能渡过河去），则输出一个最佳方案。用三元组表示渡河过程中的状态，并用箭头指出这些状态之间的迁移： 目的状态←…中间状态←…初始状态。 若问题无解，则给出“渡河失败”的信息。 （4）求出所有的解。 1．需求分析 有n个修道士和n个野人准备渡河，但只有一条能容纳c人的小船，为了防止野人侵犯修道士，要求无论在何处，修道士的个数不得少于野人的人数,否 则修道士就会有危险，设计一个算法，确定他们能否渡过河去，若能，则给出一个小船来回次数最少的最佳方案。用三元组（x1,x2,x3）来表示渡河过程中各个状态，其中，x1表示起始岸上修道士个数，x2表示起始岸上野人个数，x3表示小船位置（0——在目的岸，1——在起始岸）。若问题有解（能渡过河去），则输出一个最佳方案。用三元组表示渡河过程中的状态，并用箭头指出这些状态之间的迁移：目的状态←…中间状态←…初始状态，若问题无解，则给出“渡河失败”的信息。 2．设计 2.1 设计思想 （1）数据结构设计 逻辑结构设计: 图型结构 存储结构设计: 链式存储结构 采用这种数据结构的好处：便于采用广度搜索法，得到首先搜索到的边数最少的一条通路，输出一个最佳方案，采用图的邻接表存储结构搜索效率较高。 （2）算法设计 算法设计的总体设计思路为：在得到修道士人数和小船的容纳人数后，用boatcase得到所有情况，然后再进行安全性检查，以减去修道士少于野人的情况，接着用孩子兄弟结点表示法，将去对面的路作为孩子结点，路与路是兄弟 实验 传教士野人过河问题 37030602 王世婷 一、实验问题 传教士和食人者问题（The Missionaries and Cannibals Problem ）。在河的左岸有3个传教士、1条船和3个食人者，传教士们想用这条船将所有的成员运过河去，但是受到以下条件的限制：（1）传教士和食人者都会划船，但船一次最多只能装运两个；（2）在任何岸边食人者数目都不得超过传教士，否则传教士就会遭遇危险：被食人者攻击甚至被吃掉。此外，假定食人者会服从任何一种过河安排，试规划出一个确保全部成员安全过河的计划。 二、解答步骤 (1) 设置状态变量并确定值域 M 为传教士人数，C 为野人人数，B 为船数，要求M>=C 且M+C <= 3，L 表示左岸，R 表示右岸。 初始状态 目标状态 L R L R M 3 0 M 0 3 C 3 0 C 0 3 B 1 0 B 0 1 (2) 确定状态组，分别列出初始状态集和目标状态集 用三元组来表示f S ：（ML , CL , BL ）（均为左岸状态） 其中03,03ML CL ≤≤≤≤,BL ∈{ 0 , 1} 0S ：(3 , 3 , 1) g S ： (0 , 0 , 0) 初始状态表示全部成员在河的的左岸； 目标状态表示全部成员从河的左岸全部渡河完毕。 (3) 定义并确定规则集合 仍然以河的左岸为基点来考虑，把船从左岸划向右岸定义为Pij 操作。其中，第一下标i 表示船载的传教士数，第二下标j 表示船载的食人者数；同理，从右岸将船划回左岸称之为Qij 操作，下标的定义同前。则共有10种操作，操作集为 F={P01，P10，P11，P02，P20，Q01，Q10，Q11，Q02，Q20} P 10 if ( ML ,CL , BL=1 ) then ( ML –1 , CL , BL –1 ) P 01 if ( ML ,CL , BL=1 ) then ( ML , CL –1 , BL –1 ) P 11 if ( ML ,CL , BL=1 ) then ( ML –1 , CL –1 , BL –1 ) P 20 if ( ML ,CL , BL=1 ) then ( ML –2 , CL , BL –1 ) P 02 if ( ML ,CL , BL=1 ) then ( ML , CL –2 , BL –1 ) Q 10 if ( ML ,CL , BL=0 ) then ( ML+1 , CL , BL+1 ) Q 01 if ( ML ,CL , BL=0 ) then ( ML , CL+1 , BL +1 ) Q 11 if ( ML ,CL , BL=0 ) then ( ML+1 , CL +1, BL +1 ) 2010-2011学年第2学期考试试题 （ A ）卷 课程名称 《人工智能》 任课教师签名 出题教师签名 审题教师签名 考试方式 （ 闭 ）卷 适用专业 智能1,2 考试时间 （ 120 ）分钟 一、 填空题（每小题5分，共25 分） 1. 用谓词逻辑表示知识“所有教师都有自己的学生”,( 定义谓词：T (x)：表示x 是教师;S (y)：表示y 是学生;TS(x, y)：表示x 是y 的老师) ； 2.用产生式表示知识“王峰热爱祖国” ； 3. 用语义网络法表示知识“雪的颜色是白的” ； 4. 把下列谓词公式化成子句集：(?x)(?y)(P(x, y)∨(Q(x, y)→R(x, y))) 5. 判断下列子句集中哪些是不可满足的：{ P ∨Q , ?P ∨Q, P ∨?Q, ?P ∨?Q } 二．名词解释（每小题5分，共10分） 估价函数 人工神经元 三.计算题（第1小题10分，其余每小题15分共55分） 1. 用语义网络法表示事实:每个学生都学习c++语言。 2. 用谓词表示法求解修道士和野人问题。在河的北岸有三个修道士、三个 野人和一条船，修道士们想用这条船将所有的人都运过河去，但要受到以 下条件限制： (1) 修道士和野人都会划船，但船一次只能装运两个人。 (2) 在任何岸边，野人数不能超过修道士，否则修道士会被野人吃掉。 假定野人愿意服从任何一种过河安排，请规划出一种确保修道士安全的过河方案。要求写出所用谓词的定义、功能及变量的个体域。 3．用谓词逻辑的归结原理求证：李明过着激动人心的生活。假设：所有不 贫穷并且聪明的人都是快乐的，那些看书的人是聪明的。李明能看书且不贫穷，快乐的人过着激动人心的生活。 4.自立估价函数，用A 或A * 算法给出下图的启发信息优先搜索树。 初始棋局：目标棋局： 四．简述专家系统的开发步骤（每小题10分，共10 分） 状态空间法详解传教士和野人问题 传教士和野人问题（The Missionaries and Cannibals Problem） 在河的左岸有三个传教士、一条船和三个野人，传教士们想用这条船将所有的成员都运过河去，但是受到以下条件的限制： ①教士和野人都会划船，但船一次最多只能装运两个； ②②在任何岸边野人数目都不得超过传教士，否则传教士就会遭遇危险：被野人攻击甚至被吃掉。 此外，假定野人会服从任何一种过河安排，试规划出一个确保全部成员安全过河的计划。（1）设定状态变量及确定值域。 为了建立这个问题的状态空间，设左岸传教士数为m，则 m ={0,1,2,3}； 对应右岸的传教士数为3－m；左岸的野人数为c，则有 c ={0,1,2,3}； 对应右岸野人数为3－c；左岸船数为b，故又有b={0,1}，右岸的船数为1－b. （2）确定状态组，分别列出初始状态集和目标状态集。 问题的状态可以用一个三元数组来描述，以左岸的状态来标记，即 Sk =（m,c,b）， 右岸的状态可以不必标出。 初始状态一个：S0 =（3,3,1），初始状态表示全部成员在河的左岸； 目标状态也只一个：Sg =（0,0,0），表示全部成员从河左岸渡河完毕。 （3）定义并确定操作集。 仍然以河的左岸为基点来考虑，把船从左岸划向右岸定义为Pij操作。其中,第一下标i表示船载的传教士数, 第二下标j表示船载的野人数；同理，从右岸将船划回左岸称之为Qij 操作，下标的定义同前。则共有10种操作，操作集为 F={P01，P10，P11，P02，P20，Q01，Q10，Q11，Q02，Q20} （4）估计全部的状态空间数，并尽可能列出全部的状态空间或予以描述之。 在这个问题世界中，S0 =（3,3,1）为初始状态，S31 = Sg =（0,0,0）为目标状态。全部的可能状态共有32个，如表所示。 表1 传教士和野人问题的全部可能状态 注意：按题目规定条件，应划去非法状态，从而加快搜索效率。 1）首先可以划去左岸边野人数目超过传教士的情况，即S4、S8、S9、S20、S24、S25等6种状态是不合法的； 2）应划去右岸边野人数目超过修道士的情况，即S6、S7、S11、S22、S23、S27等情况； 3）应划去4种不可能出现状态：划去S15和S16——船不可能停靠在无人的岸边；划去S3——传教士不可能在数量占优势的野人眼皮底下把船安全地划回来；划去S28——传教士也不可能在数量占优势的野人眼皮底下把船安全地划向对岸。可见，在状态空间中，真正符合题目规定条件的只有16个合理状态。 （5）当状态数量不是很大时，按问题的有序元组画出状态空间图，依照状态空间图搜索求解。 题号题目3、修道士与野人问题 1、需求分析 n个修道士和n个野人渡河，只有一条小船，能容纳c人，两种人都会划船，建立过河方式。满足： 野人无法侵犯修道士。这就要求无论在何处，修道士的个数不得少于野人的人数（除非修道士个数为0）。设计程序模拟该过程。 程序的输入为修道士（野人）的个数以及每条船容纳人的个数。输出为判断是否可以安全渡河。如果能，则给出一个小船来回次数最少的最佳方案。 要求： （1）用一个三元组（x1,x2,x3）表示渡河过程中各个状态。其中，x1表示起始岸上修道士个数，x2表示起始岸上野人个数，x3表示小船位置（0——在目的岸，1——在起始岸）。例如（5，3，0）表示起始岸上有5个修道士，3个野人，小船在目的岸一边。 （2）采用邻接表做为存储结构。最短路径搜索采用广度搜索法。 （3）输出最优解 若问题有解（能渡过河去），则输出一个最佳方案。用三元组表示渡河过程中的状态，并用箭头指出这些状态之间的迁移： 目的状态←…中间状态←…初始状态。 若问题无解，则给出“渡河失败”的信息。 （4）求出所有的解。 2、设计 2.1设计思想 （1）数据结构设计：根据题目要求，用图形结构，用邻接表来存储结点，以及结点之间的关系，同时在广度优先遍历中利用到队列。 （2）算法设计：先定义一个图利用邻接表储存结构，再举出在船上修道士和野人的所有情况，然后判断其修道士是否处于安全的状态，如果安全则将该点添加到图中，点添加完后在看两点之间是否连通如果连通则可将边添加到图中，这样就创建出了图，然后分别利用广度搜索和深度搜索来完成题目的要求。 2.2 （1 （2）函数接口规则说明 int Search(AdjLGraph *G,int x,int y,int m ) /*查找起始和最后的结点，其中x,y,m分别表示起始岸修道士人数，野人人数和船的状态*/ int Checking(DataType x) /*检查修道士是否安全,x表示邻接表中的一个结点*/ int Connect(AdjLGraph *G,int i,int j) /*将能走通的点连接起来，i，j为图中的两个结点*/ void Creat(AdjLGraph *G) /*图的创建*/ int Print(AdjLGraph G) /*从后向前打印最短路径*/ int BroadFSearch(AdjLGraph G,int u,int v) /*用广度优先遍历搜索最短路径，u表示起始结点，v表示最后的结点*/ void Print1(AdjLGraph G) /*打印输出所有最短路径*/ void DFS(AdjLGraph G,int u,int v ,int visited[]) /*利用深度搜索找出所有最短路径，u表示起始结点，v表示最后的结点，visited[]用来标记结点是否被访问*/ 2.3详细设计 首先是定义邻接表 typedef struct { int daoshi; //道士 int yeren; //野人 int ship; //船的位置 }DataType; typedef struct Node //边结点的结构体 { int dest; //邻接边的弧头顶点序号 struct Node *next; //单链表的下一个结点指针 }Edge; typedef struct { DataType data; //顶点数据元素 int source; //弧尾顶点序号 Edge *adj; //邻接边的头指针 }AdjLHeight; typedef struct { AdjLHeight a[200]; //邻接表数组 int numOfVerts; //顶点个数 int numOfEdges; //边个数 }AdjLGraph; //邻接表结构体 同时定义了几个全局变量，便于函数的直接利用 int n,c;//修道士和野人人数为n，船能容纳人数为c int Path[200]; //保存结点的后驱结点 int Path1[200]; //保存结点的前驱结点 利用上述结构和相关函数可以构造出图，然后对图进行利用； 然后在广度优先遍历搜索中用到了队列 //而对于函数qq(int& a)，这是C++中引入的一个新类型：引用，所带来的新的函数传值方式，即按引用传值。 #include 修道士与野人问题 6(修道士与野人问题 这是一个古典问题。假设有n个修道士和n个野人准备渡河，但只有一条能容纳c人的小船，为了防止野人侵犯修道士，要求无论在何处，修道士的个数不得少于野人的人数(除非修道士个数为0)。如果两种人都会划船，试设计一个算法，确定他们能否渡过河去，若能，则给出一个小船来回次数最少的最佳方案。 要求: (1)用一个三元组(x1,x2,x3)表示渡河过程中各个状态。其中，x1表示起始岸上修道士个数，x2表示起始岸上野人个数，x3表示小船位置(0——在目的岸，1——在起始岸)。例如(2,1,1)表示起始岸上有两个修道士，一个野人，小船在起始岸一边。 采用邻接表做为存储结构，将各种状态之间的迁移图保存下来。 (2)采用广度搜索法，得到首先搜索到的边数最少的一条通路。 (3)输出数据 若问题有解(能渡过河去)，则输出一个最佳方案。用三元组表示渡河过程中的状态，并用箭头指出这些状态之间的迁移: 目的状态?…中间状态?…初始状态。 若问题无解，则给出“渡河失败”的信息。 (4)求出所有的解。 1(需求分析 有n个修道士和n个野人准备渡河，但只有一条能容纳c人的小船，为了防止野人侵犯修道士，要求无论在何处，修道士的个数不得少于野人的人数,否则修道士就会有危险，设计一个算法，确定他们能否渡过河去，若能，则给出一个小船来 回次数最少的最佳方案。用三元组(x1,x2,x3)来表示渡河过程中各个状态，其中，x1表示起始岸上修道士个数，x2表示起始岸上野人个数，x3表示小船位置(0——在目的岸，1——在起始岸)。若问题有解(能渡过河去)，则输出一个最佳方案。用三元组表示渡河过程中的状态，并用箭头指出这些状态之间的迁移:目的状态?…中间状态?…初始状态，若问题无解，则给出“渡河失败”的信息。 2(设计 2.1 设计思想 (1)数据结构设计 逻辑结构设计: 图型结构 存储结构设计: 链式存储结构 采用这种数据结构的好处:便于采用广度搜索法，得到首先搜索到的边数最少的一条通路，输出一个最佳方案，采用图的邻接表存储结构搜索效率较高。 (2)算法设计 算法设计的总体设计思路为:在得到修道士人数和小船的容纳人数后，用boatcase得到 所有情况，然后再进行安全性检查，以减去修道士少于野人的情况，接着用孩子兄弟结点表示法，将去对面的路作为孩子结点，路与路是兄弟关系，到达另一边时，同样以这种方法，直到找到(0，0,0)。主要分为4个模块:boatcase生成所有情况，BFS得到边数最少的最佳方案，safe安全性检测，print输出安全渡河的全过程。 各个模块要完成的主要功能分别为: 生成模块:生成所有的可能渡河情况 安全检测模块:对所有的可能渡河情况进行安全检测，，以减去修道士少于野人的情况 有N个传教士和N个野人来到河边渡河,河岸有一条船,每次至多可供k人乘渡。问传教士为了安全起见,应如何规划摆渡方案,使得任何时刻,河两岸以及船上的野人数目总是不超过传教士的数目(否则不安全,传教士有可能被野人吃掉)。即求解传教士和野人从左岸全部摆渡到右岸的过程中,任何时刻满足M(传教士数)≥C(野人数)和M+C≤k的摆渡方案。 我们此处举例,只讨论N为3、k为2的乘渡问题,这样传教士和野人问题的描述就具体为如下: 三个传教士与三个野人来到河边,有一条船可供一人或两人乘渡,问题是如何用这条船渡河才能使得河的任一岸上野人的数目总不超过传教士的数目(当然,如果某一岸上只有野人而没有传教士是允许的)? 我们用一个三元组(m c b)来表示河岸上的状态,其中m、c分别代表某一岸上传教士与野人的数目,b=1表示船在这一岸,b=0则表示船不在。 设N=3,k=2,则给定的问题可用下图表示,图中L和R表示左岸和右岸,B=1或0分别表示有船或无船。约束条件是:两岸上M≥C,船上M+C≤2。 我们采用产生式系统来解决这一问题。由于传教士与野人的总数目是一常数,所以只要表示出河的某一岸上的情况就可以了,为方便起见,我们选择传教士与野人开始所在的岸为所要表示的岸,并称其为左岸,另一岸称为右岸。但显然仅用描述左岸的三元组描述就足以表示出整个情况,因此必须十分重视选择较好的问题表示法。以后的讨论还可以看到高效率的问题求解过程与控制策略有关,合适的控制策略可缩小状态空间的搜索范围,提高求解的效率。因而问题的初始状态是(331),目标状态是(000)。 (1)综合数据库:用三元组表示,即(ML,CL,BL),其中0≤ML,CL≤3,BL∈{0,1} 此时问题述简化为(3,3,1)®(0,0,0) N=3的M-C问题,状态空间的总状态数为4×4×2=32,根据约束条件的要求,可以看出只有20个合法状态。再进一步分析后,又发现有4个合法状态实际上是不可能达到的。因此实际的问题空间仅由16个状态构成。下表列出分析的结果: (ML,CL,BL)(ML,CL,BL) (001)达不到(000) (011)(010) (021)(020) (031)(030)达不到 (101)不合法(100)不合法 (111)(110) (121)不合法(120)不合法 (131)不合法(130)不合法 (201)不合法(200)不合法 (211)不合法(210)不合法 (221)(220) (231)不合法(230)不合法 (301)达不到(300) (311)(310) (321)(320) (331)(330)达不到 (2)规则集合:由摆渡操作组成。该问题主要有两种操作:pmc操作(规定为从左岸划向右岸)和qmc操作(从右岸划向左岸)。每次摆渡操作,船上人数有五种组合,因而组成有10条规则的集合。下面定义的规则前5条为pmc操作(从左岸划向右岸),后5条为qmc操作(从右岸划向左岸)。 if(ML,CL,BL=1)then(ML-1,CL,BL-1);(p10操作) if(ML,CL,BL=1)then(ML,CL-1,BL-1);(p01操作) if(ML,CL,BL=1)then(ML-1,CL-1,BL-1);(p11操作) 传教士与野人过河问题实验报告 1 问题定义 河的两岸有三个传教士和三个野人需要过河，目前只有一条能装下两个人的船，在河的任何一方或者船上，如果野人的人数大于传教士的人数，那么传教士就会被野人攻击，怎么找出一种安全的渡河方案呢 2 算法分析 首先，先来看看问题的初始状态和目标状态，定义河的两岸分别为左岸和右岸，设定状态集合为（左岸传教士人数，右岸野人数，右岸传教士人数，右岸野人数，船的位置），船的位置：-1表示船在左岸，1表示船在右岸。 初始状态：（3,3,0,0,0，-1） 目标状态：（0，0，3，3，1） 然后，整个问题就抽象成了怎样从初始状态经中间的一系列状态达到目标状态。问题状态的改变是通过划船渡河来引发的，所以合理的渡河操作就成了通常所说的算符，根据题目要求，可以得出以下5个算符（按照渡船方向的不同，也可以理解为10个算符）：渡1野人、渡1传教士、渡1野人1传教士、渡2野人、渡2传教士 根据船的位置，向左移或向右移通过递归依次执行5种算符，判断是否找到所求，并排除不符合实际的状态，就可以找到所有可能的解，如图1所示为递归函数流程图。 数据结构方面采用如下所示的结构体存储当前传教士、野人、船三者的状态。 struct riverSides { int churchL;ildL == &&lastParameters[i].churchL == { if == lastParameters[i].boat) return 0; } } //检验人数数据合法性 if < 0 || < 0 || < 0 || < 0) return 0; //传教士是否被吃 if ( < && != 0) || < && != 0)) return 0; C实现传教士与野人过河问题实验报告 Document serial number【LGGKGB-LGG98YT-LGGT8CB-LGUT- 传教士与野人过河问题实验报告 1 问题定义 河的两岸有三个传教士和三个野人需要过河，目前只有一条能装下两个人的船，在河的任何一方或者船上，如果野人的人数大于传教士的人数，那么传教士就会被野人攻击，怎么找出一种安全的渡河方案呢 2 算法分析 首先，先来看看问题的初始状态和目标状态，定义河的两岸分别为左岸和右岸，设定状态集合为（左岸传教士人数，右岸野人数，右岸传教士人数，右岸野人数，船的位置），船的位置：-1表示船在左岸，1表示船在右岸。 初始状态：（3,3,0,0,0，-1） 目标状态：（0，0，3，3，1） 然后，整个问题就抽象成了怎样从初始状态经中间的一系列状态达到目标状态。问题状态的改变是通过划船渡河来引发的，所以合理的渡河操作就成了通常所说的算符，根据题目要求，可以得出以下5个算符（按照渡船方向的不同，也可以理解为10个算符）： 渡1野人、渡1传教士、渡1野人1传教士、渡2野人、渡2传教士 根据船的位置，向左移或向右移通过递归依次执行5种算符，判断是否找到所求，并排除不符合实际的状态，就可以找到所有可能的解，如图1所示为递归函数流程图。 数据结构方面采用如下所示的结构体存储当前传教士、野人、船三者的状态。 struct riverSides { int churchL;ildL == &&lastParameters[i].churchL == { if == lastParameters[i].boat) return 0; } } //检验人数数据合法性 if < 0 || < 0 || < 0 || < 0) return 0; //传教士是否被吃 传教士-野人问题 有N个传教士和N个野人要过河，现在有一条船只能承载K个人（包括野人），K 贵州航天职业技术学院《C语言程序设计》 系别: __计算机科学系 _________ 班级: __10级软件技术_________ 姓名: _______________________ 指导教师: ___陆树芬_______________ 小组成员: ___翟奇张源李雪_______ 前言 C语言作为一门最通用的语言，在过去很流行，将来依然会如此。几乎每一个理工科或者其他专业的学生毫不例外地要学习它。从C 语言产生到现在，它已经成为最重要和最流行的编程语言之一。在各种流行编程语言中，都能看到C语言的影子，如Java的语法与C 语言基本相同。学习、掌握C语言是每一个计算机技术人员的基本功之一。C语言具有高级语言的强大功能，却又有很多直接操作计算机硬件的功能（这些都是汇编语言的功能），因此，C语言通常又被称为中级语言。学习和掌握C语言，既可以增进对于计算机底层工作机制的了解，又为进一步学习其他高级语言打下了坚实的基础。本大作业是对学生在课堂上所学知识的一次综合检测。通过本次大作业的制作，应能综合使用在《C语言程序设计》课程中学到的多种基础知识，并可以很好的应用到实际操作中去，具备简单的项目设计能力。 本大作业主要以传教士和野人怎样从河的一岸完全渡到另一岸，而不发生野人吃掉传教士这一问题展开，主要使用C语言中的链表应用完成程序的设计，将此次程序设计报告分为以下几点： 1. 问题的描述：描述本程序的设计内容； 2. 问题分析：介绍此程序设计的结构和算法分析 3. 程序设计流程图 4. 程序各个功能模块的实现 5. 程序运行结果：将各种情况下的运行结果通过屏幕截取下来 6. 程序设计结论：描述本次程序设计的一些体会和在程序设计过 程中所获得的一些知识以及本次程序设计所存在的不足和缺陷。 7. 完成本次程序设计所翻阅的资料修道士与野人问题
人工智能导论课参考答案第2章
人工智能复习题
传教士和野人问题实验报告
AStar算法解决野人渡河问题
修道士与野人问题教学文案
传教士野人过河问题-两种解法思路
2011《人工智能》试卷A及答案
传教士和野人问题
数据结构课程设计--修道士野人问题和西文图书管理系统
人工智能里野人和传教士问题代码
修道士与野人问题
有N个传教士和N个野人来到河边渡河
C实现传教士与野人过河问题实验报告
C实现传教士与野人过河问题实验报告
人工智能 野人和传教士问题
传教士与野人过河问题
- 人工智能导论课参考答案第2章
- 《人工智能》试卷A及答案
- 人工智能导论课参考答案第2章
- 人工智能：野人与修道士问题
- 人工智能习题
- 数据结构课程设计--修道士野人问题和西文图书管理系统
- 传教士与野人
- 传教士_野人问题参考答案
- (整理)传教士野人问题参考答案
- 修道士与野人问题教学文案
- 《人工智能》试卷A及答案
- 人工智能 野人和传教士问题
- 人工智能：野人与修道士问题
- 知识表示方法部分参考答案
- 修道士与野人问题
- 传教士与食人魔过河
- 传教士和野人问题
- 苏州大学人工智能复习AI Ultimate Edition Part2
- 人工智能原理与应用 (张仰森 著) 高等教育出版社 课后答案
- 传教士野人过河问题-两种解法思路