《昆明理工大学 人工智能 实验一》由会员分享，可在线阅读，更多相关《昆明理工大学 人工智能 实验一（15页珍藏版）》请在金锄头文库上搜索。
1、-1-昆明理工大学信息工程与自动化学院学生实验报告昆明理工大学信息工程与自动化学院学生实验报告（ 2011 2012 学年学年 第第 1 学期学期 ）课程名称：人工智能课程名称：人工智能 开课实验室：开课实验室： 444444 20112011 年年 1212 月月 9 9 日日年级、专业、年级、专业、班班计科计科 093093学号学号200910405310200910405310姓名姓名孙浩川孙浩川成绩成绩实验项目名称实验项目名称传教士与野人过河问题传教士与野人过河问题指导教师指导教师王剑王剑教教师师评评语语该同学是否了解实验原理：A.了解B.基本了解C.不了解 该同学的实验能力：A.强
2、B.中等 C.差 该同学的实验是否达到要求：A.达到B.基本达到C.未达到 实验报告是否规范：A.规范B.基本规范C.不规范 实验过程是否详细记录：A.详细B.一般 C.没有 教师签名：教师签名：年年 月月 日日一、实验目的及内容一、实验目的及内容实验目的：理解并熟悉掌握深度优先搜索和广度优先搜索地方法。实验内容：设有 3 个传教士和 3 个野人来到河边，打算乘一只船从右岸到左岸去。该船的负载能力为两人。在任何时候，如果野人人数超过传教士人数，野人就会把传教士吃掉。他们怎样才能用这条船安全的把所有人都渡过河去? 二、实验原理及基本技术路线图（二、实验原理及基本技术路线图（方框原理图或程序流程图
3、）程序流程图）-2-三、所用仪器、材料（三、所用仪器、材料（设备名称、型号、规格等或使用软件）使用软件）1 台 PC 以及 VISUAL C+6.0 软件四、实验方法、步骤（或：程序代码或操作过程）四、实验方法、步骤（或：程序代码或操作过程）#include #include #include #define maxloop 100 /* 最大层数，对于不同的扩展方法自动调整取值 */-3-#define pristnum 3 /*初始化时设定有 3 个野人 3 个传教士，实际可以改动*/#define slavenum 3struct SPQ int sr,pr; /* 船运行一个来回后河右
4、岸的野人、传教士的人数 */int sl,pl; /* 船运行一个来回后河左岸的野人、传教士的人数 */int ssr,spr; /* 回来（由左向右时）船上的人数 */int sst,spt; /* 去时（由右向左时）船上的人数 */int loop; /* 本结点所在的层数 */struct SPQ *upnode ,*nextnode;/* 本结点的父结点和同层的下一个结点的地址 */spq; int loopnum;/* 记录总的扩展次数 */int openednum;/* 记录已扩展节点个数 */int unopenednum;/* 记录待扩展节点个数 */int resultnu
5、m;struct SPQ *opened;struct SPQ *oend;struct SPQ *unopened; struct SPQ *uend;struct SPQ *result;void initiate();void releasemem();void showresult();void addtoopened(struct SPQ *ntx);int search();void goon();int stretch(struct SPQ* ntx);-4-void recorder();int main()int flag; /* 标记扩展是否成功 */for( ; ; )i
6、nitiate();flag = search ();if(flag = 1)recorder();releasemem();showresult();goon();elseprintf(“无法找到符合条件的解“);releasemem();goon();system(“pause“);return 0;void initiate()-5-int x;char choice;uend = unopened = (struct SPQ*)malloc(sizeof(spq);if(uend=NULL)printf(“n 内存不够！n“);exit(0);unopenednum=1;openedn
7、um=0;unopened - upnode = unopened; /* 保存父结点的地址以成链表 */unopened - nextnode = unopened;unopened - sr = slavenum;unopened - pr = pristnum;unopened - sl = 0;unopened - pl = 0;unopened - sst = 0;unopened - spt = 0;unopened - ssr = 0;unopened - spr = 0;unopened - loop = 0;printf(“计科 093 班 孙浩川 200910405310n
8、n“);printf(“设有 3 个传教士和 3 个野人来到河边，打算乘一只船从右岸到左岸去。该船的负载能力为两人。在任何时候，如果野人人数超过传教士人数，野人就会把传教士吃掉。他们怎样才能用这条船安全的把所有人都渡过河去?n“);/*printf(“该船的负载能力为两人。在任何时候，如果野人人数超过传教士人数，野人n“);printf(“就会把传教士吃掉。他们怎样才能用这条船安全的把所有人都渡过河去?n“);*/-6-for(;)printf(“n 是否开始？(Y/N)“);scanf(“%s“,choice=toupper(choice);if(choice=N) printf(“n 请输
9、入传教士人数“);for(;)scanf(“%d“,if(x0) unopened - pr = x;break;else printf(“n 输入值应大于 0！n 请重新输入“);printf(“n 请输入野人人数“);for(;)scanf(“%d“,if(x0)unopened - sr = x;break;else printf(“n 输入值应大于 0！n 请重新输入“); break;-7-if(choice=Y)break;int search()int flag;struct SPQ *ntx; /* 提供将要扩展的结点的指针 */for( ; ; )ntx = unopened
10、; /* 从待扩展链表中提取最前面的一个 */if(ntx-loop = maxloop)return 0; addtoopened(ntx); /* 将 ntx 加入已扩展链表，并将这个节点从待扩展链表中去掉 */flag = stretch(ntx); /* 对 ntx 进行扩展,返回-1,0,1 */if(flag = 1)return 1; int stretch(struct SPQ *ntx)int fsr , fpr ; /* 在右岸上的人数 */int fsl , fpl ; /* 在左岸上的人数 */int sst , spt ; /* 出发时在船上的人数 */int ssr
11、 , spr ; /* 返回时船上的人数 */struct SPQ *newnode;for (sst = 0 ; sst sr;fpr = ntx - pr;fsl = ntx - sl;fpl = ntx - pl;if (sst upnode = ntx; /* 保存父结点的地址以成链表 */newnode - nextnode = NULL;newnode - sr = 0;newnode - pr = 0;newnode - sl = opened - sr;newnode - pl = opened - pr;newnode - sst = sst;newnode - spt =
12、spt;newnode - ssr = 0;newnode - spr = 0;newnode - loop = ntx - loop + 1;-9-oend - nextnode = newnode;oend = newnode;openednum+;return 1; else if (fpr - fsr) * fpr = 0) /* 判断是否满足传教士人数必须大于或等于野人人数 */fsl = fsl + sst;fpl = fpl + spt;for (ssr = 0 ; ssr = 0) /* 若符合条件则分配内存并付值 */int ffsr , ffpr;ffsr = fsr +
13、ssr;ffpr = fpr + spr; newnode = (struct SPQ*) malloc (sizeof(spq);if(newnode=NULL)printf(“n 内存不够！n“);exit(0);-10-newnode - upnode = ntx; /* 保存父结点的地址以成链表 */newnode - sr = ffsr;newnode - pr = ffpr;newnode - sl = ffsl;newnode - pl = ffpl;newnode - sst = sst;newnode - spt = spt;newnode - ssr = ssr;newno
14、de - spr = spr;newnode - loop = ntx - loop + 1;uend - nextnode = newnode;uend = newnode;unopenednum+; return 0;void addtoopened(struct SPQ *ntx)unopened = unopened - nextnode;unopenednum-;if (openednum = 0 )oend = opened = ntx;-11-oend - nextnode = ntx;oend = ntx;openednum+;void recorder()int i , lo
15、op;struct SPQ *newnode;struct SPQ *ntx;loop = oend - loop;ntx = oend;resultnum = 0;for( i = 0 ; i sr = ntx - sr;newnode - pr = ntx - pr;newnode - sl = ntx - sl;newnode - pl = ntx - pl;newnode - sst = ntx - sst;newnode - spt = ntx - spt;newnode - ssr = ntx - ssr;newnode - spr = ntx - spr;newnode - nextnode = NULL;ntx = ntx - upnode; -12
