搜档网
当前位置:搜档网 › 传教士与野人过河问题

传教士与野人过河问题

传教士与野人过河问题
传教士与野人过河问题

贵州航天职业技术学院《C语言程序设计》

系别: __计算机科学系 _________

班级: __10级软件技术_________

姓名: _______________________

指导教师: ___陆树芬_______________

小组成员: ___翟奇张源李雪_______

前言

C语言作为一门最通用的语言,在过去很流行,将来依然会如此。几乎每一个理工科或者其他专业的学生毫不例外地要学习它。从C 语言产生到现在,它已经成为最重要和最流行的编程语言之一。在各种流行编程语言中,都能看到C语言的影子,如Java的语法与C 语言基本相同。学习、掌握C语言是每一个计算机技术人员的基本功之一。C语言具有高级语言的强大功能,却又有很多直接操作计算机硬件的功能(这些都是汇编语言的功能),因此,C语言通常又被称为中级语言。学习和掌握C语言,既可以增进对于计算机底层工作机制的了解,又为进一步学习其他高级语言打下了坚实的基础。本大作业是对学生在课堂上所学知识的一次综合检测。通过本次大作业的制作,应能综合使用在《C语言程序设计》课程中学到的多种基础知识,并可以很好的应用到实际操作中去,具备简单的项目设计能力。

本大作业主要以传教士和野人怎样从河的一岸完全渡到另一岸,而不发生野人吃掉传教士这一问题展开,主要使用C语言中的链表应用完成程序的设计,将此次程序设计报告分为以下几点:

1. 问题的描述:描述本程序的设计内容;

2. 问题分析:介绍此程序设计的结构和算法分析

3. 程序设计流程图

4. 程序各个功能模块的实现

5. 程序运行结果:将各种情况下的运行结果通过屏幕截取下来

6. 程序设计结论:描述本次程序设计的一些体会和在程序设计过

程中所获得的一些知识以及本次程序设计所存在的不足和缺陷。

7. 完成本次程序设计所翻阅的资料

目录

一.问题描述 ------------------------------------------------------------ 5

二.问题分析 ------------------------------------------------------------ 5

三.主要流程图 --------------------------------------------------------- 7

四. 基本数据类型声明及数据结构-------------------------------- 8

五. 程序主要实现说明及设置-------------------------------------- 9六.运行结果------------------------------------------------------- 19

七. 实验结论 ------------------------------------------------------- 25

八.参考文献 ---------------------------------------------------------- 27

一.问题描述

有M个传教士和N个野人来到河边准备渡河,河岸有一条船,每次至多可供k人乘渡。任何时刻在河的两岸以及船上的野人数目总是不超过传教士的数目。

二.问题分析

1.定义节点的结构:以取船的一个来回作为一步搜索,这样节点可由下面几个量进行描述:两岸的传教士人数和野人人数、船上的传教士人数和野人人数,由初始节点搜索几步后到达本节点。需要注意的是并不是所有节点都是可达的,题目中对可达节点作出了限制,只有两岸上的人数必须不能为负,且每一时刻野人的人数都必须小于或等于传教士的人数。

2.定义连接:两个节点间的连接可由般从右到左岸时船上的传教士人数、野人人数、船返回时船上的传教士人数、野人人数进行描述。

3.算法分析:

先来看看问题的初始状态和目标状态,假设传教士和野人人数都为3人,船的负载人数为2人,河岸分为右岸和左岸:

初始状态:

右岸 3传教士,3野人;

左岸 0传教士,0野人;

船停在右岸,船上有0个人;

目标状态:

右岸 0传教士,0野人;

左岸 3传教士,3野人;

船停在左岸,船上有0个人;

整个问题就抽象成了怎样从初始状态经中间的一系列状态达到目标状态。问题状态的改变是通过划船渡河来引发的,所以合理的渡河操作就成了通常所说的算符,根据题目要求,可以得出以下5个算符(按照渡船方向的不同,也可以理解为10或更多个算符):

