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

实验报告课程名称人工智能_____________实验项目野人过河问题_______________实验仪器电脑、visualC++_________系别计算机学院____________专业__计算机科学与技术_____班级/学号学生姓名___实验日期2010年月日_______成绩_______________________指导教师一、实验目的理解并熟悉掌握深度优先搜索和广度优先搜索地方法。二、实验内容题目：设有3个传教士和3个野人来到河边，打算乘一只船从右岸到左岸去。该船的负载能力为两人。在任何时候，如果野人人数超过传教士人数，野人就会把传教士吃掉。他们怎样才能用这条船安全的把所有人都渡过河去?三、代码和结果#includestdio.h#includestdlib.h#includectype.h#definemaxloop100/*最大层数，对于不同的扩展方法自动调整取值*/#definepristnum3/*初始化时设定有3个野人3个传教士，实际可以改动*/#defineslavenum3structSPQ{intsr,pr;/*船运行一个来回后河右岸的野人、传教士的人数*/intsl,pl;/*船运行一个来回后河左岸的野人、传教士的人数*/intssr,spr;/*回来（由左向右时）船上的人数*/intsst,spt;/*去时（由右向左时）船上的人数*/intloop;/*本结点所在的层数*/structSPQ*upnode,*nextnode;/*本结点的父结点和同层的下一个结点的地址*/}spq;intloopnum;/*记录总的扩展次数*/intopenednum;/*记录已扩展节点个数*/intunopenednum;/*记录待扩展节点个数*/intresultnum;structSPQ*opened;structSPQ*oend;structSPQ*unopened;structSPQ*uend;structSPQ*result;voidinitiate();voidreleasemem();voidshowresult();voidaddtoopened(structSPQ*ntx);intsearch();voidgoon();intstretch(structSPQ*ntx);voidrecorder();intmain(){intflag;/*标记扩展是否成功*/for(;;){initiate();flag=search();if(flag==1){recorder();releasemem();showresult();goon();}else{printf(无法找到符合条件的解);releasemem();goon();}}system(pause);return0;}voidinitiate(){intx;charchoice;uend=unopened=(structSPQ*)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值皆为3\n);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;}elseprintf(\n输入值应大于0！\n请重新输入);}printf(\n请输入野人人数);for(;;){scanf(%d,&x);if(x0){unopened-sr=x;break;}elseprintf(\n输入值应大于0！\n请重新输入);}break;}if(choice=='N')break;}}intsearch(){intflag;structSPQ*ntx;/*提供将要扩展的结点的指针*/for(;;){ntx=unopened;/*从待扩展链表中提取最前面的一个*/if(ntx-loop==maxloop)return0;addtoopened(ntx);/*将ntx加入已扩展链表，并将这个节点从待扩展链表中去掉*/flag=stretch(ntx);/*对ntx进行扩展,返回-1,0,1*/if(flag==1)return1;}}intstretch(structSPQ*ntx){intfsr,fpr;/*在右岸上的人数*/intfsl,fpl;/*在左岸上的人数*/intsst,spt;/*出发时在船上的人数*/intssr,spr;/*返回时船上的人数*/structSPQ*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=(structSPQ*)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++;return1;}elseif((fpr-fsr)*fpr=0)/*判断是否满足传教士人数必须大于或等于野人人数*/{fsl=fsl+sst;fpl=fpl+spt;for(ssr=0;ssr=1;ssr++)/*返回*/{intffsl,ffpl;if((ssr=fsl)&&((1-ssr)=fpl)){spr=1-ssr;ffsl=fsl-ssr;ffpl=fpl-spr;if((ffpl-ffsl)*ffpl=0){/*若符合条件则分配内存并付值*/intffsr,ffpr;ffsr=fsr+ssr;ffpr=fpr+spr;newnode=(structSPQ*)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++;}}}}}}return0;}voidaddtoopened(structSPQ*ntx){unopened=unopened-nextnode;unopenednum--;if(openednum==0)oend=opened=ntx;oend-nextnode=ntx;oend=ntx;openednum++;}voidrecorder(){inti,loop;structSPQ*newnode;structSPQ*ntx;loop=oend-loop;ntx=oend;resultnum=0;for(i=0;i=loop;i++){newnode=(structSPQ*)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++;}}voidreleasemem(){inti;structSPQ*nodefree;for(i=1;iopenednum;i++){nodefree=opened;opened=opened-nextnode;free(nodefree);}for(i=0;iunopenednum;i++){nodefree=unopened;unopened=unopened-nextnode;free(nodefree);}}voidshowresult(){inti;intfsr,fpr;/*在右岸上的人数*/intfsl,fpl;/*在左岸上的人数*/structSPQ*nodefree;printf(%d个传教士,result-pr);printf(%d个野人,result-sr);printf(%d个传教士,result-pl);printf(%d个野人,result-sl);for(i=1;iresultnum;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(传教士%8d%8d\t-\t%8d\n,fpl,result-spt,fpr);printf(野人%8d%8d\t-\t%8d\n,fsl,result-sst,fsr);printf(传教士%8d%8d\t-\t%8d\n,result-pl,result-spr