昆明理工大学人工智能实验报告

昆明理工大学信息工程与自动化学院学生实验报告〔2013——2014学年第一学期〕课程名称：人工智能导论开课实验室：信自楼234室2013年11月5日年级、专业、班学号姓名成绩实验工程名称状态空间搜索实验—八数码问题求解指导教师教师评语该同学是否了解实验原理：A.了解□B.根本了解□C.不了解□该同学的实验能力：A.强□B.中等□C.差□该同学的实验是否到达要求：A.到达□B.根本到达□C.未到达□实验报告是否标准：A.标准□B.根本标准□C.不标准□实验过程是否详细记录：A.详细□B.一般□C.没有□教师签名：年月日一、实验问题1、用软件编程解决八数码问题二、实验目的1、熟悉人工智能求解八数码问题，以及对人工智能深入了解。2、熟悉状态空间的盲目搜索、启发式搜索，和A*算法。3、熟悉人工智能系统中的问题求解过程。三、实验原理1、将初始节点s放入open表中2、假设open表为空那么推出3、移出open表中的第一个节点N放入close表中，并冠以顺序编号n，4、假设目标节点Sg=N，那么搜索成功，结束5、假设N不可扩展，那么转入第2步四、程序框图StartStart把S放入open表中判断open表是否为空表YESEND把open表的第一个节点移到close表中扩展节点n，把其后裔放入open表前面是否有后继节点为目标节点YESENDNO五、实验结果及分析1、通过逆序数的奇数偶数来判断。因为在空白移动过程中，数码的逆序数不改变。左右移动，数码序列不变。上下移动，数码序列中某个数字那么移动了两位。八数码问题为3*3矩阵，3为奇数，故逆序数不作改变。故可通过判断当前状态S的逆序数以及目标状态的数字序列的逆序数的奇偶性是否相同来判断该问题是否可解。2、是否到达目标节点，将当前节点和目标节点进行比拟3、对于f(n)的考虑，f〔n〕是否最小，选择最小的扩展，假设几个相等的状态同时出现，那么随机选一个。4、将Open表中的所有节点进行排序选择估价函数f(n)最优的进行扩展。第二种选择就是选择当前层扩展的节点中选择最优的f(n)进行扩展。六、结论1、尽管明白怎么样解决八数码问题，但用电脑编程还是不会编。虽然学过C语言，由于不用也生疏了。以后对学过的只是温故而知新。2、通过本次试验我对启发式搜索有了更加深入的了解。在实验中通过对两种启发式搜索所扩在的节点数来看更加有效能在复杂情况下求得更加优质的解防止不必要的节点的扩展。使搜索的速度更快。3、八数码的启发式搜索、A算法等用书面的形式很容易表示出来，但用计算机能读懂的语言〔如C语言〕表示，这个转换的的过程很困难。七、源程序及注释#include<stdio.h>#include<conio.h>intn,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;i<9;i++){if(base[n-1].matrix[i]!=end[i]){return0;}}return1;}voidshow()/*显示矩阵的内容*/{inti=1;while(m>=0){intmm=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;i<9;i++){if(base[x].matrix[i]=='')break;}if(i==0||i==3||i==6||i==9){return0;}for(j=0;j<9;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;i<9;i++){if(base[x].matrix[i]=='')break;}if(i==2||i==5||i==8||i==9){return0;}for(j=0;j<9;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';base[n].father=x;base[x].extend='N';n++;if(match(i))leave();return1;}intup(intx)/*把下标为X的数组中的矩阵的空格上移*/{inti,j;charch;for(i=0;i<9;i++){if(base[x].matrix[i]=='')break;}if(i==0||i==1||i==2||i==9){return0;}for(j=0;j<9;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;charch;for(i=0;i<9;i++){if(base[x].matrix[i]=='')break;}if(i==6||i==7||i==8||i==9){return0;}for(j=0;j<9;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;/*以下是输入初始和目标矩阵，并把输入的0转换为空格*/printf("3*3方格初始状态:");scanf("%s",a);printf("3*3方格结束状态:");scanf("%s",b);for(i=0;i<9;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;i<9;i++){base[0].matrix[i]=start[i];}base[0].operate='N';base[0].extend='Y';base[0].father=-1;/*以上是为第一个base数组元素赋值*/for(i=0;n<4000;i++){if(base[i].extend=='Y'){if(base[i].operate=='L'){right(i);up(i);down(i);}if(base[i].operate=='R'){left(i);