渡1野人、渡1传教士、渡1野人1传教士、渡2野人、渡2传教士算符知道以后,剩下的核心问题就是搜索方法:首先定义freeit()函数释放不符合条件的节点,determ()函数判断符合条件的情况,sign()函数判断船的航行方向,copyit()函数复制节点内容,print ()函数显示保存结果,然后在trans()函数中通过调用sign()、copit()、determ()、print()完成渡河既搜索方法。

搜索中采用的一些规则如下:

1、渡船优先规则:右岸一次运走的人越多越好(即右岸运多人优先),同时野人优先运走;左岸一次运走的人越少越好(即左岸运少人优先),同时传教士优先运走;

2、不能重复上次渡船操作(通过链表中前一操作比较),避免进入死循环;

3、任何时候河两边的野人和传教士人数均分别大于或等于0且小于或等于4;

4、由于只是找出最优解,所以当找到某一算符(当前最优先的)满足操作条件后,不再搜索其下一节点,而是直接载入链表。

5、若搜索某节点a的时候,没有找到合适的子节点,则从链表中返回节点a的父节点b,从上次已经选择了的算符之后的算符中找最优先的算符继续搜索b

三.主要流程图

四. 基本数据类型声明及数据结构

#include

#include

#include

#include

FILE *fp;

struct a *jj,head; //jj指向各种情况下船上的传教士和野人人数

long r,total=0,js=0; /*js渡船的方法数,r 为船的负载人数,total为初始状态到目标状态之间的状态个数*/

long k1,k2; //起初传教士和野人的个数

/*结构类型a:记录各种情况下船上的传教士和野人数*/

struct a{

long m,s; //船上的传教士和野人个数

struct a *next; //指向下一个接点(a)的指针next

};

/*建立双向的指针链表,记入符合的情况*/

struct aim

{

long m1,s1; //右岸的传教士和野人个数

long m2,s2; //左岸的传教士和野人个数

long n; //n为摆渡次数

struct aim *back,*next;//指向前一个接点(aim)的指针bake和下一个接点(aim)的指针next

};

五. 程序主要实现说明及设置

1./*释放该接点,并将其上的接点的next指针还原*/

void freeit(struct aim *p)

{

struct aim *p1=p;

p1=p->back;

free(p);

if(p1!=NULL)

p1->next=NULL;

return;

}

2./*判断函数判断符合条件的情况*/

long determ(struct aim *p)

{

struct aim *p1=p;

if(p->s1>k2||p->m1>k1||p->s2>k2||p->m2>k1||p-> s1<0||p->s2<0||p->m1<0||p->m2<0)

return -1;

if(k1>4||k2>4)

return -1;

if(p->m1!=0)

if(p->s1>p->m1)

return -1;

if(p->m2!=0)

if(p->s2>p->m2)

return -1;

while(p1!=NULL)

{

p1=p1->back;

if(p1!=NULL)

if(p1->n%2==p->n%2)

if(p1->s1==p->s1)

if(p1->s2==p->s2)

if(p1->m1==p->m1)

if(p1->m2==p->m2)

return -1;

}

if(p->s1==0&&p->m1==0) //条件成立摆渡完成返回1

if(p->n%2==0)

return 1;

else

return -1;

return 0;

}

3./*符号函数判断是从右到左航行还是从左到右航行*/

long sign(long n)

{

if(n%2==0)

return -1; //从右到左再返回

return 1; //从右到左不反回

}

4./*复制内容函数*/

void copyit(struct aim *p3,struct aim *p)

{

p3->s1=p->s1;

p3->s2=p->s2;

p3->m1=p->m1;

p3->m2=p->m2;

p3->n=p->n+1; //指向下一次摆渡

p3->back=p;

p3->next=NULL;

p->next=p3;

}

5./*打印函数在屏幕上显示结果并将其存入文件中*/

void print(struct aim *p3)

{

struct aim *p=p3;

js++;

while(p->back)

{

p=p->back;//指向下一个方法的接点

}

/*********************************/

printf("\n方法%ld:\n",js);

fprintf(fp,"\n方法%ld:\n",js);

/*********************************/

while(p)

{

/*********************************/

printf("%ld,%ld::%ld,%ld\t",p->m1,p->s1,p->m2, p->s2);

fprintf(fp,"%ld,%ld::%ld,%ld\t",p->m1,p->s1,p->m2,p->s2);

/*********************************/

p=p->next; //指向下一个节点

}

printf("\n");

}

