昆明理工大学信息工程与自动化学院学生实验报告（2011 —2012 学年第 1 学期）课程名称：人工智能开课实验室： 444 2011年 12 月 9日年级、专业、班计科093 学号200910405310 姓名孙浩川成绩实验项目名称传教士与野人过河问题指导教师王剑教师评语该同学是否了解实验原理： A.了解□ B.基本了解□ C.不了解□该同学的实验能力： A.强□ B.中等□ C.差□该同学的实验是否达到要求： A.达到□ B.基本达到□ C.未达到□实验报告是否规范： A.规范□ B.基本规范□ C.不规范□实验过程是否详细记录： A.详细□ B.一般□ C.没有□教师签名：年月日一、实验目的及内容实验目的：理解并熟悉掌握深度优先搜索和广度优先搜索地方法。
实验内容：设有3个传教士和3个野人来到河边，打算乘一只船从右岸到左岸去。
该船的负载能力为两人。
在任何时候，如果野人人数超过传教士人数，野人就会把传教士吃掉。
他们怎样才能用这条船安全的把所有人都渡过河去?二、实验原理及基本技术路线图（方框原理图或程序流程图）三、所用仪器、材料（设备名称、型号、规格等或使用软件）1台PC以及VISUAL C++6.0软件四、实验方法、步骤（或：程序代码或操作过程）#include <stdio.h>#include <stdlib.h>#include <ctype.h>#define maxloop 100 /* 最大层数，对于不同的扩展方法自动调整取值 */#define pristnum 3 /*初始化时设定有3个野人3个传教士，实际可以改动*/#define slavenum 3struct 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;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);void recorder();int main(){int flag; /* 标记扩展是否成功 */ for( ; ; ){initiate();flag = search ();if(flag == 1){recorder();releasemem();showresult();goon();}else{printf("无法找到符合条件的解"); releasemem();goon();}}system("pause");return 0;}void initiate(){int x;char choice;uend = unopened = (struct SPQ*)malloc(sizeof(spq));if(uend==NULL){printf("\n内存不够！\n");exit(0);}unopenednum=1;openednum=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班孙浩川 200910405310\n\n");printf("设有3个传教士和3个野人来到河边，打算乘一只船从右岸到左岸去。
该船的负载能力为两人。
在任何时候，如果野人人数超过传教士人数，野人就会把传教士吃掉。
他们怎样才能用这条船安全的把所有人都渡过河去?\n");/*printf("该船的负载能力为两人。
在任何时候，如果野人人数超过传教士人数，野人\n");printf("就会把传教士吃掉。
他们怎样才能用这条船安全的把所有人都渡过河去?\n");*/for(;;){printf("\n是否开始？(Y/N)");scanf("%s",&choice);choice=toupper(choice);if(choice=='N'){printf("\n请输入传教士人数");for(;;){scanf("%d",&x);if(x>0){unopened -> pr = x;break;}else printf("\n输入值应大于0！\n请重新输入"); }printf("\n请输入野人人数");for(;;){scanf("%d",&x);if(x>0){unopened -> sr = x;break;}else printf("\n输入值应大于0！\n请重新输入"); }break;}if(choice=='Y')break;}}int search(){int flag;struct SPQ *ntx; /* 提供将要扩展的结点的指针 */for( ; ; ){ntx = unopened; /* 从待扩展链表中提取最前面的一个 */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 , spr ; /* 返回时船上的人数 */struct SPQ *newnode;for (sst = 0 ; sst <= 2 ; sst++) /* 讨论不同的可能性并判断是否符合条件 */{fsr = ntx -> sr;fpr = ntx -> pr;fsl = ntx -> sl;fpl = ntx -> pl;if ((sst <= fsr) && (( 2 - sst) <= fpr))/* 满足人数限制 */{spt = 2 - sst;fsr = fsr - sst;fpr = fpr - spt;if((fpr == 0) && (fsr == 0))/* 搜索成功 */{newnode = (struct SPQ*) malloc (sizeof(spq));if(newnode==NULL){printf("\n内存不够！\n");exit(0);}newnode -> upnode = ntx; /* 保存父结点的地址以成链表 */newnode -> nextnode = NULL;newnode -> sr = 0;newnode -> pr = 0;newnode -> sl = opened -> sr;newnode -> pl = opened -> pr;newnode -> sst = sst;newnode -> spt = spt;newnode -> ssr = 0;newnode -> spr = 0;newnode -> loop = ntx -> loop + 1;oend -> nextnode = newnode;oend = newnode;openednum++;return 1;}else if ((fpr - fsr) * fpr >= 0) /* 判断是否满足传教士人数必须大于或等于野人人数 */{fsl = fsl + sst;fpl = fpl + spt;for (ssr = 0 ; ssr <= 1 ; ssr++) /* 返回 */{int ffsl , ffpl;if ((ssr <= fsl) && ((1 - ssr) <= fpl)){spr = 1 - ssr;ffsl = fsl - ssr;ffpl = fpl - spr;if ((ffpl - ffsl) * ffpl >= 0){ /* 若符合条件则分配内存并付值 */int ffsr , ffpr;ffsr = fsr + ssr;ffpr = fpr + spr;newnode = (struct SPQ*) malloc (sizeof(spq));if(newnode==NULL){printf("\n内存不够！\n");exit(0);}newnode -> upnode = ntx; /* 保存父结点的地址以成链表 */newnode -> sr = ffsr;newnode -> pr = ffpr;newnode -> sl = ffsl;newnode -> pl = ffpl;newnode -> sst = sst;newnode -> spt = spt;newnode -> ssr = ssr;newnode -> 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;oend -> nextnode = ntx;oend = ntx;openednum++;}void recorder(){int i , loop;struct SPQ *newnode;struct SPQ *ntx;loop = oend -> loop;ntx = oend;resultnum = 0;for( i = 0 ; i <= loop ; i++ ){newnode = (struct SPQ*) malloc (sizeof(spq)); if(newnode==NULL){printf("\n内存不够！\n");exit(0);}newnode -> 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;if(i == 0)result = newnode;newnode -> nextnode = result;result = newnode;resultnum++;}}void releasemem(){int i;struct SPQ* nodefree;for ( i = 1 ; i < openednum ; i++ ) {nodefree = opened;opened = opened -> nextnode;free(nodefree);}for ( i = 0 ; i < unopenednum ; i++ ) {nodefree = unopened;unopened = unopened -> nextnode; free(nodefree);}}void showresult(){int i;int fsr , fpr ; /* 在右岸上的人数 */ int fsl , fpl ; /* 在左岸上的人数 */ struct SPQ* nodefree;printf("%d个传教士",result -> pr);printf("%d个野人",result -> sr);printf("%d个传教士",result -> pl);printf("%d个野人",result -> sl);for ( i = 1 ; i < resultnum ; i++ ){nodefree = result;result = result -> nextnode;free(nodefree);// printf("\n\n\t左岸人数船上人数及方向右岸人数\n");printf("第%d轮\n",i);fpl = result -> pl - result -> spt + result -> spr;fpr = result -> pr - result -> spr;fsl = result -> sl - result -> sst + result -> ssr;fsr = result -> sr - result -> ssr;printf("传教士\t左岸%d人，船上%d人，向左，右岸%d人\n",fpl,result -> spt,fpr);printf("野人\t左岸%d人，船上%d人，向左，右岸%d人\n",fsl,result -> sst,fsr);printf("传教士\t左岸%d人，船上%d人，向右，右岸%d人\n",result -> pl,result -> spr,result -> pr - result -> spr);printf("野人\t左岸%d人，船上%d人，向右，右岸%d人\n",result -> sl,result -> ssr,result -> sr - result -> ssr);}printf("\n全体传教士和野人全部到达对岸");free(result);}void goon(){char choice;for(;;){printf("是否继续？(Y/N)\n");scanf ("%s" , &choice);choice=toupper(choice);if(choice=='Y')break;if(choice=='N')exit(0);}}五、实验过程原始记录( 测试数据、图表、计算等)六、实验结果、分析和结论（误差分析与数据处理、成果总结等。