人工智能二_野人过河问题_实验3.doc

实 验 报 告课程名称 人工智能_ 实验项目 野人过河问题_ 实验仪器 电脑 、visual C+_ 系 别 计算机学院_ 专 业 _计算机科学与技术_ 班级/学号 学生姓名 _ _实验日期 2010年 月 日_ 成 绩 _ 指导教师 一、 实验目的理解并熟悉掌握深度优先搜索和广度优先搜索地方法。二、 实验内容题目：设有3个传教士和3个野人来到河边，打算乘一只船从右岸到左岸去。 该船的负载能力为两人。在任何时候，如果野人人数超过传教士人数，野人 就会把传教士吃掉。他们怎样才能用这条船安全的把所有人都渡过河去? 三、代码和结果#include #include #include #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(题目：设有n个传教士和m个野人来到河边，打算乘一只船从右岸到左岸去。n); printf(该船的负载能力为两人。在任何时候，如果野人人数超过传教士人数，野人n); printf(就会把传教士吃掉。他们怎样才能用这条船安全的把所有人都渡过河去?n); printf(n默认的n、m值皆为3n); for(;) printf(n是否修改？(Y/N); scanf(%s,&choice); choice=toupper(choice); if(choice=Y) printf(n请输入传教士人数); for(;) scanf(%d,&x); if(x0) unopened - pr = x; break; else printf(n输入值应大于0！n请重新输入); printf(n请输入野人人数); for(;) scanf(%d,&x); if(x0) unopened - sr = x; break; else printf(n输入值应大于0！n请重新输入); break; if(choice=N)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 sr; fpr = ntx - pr; fsl = ntx - sl; fpl = ntx - pl; if (sst = fsr) & ( 2 - 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 = 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) = 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 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 nextnode; free(nodefree); for ( i = 0 ; i 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 nextnode; free(nodefree); printf(nnt左岸人数 船上人数及方向 右岸人数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(传教士%8d%8dt spt,fpr); printf(野 人%8d%8dt sst,fsr); printf(传教士%8d%8dt-t%8dn,result - pl,result - spr,result - pr - result - spr)