6./*转移函数将人从右岸渡到左岸*/

void trans(struct aim *p)

{

struct aim *p3;

struct a *fla;

long i,j,f,e;

fla=&head;

p3=(struct aim *)malloc(sizeof(struct aim)); f=sign(p->n);

for(i=0;i

{

fla=fla->next;

copyit(p3,p);

/*渡河:右岸人数减去船上所渡人数,左岸人数则

加上从右岸渡来的人数*/

p3->s1-=fla->s*f;

p3->m1-=fla->m*f;

p3->s2+=fla->s*f;

p3->m2+=fla->m*f;

j=determ(p3); //调用判断函数判断符合条件的

情况

if(j==-1)

{

if(i

{

continue;

}

else

{

freeit(p3); //调用freeit()释放该接点

break;

}

}

if(j==1)

{

if(i

{

print(p3);

continue;

}

else

{

print(p3); //调用print()打印结果

freeit(p3);

break;

}

}

if(j==0)

trans(p3);//递归调用转移函数将人从右岸渡到左岸

}

if(j==-1)

/*********************************/

printf("你输入的数据出现错误!\n");

printf("请重新运行程序!\n");

/*********************************/

return;

}

7./*程序入口*/

void main()

{

struct aim *p,*p1;

long j,a ;

long e,f;

struct a *flag;

FILE*fpt;

if((fpt=fopen("c:result.txt","w+"))==0) {

printf("can't creat it\n");

exit(0);

}

fp=fpt;

p=(struct aim *)malloc(sizeof(struct aim)); p->back=NULL;

p->next=NULL;

p->s2=0;

p->m2=0;

p->n=1;

/*********************************/

printf("请输入船的负载人数\n");

fprintf(fp,"\n请输入船的负载人数\n");

scanf("%ld",&r);

fprintf(fp,"\n%ld\n",r);

/*********************************/

/*if(r>3)

{

printf("船太小已经超载了!\n");

}*/

flag=&head;

for(e=0;e<=r;e++)

for(f=0;f<=r;f++)

if(e+f>0&&e+f<=r)

{

total++;

jj=(struct a*)malloc(sizeof(struct a)); jj->m=e;

jj->s=f;

flag->next=jj;

jj->next=NULL;

flag=jj;

}

/*********************************/

printf("注意:输入的传教士的人数大于或等于野人个数:\n");

printf("请输入传教士和野人的个数: 传教士,野人;\n");

fprintf(fp,"\n请输入传教士和野人的个数: 传教士,野人\n");

scanf("%ld,%ld",&p->m1,&p->s1);

fprintf(fp,"\n%ld,%ld\n",p->m1,p->s1); /**********************************/

k1=p->m1;

k2=p->s1;

if(k1>4||k2>4||k2>k1)

{

printf("你输入的数据出现错误!\n");

printf("请重新运行程序!\n");

fprintf(fp,"\n你输入的数据出现错误!\n"); fprintf(fp,"\n请重新运行程序!\n");

}

trans(p);

fclose(fpt);

getch();

}

六.运行结果

1.

2.

3.

4.

修道士与野人问题

实验课名称:数据结构实验五 实验名称:修道士与野人问题 班级: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;idata.xds-array[i].xds; tem.yr=q->data.yr-array[i].yr; tem.cw=1-q->data.cw;

传教士野人过河问题-两种解法思路

实验 传教士野人过河问题 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 )

MC牧师过河问题

人工智能上机实验报告 学号:姓名:所在系:信息学院班级: 实验名称:实验日期2016年12月3日 实验指导教师实验机房A401 ------------------------------------------------------------------------------------------------------ 1.实验目的: (1)在掌握状态空间搜索策略的基础上,理解知识表示的方法。 (2)能够应用知识表示方法,解决实际问题 2. 实验内容: (1)M-C问题描述 有n个牧师和n个野人准备渡河,但只有一条能容纳c个人的小船,为了防止野人侵犯牧师,要求无论在何处,牧师的人数不得少于野人的人数(除非牧师人数为0),且假定野人与牧师都会划船,试设计一个算法,确定他们能否渡过河去,若能,则给出小船来回次数最少的最佳方案。 3.算法设计(编程思路或流程图或源代码) #include #include #include #define maxloop 100 /* 最大层数,对于不同的扩展方法自动调整取值*/ #define pristnum 3 /*初始化时设定有3个野人3个牧师,实际可以改动*/ #define slavenum 3 struct SPQ { int sr,pr; /* 船运行一个来回后河右岸的野人、牧师的人数*/ int sl,pl; /* 船运行一个来回后河左岸的野人、牧师的人数*/ int ssr,spr; /* 回来(由左向右时)船上的人数*/ int sst,spt; /* 去时(由右向左时)船上的人数*/ int loop; /* 本结点所在的层数*/ struct SPQ *upnode ,*nextnode;/* 本结点的父结点和同层的下一个结点的地址*/ }spq; int loopnum;/* 记录总的扩展次数*/ int openednum;/* 记录已扩展节点个数*/ int unopenednum;/* 记录待扩展节点个数*/ int resultnum; struct SPQ *opened; struct SPQ *oend; struct SPQ *unopened;

传教士和野人问题实验报告

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队列头结点的子结点,同时保存受访问结点的父结点信息,知道搜索到目标结点或者无解为止。 算法框图如下所示:

传教士和野人问题

状态空间法详解传教士和野人问题 传教士和野人问题(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)当状态数量不是很大时,按问题的有序元组画出状态空间图,依照状态空间图搜索求解。

AStar算法解决野人渡河问题

江南大学物联网工程学院实验报告 课程名称人工智能实验名称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;

有N个传教士和N个野人来到河边渡河

有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操作)

修道士与野人问题教学文案

修道士与野人问题

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得到所有情况,然后再进行安全性检查,以减去修道士少于野人的情况,接着用孩子兄弟结点表示法,将去对面的路作为孩子结点,路与路是兄弟

C实现传教士与野人过河问题实验报告

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; //传教士是否被吃

野人过河问题算法分析

野人过河问题算法分析 野人过河问题属于人工智能学科中的一个经典问题,问题描述如下:有三个牧师(也有的翻译为传教士)和三个野人过河,只有一条能装下两个人的船,在河的任何一方或者船上,如果野人的人数大于牧师的人数,那么牧师就会有危险. 你能不能找出一种安全的渡河方法呢? 一、算法分析 先来看看问题的初始状态和目标状态,假设和分为甲岸和乙岸:初始状态:甲岸,3野人,3牧师; 乙岸,0野人,0牧师; 船停在甲岸,船上有0个人; 目标状态:甲岸,0野人,0牧师; 乙岸,3野人,3牧师; 船停在乙岸,船上有0个人; 整个问题就抽象成了怎样从初始状态经中间的一系列状态达到目标状态。问题状态的改变是通过划船渡河来引发的,所以合理的渡河操作就成了通常所说的算符,根据题目要求,可以得出以下5个算符(按照渡船方向的不同,也可以理解为10个算符): 渡1野人、渡1牧师、渡1野人1牧师、渡2野人、渡2牧师算符知道以后,剩下的核心问题就是搜索方法了,本文采用深度优先搜索,通过一个FindNext(…)函数找出下一步可以进行的渡河操作中的最优操作,如果没有找到则返回其父节点,看看是否有其它兄弟节点可以扩展,然后用Process(…)函数递规调用FindNext(…),一级一级的向后扩展。 搜索中采用的一些规则如下: 1、渡船优先规则:甲岸一次运走的人越多越好(即甲岸运多人优先),同时野人优先运走; 乙岸一次运走的人越少越好(即乙岸运少人优先),同时牧师优先运走; 2、不能重复上次渡船操作(通过链表中前一操作比较),避免进入死循环; 3、任何时候河两边的野人和牧师数均分别大于等于0且小于等于3; 4、由于只是找出最优解,所以当找到某一算符(当前最优先的)满足操作条件后,不再搜索其兄弟节点,而是直接载入链表。 5、若扩展某节点a的时候,没有找到合适的子节点,则从链表中返回节点a的父节点b,从上次已经选择了的算符之后的算符中找最优先的算符继续扩展b。 二、基本数据结构 仔细阅读问题,可以发现有些基本东西我们必须把握,例如:每时刻河两岸野人牧师各自的数目、船的状态、整个问题状态。所以我们定义如下几个数据结构: typedef struct _riverside // 岸边状态类型

传教士与野人过河问题

贵州航天职业技术学院《C语言程序设计》 系别: __计算机科学系 _________ 班级: __10级软件技术_________ 姓名: _______________________ 指导教师: ___陆树芬_______________ 小组成员: ___翟奇张源李雪_______

前言 C语言作为一门最通用的语言,在过去很流行,将来依然会如此。几乎每一个理工科或者其他专业的学生毫不例外地要学习它。从C 语言产生到现在,它已经成为最重要和最流行的编程语言之一。在各种流行编程语言中,都能看到C语言的影子,如Java的语法与C 语言基本相同。学习、掌握C语言是每一个计算机技术人员的基本功之一。C语言具有高级语言的强大功能,却又有很多直接操作计算机硬件的功能(这些都是汇编语言的功能),因此,C语言通常又被称为中级语言。学习和掌握C语言,既可以增进对于计算机底层工作机制的了解,又为进一步学习其他高级语言打下了坚实的基础。本大作业是对学生在课堂上所学知识的一次综合检测。通过本次大作业的制作,应能综合使用在《C语言程序设计》课程中学到的多种基础知识,并可以很好的应用到实际操作中去,具备简单的项目设计能力。 本大作业主要以传教士和野人怎样从河的一岸完全渡到另一岸,而不发生野人吃掉传教士这一问题展开,主要使用C语言中的链表应用完成程序的设计,将此次程序设计报告分为以下几点: 1. 问题的描述:描述本程序的设计内容; 2. 问题分析:介绍此程序设计的结构和算法分析 3. 程序设计流程图 4. 程序各个功能模块的实现

5. 程序运行结果:将各种情况下的运行结果通过屏幕截取下来 6. 程序设计结论:描述本次程序设计的一些体会和在程序设计过 程中所获得的一些知识以及本次程序设计所存在的不足和缺陷。 7. 完成本次程序设计所翻阅的资料

传教士和野人过河

实验报告 一、实验名称: 传教士和野人过河 二、实验目的: 这是经典的过河方案规划问题,通过本实验的设计与编程实现让学生掌握基 于状态空间知识表示方法的一般搜索策略。 三、实验内容: 设有3个传教士和3个野人同在河的左岸,他们都要到对岸去;河里只有 一条船,他们都会划船,但每次渡船至多只能乘两人;如果在任何一岸上,也认的数量超过传教士,野人就要吃掉传教士,要求设计算法,用船将3 个传教士和3个野人安全的从左岸移到右岸。 四、实验设计 (一)所用的语言:c++语言 (二)数据结构 节点状态用列表(m,c,b)表示,其中m表示传教士在左岸的人数; c表 示野人在左岸的人数;b表示船是否在左岸,当b=1时,表示船在左岸, 当b=0时,表式船在右岸。 初始状态:(3,3,1) 目标状态: (0,0,0) 操作算子:船上人数组合(m,c)共5种(1,0),(1,1),(2,0), (0,1),(0,2) 因此算法有10种 1)从右岸向左岸过1个传教士,0个野人

