人工智能实验报告八数码难题(共6页).doc
精选优质文档-倾情为你奉上昆明理工大学信息工程与自动化学院学生实验报告（ 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,8的八张牌，初始状态S0，目标状态S1如图所示，可以使用的操作有：空格上移，空格左移，空格右移，空格下移。只允许位于空格左，上，右，下方的牌移入空格。用广度优先搜索策略寻找从初始状态到目标状态的解路径。 二、实验原理算法思想：这是一种盲目搜索算法。算法主要思想是从初始结点开始依次沿其上下左右四个方向扩展结点，并逐一检查这些后继结点是否为目标结点，若不等于目标结点则把该后继结点插入到数组末尾。然后取数组中未扩展的第一个结点重复以上操作，直到得到目标结点为止或在限定步数以内未得到解。广度优先搜索策略数据结构：void Bfs() queue<Map> Queue; Queue.push(org); HashTable org.myindex = -1; while( NOT Queue.empty() ) Map node = Queue.front(); Queue.pop( ); for(int k =0 ; k < 4; k + ) Map tmp = node; tmp.position = node.position + derectionk; if(tmp.position < 0 | tmp.position > 8 | ( k > 1 && tmp.position / 3 != node.position /3 ) ) continue; tmp.myindex = HashValue( node , k ); if(0 != HashTabletmp.myindex ) continue; tmp.detail node.position = tmp.detail tmp.position ; tmp.detail tmp.position = 0 ; HashTabletmp.myindex = node.myindex; / 状态记录到hashtable中 if( node.myindex = EndIndex ) return ; Queue.push( tmp ); return ; 三、所用仪器、材料1台PC及VISUAL C+6.0软件四、实验方法、步骤源代码见同一文件夹中bashuma.cpp部分程序代码：typedef struct Node int num9; int deepth; int diffnum; int value; struct Node * pre; struct Node * next; struct Node * parent;numNode; int main ( int argc, char *argv ) open=create_numNode(); close=create_numNode(); open->pre=open->next=close->pre=close->next=NULL; init(); /由用户输入初始和目标状态 numNode *p1; p1=create_numNode(); p1->parent=NULL; p1->deepth=0; int i=0; for ( i=0; i<9; i+) p1->numi=origini; open_insert(open,p1); numNode_num=1; p1=open_getfirst(open); while (p1!=NULL) close_append(close,p1); if(expand(p1) return EXIT_SUCCESS; p1=open_getfirst(open); printf("No solution!n"); return EXIT_SUCCESS; void init ( ) while(1) printf("输入初始状态S0（请从左到右依次输入每行数字，0代表空格）:n"); char temp10; scanf("%s",&temp); int i=0; for ( i=0;i<9 && tempi-'0'>=0 && tempi-'0'<=8; i+) origini=tempi-'0' printf("请输入目标状态S1:n"); scanf("%s",&temp); int j=0; for ( j=0; j<9 && tempj-'0'>=0 && tempj-'0'<=8; j+) targetj=tempj-'0' system("cls"); if ( i=9&&j=9) break; int operate(int m, int op) int blank; blank=0; while (mblank!=0 && blank<9 ) +blank; if (blank=9) return 1; switch (op) case 1: /* up */ if (blank>2) swap(m+blank,m+blank-3); break; case 2: /* down */ if (blank<6) swap(m+blank,m+blank+3); break; case 3: /* left */ if (blank!=0 && blank!=3 && blank!=6) swap(m+blank,m+blank-1); break; case 4: /* right */ if (blank!=2 && blank!=5 && blank!=8) swap(m+blank,m+blank+1); break; default : return 1; return 0;五、实验过程原始记录六、实验总结：人工智能这门课程综合了许多学科的知识，这些知识面十分广，以及它的应用也是十分广泛的，才刚开始学习的时候就会感觉有点复杂，因为它毕竟综合了一些我们还没有学过的知识。通过这次实验，我对八数码难题有了更进一步的认识，对广度优先搜索策略更加熟悉，广度优先搜索策略在有解的情形总能保证搜索到最短路经，也就是移动最少步数的路径。在进行广度优先搜索时候，将父结点所在的数组索引记录在子结点中了，所以得到目标排列的时候，我们只要从子结点逆向搜索就可以得到最优搜索路径了。 这次实验还让我对人工智能的应用有了更全面的认识，让我对今后的学习有了一个更加明确的目标。专心-专注-专业
