C语言解八数码问题之人工智能实验报告

《人工智能》上机实验2基于人工智能的状态空间搜索策略研究——八数码问题求解（一）实验软件TC2.0或VC6.0编程语言或其它编程语言（二）实验目的1.熟悉人工智能系统中的问题求解过程；2.熟悉状态空间的盲目搜索和启发式搜索算法的应用；3.熟悉对八数码问题的建模、求解及编程语言的应用。（三）需要的预备知识1.熟悉TC2.0或VC6.0编程语言或者其它编程语言；2.熟悉状态空间的宽度优先搜索、深度优先搜索和启发式搜索算法；3.熟悉计算机语言对常用数据结构如链表、队列等的描述应用；4.熟悉计算机常用人机接口设计。（四）实验数据及步骤1.实验内容八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。2541233784186765(a)初始状态(b)目标状态图1八数码问题示意图请任选一种盲目搜索算法（深度优先搜索或宽度优先搜索）或任选一种启发式搜索方法（A算法或A*算法）编程求解八数码问题（初始状态任选），并对实验结果进行分析，得出合理的结论。2.实验步骤（1）分析算法基本原理和基本流程；程序采用宽度优先搜索算法，基本流程如下：3起始把s放入open表失败成功是否open表为空表？是把open表中的第一个节点n移入close表否扩展节点n，把其后裔放入open表的前头是否有后继节点为目标节点？否是4（2）确定对问题描述的基本数据结构，如Open表和Closed表等；OPENCLOSEDSA,B,CSB,C,D,E,FS,AC,D,E,F,GS,A,BD,E,F,G,HS,A,B,CE,F,G,H,I,JS,A,B,C,DF,G,H,I,JK,LS,A,B,C,D,EG,H,I,JK,L,M,NS,A,B,C,D,E,FH,I,JK,L,M,N,O,PS,A,B,C,D,E,F,G（3）编写算符运算、目标比较等函数；（4）编写输入、输出接口；（5）全部模块联调；（6）撰写实验报告。（五）实验报告要求所撰写的实验报告必须包含以下内容：1.算法基本原理和流程框图；2.基本数据结构分析和实现；3.编写程序的各个子模块，按模块编写文档，含每个模块的建立时间、功能、输入输出参数意义和与其它模块联系等；4.程序运行结果，含使用的搜索算法及搜索路径等；5.实验结果分析；6.结论；7.提供全部源程序及软件的可执行程序。5附：实验报告格式一、实验问题二、实验目的三、实验原理四、程序框图五、实验结果及分析六、结论七、源程序及注释#includestdio.h#includeconio.hintn,m;typedefstructNode{charmatrix[10];/*存储矩阵*/charoperate;/*存储不可以进行的操作，L代表不能左移R代表不能右移U代表不能上移D代表不能下移*/charextend;/*是否可以扩展，Y代表可以，N代表不可以*/intfather;/*指向产生自身的父结点*/}Node;charstart[10]={83426517};/*此处没有必要初始化*/charend[10]={12384765};/*此处没有必要初始化*/Nodebase[4000];intresult[100];/*存放结果的base数组下标号，逆序存放*/intmatch()/*判断是否为目标*/{inti;for(i=0;i9;i++){if(base[n-1].matrix[i]!=end[i]){return0;}}return1;}voidshow()/*显示矩阵的内容*/{inti=1;while(m=0){6intmm=result[m];//clrscr();printf(\n\n\n状态方格\t\t步骤%d,i);printf(\n\n\n\n\n\t\t\t%c\t%c\t%c\n,base[mm].matrix[0],base[mm].matrix[1],base[mm].matrix[2]);printf(\n\n\t\t\t%c\t%c\t%c\n,base[mm].matrix[3],base[mm].matrix[4],base[mm].matrix[5]);printf(\n\n\t\t\t%c\t%c\t%c\n,base[mm].matrix[6],base[mm].matrix[7],base[mm].matrix[8]);//sleep(1);m--;i++;}}voidleave()/*推理成功后退出程序之前要执行的函数，主要作用是输出结果*/{n--;while(base[n].father!=-1){result[m]=n;m++;n=base[n].father;}result[m]=0;result[m+1]='\0';show();//clrscr();printf(\n\n\n\n\n\n\n\n\n\t\t\t\t搜索结束\n\n\n\n\n\n\n\n\n\n);getch();//exit(0);}intleft(intx)/*把下标为X的数组中的矩阵的空格左移*/{inti,j;charch;for(i=0;i9;i++){if(base[x].matrix[i]=='')break;}if(i==0||i==3||i==6||i==9){return0;7}for(j=0;j9;j++){base[n].matrix[j]=base[x].matrix[j];}ch=base[n].matrix[i-1];base[n].matrix[i-1]=base[n].matrix[i];base[n].matrix[i]=ch;base[n].operate='R';base[n].extend='Y';base[n].father=x;base[x].extend='N';n++;if(match(i))leave();return1;}intright(intx)/*把下标为X的数组中的矩阵的空格右移*/{inti,j;charch;for(i=0;i9;i++){if(base[x].matrix[i]=='')break;}if(i==2||i==5||i==8||i==9){return0;}for(j=0;j9;j++){base[n].matrix[j]=base[x].matrix[j];}ch=base[n].matrix[i+1];base[n].matrix[i+1]=base[n].matrix[i];base[n].matrix[i]=ch;base[n].operate='L';base[n].extend='Y';8base[n].father=x;base[x].extend='N';n++;if(match(i))leave();return1;}intup(intx)/*把下标为X的数组中的矩阵的空格上移*/{inti,j;charch;for(i=0;i9;i++){if(base[x].matrix[i]=='')break;}if(i==0||i==1||i==2||i==9){return0;}for(j=0;j9;j++){base[n].matrix[j]=base[x].matrix[j];}ch=base[n].matrix[i-3];base[n].matrix[i-3]=base[n].matrix[i];base[n].matrix[i]=ch;base[n].operate='D';base[n].extend='Y';base[n].father=x;base[x].extend='N';n++;if(match(i))leave();return1;}intdown(intx)/*把下标为X的数组中的矩阵的空格下移*/{inti,j;9charch;for(i=0;i9;i++){if(base[x].matrix[i]=='')break;}if(i==6||i==7||i==8||i==9){return0;}for(j=0;j9;j++){base[n].matrix[j]=base[x].matrix[j];}ch=base[n].matrix[i+3];base[n].matrix[i+3]=base[n].matrix[i];base[n].matrix[i]=ch;base[n].operate='U';base[n].extend='Y';base[n].father=x;base[x].extend='N';n++;if(match(i))leave();return1;}main(){inti;chara[20],b[20];n=1;//textcolor(LIGHTGREEN);//clrscr();/*以下是输入初始和目标矩阵，并把输入的0转换为空格*/printf(Pleaseinputthestart9chars:);scanf(%s,a);printf(Pleaseinputtheend9chars:);scanf(%s,b);10for(i=0;i9;i++){if(a[i]=='0'){start[i]='';continue;}if(b[i]=='0'){end[i]='';continue;}start[i]=a[i];end[i]=b[i];}start[9]='\0';end[9]='\0';for(i=0;i9;i++){base[0].matrix[i]=start[i];}base[0].operate='N';base[0].extend='Y';base[0].father=-1;/*以上是为第一个base数组元素赋值*/for(i=0;n4000;i++){if(base[i].extend=='Y'){if(base[i].operate=='L'){right(i);up(i);down(i);}if(base[i].operate=='R'){left(i);up(i);down(i);}if(base[i].operate=='U'){left(i);right(i);down(i);}11if(base[i].operate=='D'){left(i);right(i);up(i);}if(base[i].operate=='N'){left(i);right(i);up(i);down(i);}}}}