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

人工智能二-野人过河问题-实验3实验报告课程名称人工智能_____________实验项目野人过河问题_______________实验仪器电脑、visualC++_________系别计算机学院____________专业__计算机科学与技术_____班级/学号学生姓名___实验日期2010年月日_______成绩_______________________指导教师一、实验目的理解并熟悉掌握深度优先搜索和广度优先搜索地方法。二、实验内容题目：设有3个传教士和3个野人来到河边，打算乘一只船从右岸到左岸去。该船的负载能力为两人。在任何时候，如果野人人数超过传教士人数，野人就会把传教士吃掉。他们怎样才能用这条船安全的把所有人都渡过河去?三、代码和结果#include<stdio.h>#include<stdlib.h>#include<ctype.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(x>0){unopened->pr=x;break;}elseprintf("\n输入值应大于0！\n请重新输入");}printf("\n请输入野人人数");for(;;){scanf("%d",&x);if(x>0){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;i<openednum;i++){nodefree=opened;opened=opened->nextnode;free(nodefr