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

1、昆明理工大学信息工程与自动化学院学生实验报告(201201学年第一学期)课程名称：开课实验室：年 月曰年级、专业、班学号姓名成绩实验项目名称八数码难题指导教师教该同学是否了解实验原理：A.了解口B.基本了解口C.不了解口师该同学的实验能力：A强 口B.中等C.差该冋学的实验是否达到要求：A.达到口B.基本达到口C.未达到口评实验报告是否规范：A.规范口B.基本规范口C.不规范口实验过程是否详细记录：A.详细口B.- 般C.没有语教师签名：年月曰、实验内容八数码难题，问题描述：在3X3方格棋盘上，分别放置了标有数字1,234,5,6,7,8的八张牌，初始状态SO,目标状态S1如图所示，可以使用的

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

3、 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 8 | ( k 1 & tmp.position / 3 != node.position /3 ) )continue;tmp.myindex = HashValue( node , k );if(0 != HashTabletmp.myindex ) continue; tm

4、p.detail node.position =tmp.detail tmp.position ; tmp.detail tmp.position = 0 ;HashTabletmp.myindex = node.myindex;/状态记录至U hashtable中if( node.myindex = EndIndex ) return ; Queue.push( tmp );return ;三、所用仪器、材料1台PC及VISUAL C+6.0软件四、实验方法、步骤源代码见同一文件夹中bashuma.cpp部分程序代码：typedef struct Node int num9;int deep

5、th;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

6、=0;for ( i=0; inumi=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(输入初始状态SO(请从左到右依次输入每行数字，0代表空格)：n);char temp10;scan

7、f(%s,&temp);int i=0;for ( i=0;i=0 & tempi-0=8; i+)origini=tempi-0;printf(请输入目标状态S1：n);scanf(%s,&temp);int j=0;for ( j=0; j=0 & tempj-0=8; j+)targetj=tempj-0;system(cls);if ( i=9&j=9)break;int operate nt m, int op)int bla nk;bla nk=0;while (mblank!=0 & blank2)swap(m+bla nk,m+b

8、la nk-3); break;case 2: /* dow n */if (bla nk6)swap(m+bla nk,m+bla nk+3); break;case 3: /* left */if (bla nk!=0 & bla nk!=3 & bla nk!=6) swap(m+bla nk,m+bla nk-1); break;case 4: /* right */if (blank!=2 & blank!=5 & blank!=8) swap(m+bla nk,m+bla nk+1); break;default : retur n 1;return 0;五、Step0：*83104765Step1：203184765Step2：023184765Step3：实验过程原始记录回HG:VCDebugbashuma* G:VCDebuqbashu六、实验总结:人工智能这门课程综合了许多学科的知识，这些知识面十分广，以及它 的应用也是十分广泛的，才刚开始学习的时候就会感觉有点复杂，因为它毕竟 综合了一些我们还没有学过的知识。通过这次实验，我对八数码难题有了更进 一步的认识，对广度优先搜索策略更加熟悉，广度优先搜索策略在有解的情形 总能