人工智能实验2

实验二图搜索技术一、实验目的1．加深学生对图搜索技术的理解。2．掌握图搜索基本编程方法。3．能初步运用图搜索技术解决一些实际应用问题。二、预习要求1．复习广度优先搜索算法。2．复习深度优先搜索算法。3．设计初步的搜索算法。三、实验内容1．（必做）利用深度优先和广度优先搜索技术解决传道士和野人问题。修道士和野人问题如下：有三个传教士和三个野人一起来到河边准备渡河，河边有一条空船，且传教士和野人都会划船，但每次最多可供两人乘渡。河的任何一岸以及船上一旦出现野人人数超过传教士人数，野人就会把传教士吃掉。为完全地渡河，传教士应如何规划渡河方案？2．（选做）若传教士和野人的数目均为五人，渡船至多可乘三人，请定义一个启发函数，并给出相应的搜索树。四、实验要求：1．程序运行时，应能在屏幕上显示结果。2.界面直观、友好。3．交实验报告。一、实验代码：#includestdio.h#includemalloc.h#includestdlib.htypedefstruct{intxds;//修道士个数intyr;//野人个数intcw;//船的位置}DataType;DataTypearray[50000];typedefstructnode//结构体定义{DataTypedata;structnode*son;//儿子节点structnode*bro;//兄弟节点structnode*par;//双亲节点structnode*next;}Link;voidLinkinit(Link**head)//初始化操作{*head=(Link*)malloc(sizeof(Link));//申请动态空间(*head)-son=NULL;(*head)-bro=NULL;(*head)-par=NULL;(*head)-next=NULL;}voidinsertson(Link*head,DataTypex)//在邻接表中插入儿子结点的操作{Link*q,*s;q=(Link*)malloc(sizeof(Link));q-data=x;head-son=q;//将x插入给头结点的儿子指针s=head;while(s-next!=NULL)s=s-next;q-par=head;q-son=NULL;q-bro=NULL;s-next=q;q-next=NULL;}voidinsertbro(Link*head,DataTypex)//在邻接表中插入兄弟结点的操作，所有的兄弟结点都指向他们右边的结点{Link*q,*s;q=(Link*)malloc(sizeof(Link));s=head-son;q-data=x;while(s-bro!=NULL)s=s-bro;s-bro=q;s-next=q;q-next=NULL;q-bro=NULL;q-par=head;q-son=NULL;}intboatcase(DataTypex,intn)//生成所有情况；{inti=0,a,b,t=0;if(x.cw)//在此岸,上船的人多优先{a=0;b=n-a;//a为修道士b为野人while(a+b=1)//当船上有人时{t++;while(b=0)//当野人个数不为负数{array[i].xds=a;array[i].yr=b;i++;a++;b--;}a=0;//船上空位个数b=n-a-t;}}else//在对岸,上船的人少优先{a=1;b=0;t=0;while(a+b=n){t++;//船上的人数while(a=0){array[i].xds=a*(-1);array[i].yr=b*(-1);i++;a--;b++;}a=array[0].xds*(-1)+t;b=0;}}returni;//i为总数量}intsafe(DataTypex,intn)//安全性检测{//起始目的if((x.xds=x.yr||x.xds==0)&&((n-x.xds)=(n-x.yr)||x.xds==n)&&x.xds=0&&x.xds=n&&x.yr=0&&x.yr=n)return1;//船上修道士elsereturn0;}voidprint(Link*q,Link*p)//打印安全渡河的过程,当船到对岸时,把对岸当作其始岸,此岸当作彼岸{DataTypea[100];inti=1;a[0].cw=0;a[0].xds=0;a[0].yr=0;while(q!=p)//避免出现相同情况而循环{a[i++]=q-data;//将一次过河的情况给b[i]q=q-par;}while((--i)-1)//输出过河图{printf((%d%d%d),a[i].xds,a[i].yr,a[i].cw);if(!(a[i].xds==0&&a[i].yr==0&&a[i].cw==0)){if(a[i].cw==1)printf(--(%d%d)--(%d%d0)\n,a[i].xds-a[i-1].xds,a[i].yr-a[i-1].yr,a[i-1].xds,a[i-1].yr);//a[i].xds-a[i-1].xds表示过河过程中船上的修道士数,a[i].yr-a[i-1].yr表示过河过程中船上的野人数elseprintf(--(%d%d)--(%d%d1)\n,(a[i].xds-a[i-1].xds)*(-1),(-1)*(a[i].yr-a[i-1].yr),a[i-1].xds,a[i-1].yr);}}printf(渡河成功!\n);}voidguangdu(Link*p,intn,intc)//广度搜索{Link*q,*t;DataTypetem;inti,flag1,flag2,g=0,j,count=0;q=p-son;while(q!=NULL)//逐个搜索儿子结点{flag1=0;//等于0表示插入儿子结点,1表示插入兄弟结点j=boatcase(q-data,c);//可能过河的情况for(i=0;ij;i++)//搜索兄弟结点{tem.xds=q-data.xds-array[i].xds;tem.yr=q-data.yr-array[i].yr;tem.cw=1-q-data.cw;t=q;if(safe(tem,n))//是否安全{flag2=1;//1表示没有死循环while(t!=p)//保证不会出现循环{if(tem.xds==t-data.xds&&tem.yr==t-data.yr&&tem.cw==t-data.cw){//出现相当情况时候flag2=0;break;}t=t-par;}if(flag2==1){if(flag1==0)//插入儿子结点{insertson(q,tem);flag1=1;}else//插入兄弟结insertbro(q,tem);if(tem.xds==0&&tem.yr==0&&tem.cw==0){print(q,p);count++;}}}}q=q-next;}if(count==0)printf(无法成功渡河!\n);elseprintf(有%d种渡河方式。\n,count);}intmain(){intn,c,back;Link*p;DataTypetem;printf(***********************欢迎进入野人传教士游戏的实现程序***********************\n);printf(本游戏的游戏规则为：野人和传教士渡河，河的任何一岸以及船上一旦出现野人人数超过传\n);printf(教士人数,野人就会把传教士吃掉，实现野人和传教士完全渡过河\n);printf(******************************************************************************\n);while(back){printf(请输入修道士与野人的人数n:\n);scanf(%d,&n);if(n==0)break;printf(请输入船可容纳的人数c:\n);scanf(%d,&c);tem.xds=n;tem.yr=n;tem.cw=1;Linkinit(&p);//初始化邻接表;insertson(p,tem);//将初始状态作为头结点的孩子结点；guangdu(p,n,c);//进行广度搜索；printf(是否继续?(继续1,退出0)\n);scanf(%d,&back);}}二、实现结果：