人工智能实验报告八数码难题.doc

《人工智能实验报告八数码难题.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、昆明理工大学信息工程与自动化学院学生实验报告（201—201学年第一学期）课程名称：开课实验室：年月日年级、专业、班学号姓名成绩实验项目名称八数码难题指导教师教师评语该同学是否了解实验原理：A.了解□B.基本了解□C.不了解□该同学的实验能力：A.强□B.中等□C.差□该同学的实验是否达到要求：A.达到□B.基本达到□C.未达到□实验报告是否规范：A.规范□B.基本规范□C.不规范□实验过程是否详细记录：A.详细□B.一般□C.没有□教师签名：年月日一、实验内容八数码难题，问题描述：在3×3方格棋盘上，分别放置了标有数字1,2,3,4,5,6,7

2、,8的八张牌，初始状态S0，目标状态S1如图所示，可以使用的操作有：空格上移，空格左移，空格右移，空格下移。只允许位于空格左，上，右，下方的牌移入空格。用广度优先搜索策略寻找从初始状态到目标状态的解路径。二、实验原理算法思想：这是一种盲目搜索算法。算法主要思想是从初始结点开始依次沿其上下左右四个方向扩展结点，并逐一检查这些后继结点是否为目标结点，若不等于目标结点则把该后继结点插入到数组末尾。然后取数组中未扩展的第一个结点重复以上操作，直到得到目标结点为止或在限定步数以内未得到解。-5-广度优先搜索策略数据结构：voidBfs(){queue

3、p>Queue;Queue.push(org);HashTable[org.myindex]=-1;while(NOTQueue.empty()){Mapnode=Queue.front();Queue.pop();for(intk=0;k<4;k++){Maptmp=node;tmp.position=node.position+derection[k];if(tmp.position<0

4、

5、tmp.position>8

6、

7、(k>1&&tmp.position/3!=node.position/3))continue;tmp.myindex=H

8、ashValue(node,k);if(0!=HashTable[tmp.myindex])continue;tmp.detail[node.position]=tmp.detail[tmp.position];tmp.detail[tmp.position]=0;HashTable[tmp.myindex]=node.myindex;//状态记录到hashtable中if(node.myindex==EndIndex)return;Queue.push(tmp);}}return;}三、所用仪器、材料1台PC及VISUALC++6.0软件四、实

9、验方法、步骤源代码见同一文件夹中bashuma.cpp部分程序代码：typedefstructNode{intnum[9];intdeepth;intdiffnum;intvalue;structNode*pre;structNode*next;structNode*parent;}numNode;-5-intmain(intargc,char*argv[]){open=create_numNode();close=create_numNode();open->pre=open->next=close->pre=close->next=NULL;

10、init();//由用户输入初始和目标状态numNode*p1;p1=create_numNode();p1->parent=NULL;p1->deepth=0;inti=0;for(i=0;i<9;i++){p1->num[i]=origin[i];}open_insert(open,p1);numNode_num=1;p1=open_getfirst(open);while(p1!=NULL){close_append(close,p1);if(expand(p1))returnEXIT_SUCCESS;p1=open_getfirst(op

11、en);}printf("Nosolution!");returnEXIT_SUCCESS;}voidinit(){while(1){printf("输入初始状态S0（请从左到右依次输入每行数字，0代表空格）:");chartemp[10];scanf("%s",&temp);inti=0;for(i=0;i<9&&temp[i]-'0'>=0&&temp[i]-'0'<=8;i++){origin[i]=temp[i]-'0';}printf("请输入目标状态S1:");scanf("%s",&temp);-5-intj=0;for

12、(j=0;j<9&&temp[j]-'0'>=0&&temp[j]-'0'<=8;j++){target[j]=temp[j]-'0';