2)从右岸向左岸过1个传教士,1个野人 3)从右岸向左岸过2个传教士,0个野人 4)从右岸向左岸过0个传教士,1个野人 5)从右岸向左岸过0个传教士,2个野人 6)从左岸向右岸过1个传教士,0个野人 7)从左岸向右岸过1个传教士,1个野人 8)从左岸向右岸过2个传教士,0个野人 9)从左岸向右岸过0个传教士,1个野人 10)从左岸向右岸过0个传教士,2个野人 状态节点: typedef struct st { int m;//传教士 int c;//野人 int b;//船左 }state;//状态 将有效的节点存储在树中 Tree 中的节点 typedef struct hnode { state s; struct hnode *left; struct hnode *right; }node; Open表,closed表用队列存储 //定义队列中的节点 typedef struct Queuenode { node * np; struct Queuenode* next; }Qnode;//队列中节点 //定义队列 typedef struct Queue { Qnode *front; Qnode *rear; }queue; (三)算法流程 1.用起始节点(3,3,1) 初始化tree,初始化open表,closed表。

人工智能里野人和传教士问题代码

//而对于函数qq(int& a),这是C++中引入的一个新类型:引用,所带来的新的函数传值方式,即按引用传值。 #include /* exit() */ #include #include #define NULL 0 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 typedef struct { int m; int c; int b; }QElemType; /* 定义队列的数据元素类型QElemType为结构体类型*/ typedef struct _Rule { int m; int c; }Rule; Rule rule[5] = {{1,1}, {1,0}, {0,1}, {2,0}, {0,2}}; // 规则集e typedef struct QNode { QElemType data; struct QNode *next; }QNode,*QueuePtr; typedef struct { QueuePtr front,rear; /* 队头、队尾指针*/ }LinkQueue; void InitQueue(LinkQueue *Q) { /* 构造一个空队列Q */ (*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode)); if(!(*Q).front) exit(0); (*Q).front->next=NULL; } int DeQueue(LinkQueue *Q,QElemType *e) { /* 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */

人工智能 野人和传教士问题

传教士-野人问题 有N个传教士和N个野人要过河,现在有一条船只能承载K个人(包括野人),K=C且M+C <= K 初始状态目标状态 L R L R M 3 0 M 0 3 C 3 0 C 0 3 B 1 0 B 0 1 (1)用三元组来表示(ML , CL , BL) 其中0<=ML , CL <= 3 , BL ∈{ 0 , 1} (3 , 3 , 1) (0 , 0 , 0) (2)规则集合 P10if ( ML ,CL , BL=1 ) then ( ML–1 , CL , BL –1 ) P01if ( ML ,CL , BL=1 ) then ( ML , CL–1 , BL –1 ) P11if ( ML ,CL , BL=1 ) then ( ML–1 , CL–1 , BL –1 ) P20if ( ML ,CL , BL=1 ) then ( ML–2 , CL , BL –1 ) P02if ( ML ,CL , BL=1 ) then ( ML , CL–2 , BL –1 ) Q10if ( ML ,CL , BL=0 ) then ( ML+1 , CL , BL+1 ) Q01if ( ML ,CL , BL=0 ) then ( ML , CL+1 , BL +1 ) Q11if ( ML ,CL , BL=0 ) then ( ML+1 , CL +1, BL +1 ) Q20 if ( ML ,CL , BL=0 ) then ( ML+2 , CL +2, BL +1 ) Q02if ( ML ,CL , BL=0 ) then ( ML , CL +2, BL +1 ) (3)寻找一个启发式函数引导规则的选用 右岸总人数6 – ML – CL 两岸中传教士数目>=野人数目 f = –∞其它

传教士和野人问题

传教士和野人问题(Missionaries and Cannibals)传教士和野人问题是一个经典的智力游戏问题。在这个问题中,实际上隐含了这样一个条件:如果在河的某一岸只有野人,而没有传教士,也同样被认为是合法状态。在具体书写某些条件时,为了简便,这一点有时并没有考虑,但我们默认这个条件是被考虑了的。 有N个传教士和N个野人来到河边准备渡河,河岸有一条船,每次至多可供k人乘渡。问传教士为了安全起见,应如何规划摆渡方案,使得任何时刻,在河的两岸以及船上的野人数目总是不超过传教士的数目。即求解传教士和野人从左岸全部摆渡到右岸的过程中,任何时刻满足M(传教士数)≥C (野人数)和M+C≤k的摆渡方案。 设N=3,k=2,则给定的问题可用图1.2表示,图中L和R表示左岸和右岸,B=1或0分别表示有船或无船。约束条件是:两岸上M≥C,船上M+C≤2。

图1.2 M-C问题实例 由于传教士和野人数是一个常数,所以知道了一岸的情况,另一岸的情况也就知道了。因此为了简便起见,在描述问题时,只描述一岸--如左岸--的情况就可以了。 另外,该问题我们最关心的是在摆渡过程中,两岸状态的变化情况,因此船上的情况并不需要直接表达出来。在一次摆渡过程中,船上究竟有几个传教士和野人,可以通过两个相连的状态简单得到。这样表达更简练,突出了问题的重点。(1)综合数据库:用三元组表示左岸的情况,即(,,),其中0≤,≤3,∈{0,1} ,其中表示在左岸的传教士人数,表示在左岸的野人数,=1表示船在左岸,=0表示船在右岸。则此时问题描述可以简化为:(3,3,1)→(0,0,0) N=3的M-C问题,状态空间的总状态数为4×4×2=32,根据约束条件的要求,可以看出只有20个合法状态。再进一步分析后,又发现有4个合法状态实际上是不可能达到的。因此实际的问题空间仅由16个状态构成。下表列出分析的结果: ( ) (001)达不到(传教士( )(000)

C实现传教士与野人过河问题实验报告

传教士与野人过河问题实验报告 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;

人工智能实验2 传教士过河问题

人工智能实验报告 班级:计研-12班 学号:25 姓名:孔德星

实验二知识表示方法 1.实验目的 (1)了解知识表示相关技术; (2)掌握问题规约法或者状态空间法的分析方法。 2.实验内容(2个实验内容可以选择1个实现) (1)梵塔问题实验。熟悉和掌握问题规约法的原理、实质和规约过程;理解规约图的表示方法; (2)状态空间法实验。从前有一条河,河的左岸有m个传教士、m个野人和一艘最多可乘n人的小船。约定左岸,右岸和船上或者没有传教士,或者野人数量少于传教士,否则野人会把传教士吃掉。搜索一条可使所有的野人和传教士安全渡到右岸的方案。 3.实验报告要求 (1)简述实验原理及方法,并请给出程序设计流程图。 实验原理:假设开始时传教士、野人和船都在右岸,用数组(a,b,c)分别表示右岸传教士个数、右岸野人个数、船的位置,则可分为三种情况讨论: A、n>m/2。此种情况下,先把所有的野人度过去,每次返回一个野人,当出现(m,0,0)情况时,返回m-n个野人(若m==n,返回1个野人)。然后渡n个传教士,此时野人==传教士,然后返回一个野人和传教士,再开始最大限度的渡传教士,每次返回一个野人,最终直到 a==b==c==0; B、n<=3&&n<=m/2 || n==1,显然此时无解; C、n>=4&&n<=m/2,此时只能每次传n/2个传教士和野人,每次返回一个野人和传教士,直到最终结果。 程序流程图:

(2)源程序清单: 本程序用C++语言编写。 #include"iostream" using namespace std; bool flag = false; //标记是否有解 bool af = false; //标记a是否为0 bool bf = false; //当b变为0后赋值为true; bool ef = false; //当a==b后赋值为true bool f = false; //判断n是否大于m/2 int m;//传教士野人的个数 int n;//船一次能装载的人数 void mc(int a,int b,int c); int main() { cout<<"传教士与野人过河问题。\n假设最初时传教士与野人在河的右岸。\n"; cout<<"请输入传教士野人的个数:\n"; cin>>m; cout<<"请输入船一次能装载的人数: \n"; cin>>n; cout<<"右岸传教士人数\t"<<"右岸野人个数\t"<<"船的位置(1.右岸 0左岸)"< m/2) f = true; mc(m,m,1);

修道士与野人问题

修道士与野人问题 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输出安全渡河的全过程。 各个模块要完成的主要功能分别为: 生成模块:生成所有的可能渡河情况 安全检测模块:对所有的可能渡河情况进行安全检测,,以减去修道士少于野人的情况

相关主题