学生实验报告实验课名称：人工智能实验项目名称：八数码实验专业名称：计算机科学与技术班级： 2012240201学号： 201224020102学生姓名：张璐教师姓名：陈亮亮2014年12 月13 日实验日期：2014 年12 月9 日实验室名称：明远2202最后，为提高程序的运行效率，减少程序扩展节点时搜索量，将当前0所处位置(i_0：0在s[3][3]中所处行号，j_0：0在s[3][3]中所处列号)也存储在DATA中。

五．源程序：struct array{int id;int depth;int Wx; //错位个数int moveNum;//计算移动距离int a[MAX_X][MAX_Y];int x; //0的横坐标（在数组里的）int y; //0的纵坐标};class EightDigital{public:EightDigital(int a[MAX_X][MAX_Y],int b[MAX_X][MAX_Y]);~EightDigital();bool safe(int x,int y); //判断与0相邻的位置能否交换，防止数组越界bool compare(); //判断是否到达目标void search(int x,int y); //搜索目标void addOpenTable(int x0,int y0,int x1,int y1);//x0,y0是交换前0的坐标，x1,y1是交换后0的坐标,加入open表void addCloseTable(); //create close tablevoid deleteOpenTable();void insertSort();void exchange(int x0,int y0,int x1,int y1); //交换数组值，移动0int Wx(); //计算错位个数void print(); //打印数组bool haveSolution();int moveNum();array closeTable[MAX_NUM];int countNumClose;private:array openTable[MAX_NUM];int depth;int countNum;int initX;int initY;int WxNum;int src[MAX_X][MAX_Y];int srcCopy[MAX_X][MAX_Y];int dst[MAX_X][MAX_Y];int tempA[MAX_X*MAX_Y];int tempB[MAX_X*MAX_Y];};EightDigital::EightDigital(int a[MAX_X][MAX_Y],int b[MAX_X][MAX_Y]) {depth=0;countNum=0;countNumClose=0;int i,j;for (i=0;i<MAX_X;++i){for(j=0;j<MAX_Y;++j){openTable[0].a[i][j]=a[i][j];src[i][j]=a[i][j];dst[i][j]=b[i][j];if (a[i][j]==0) {initX=i;initY=j;}tempA[i*MAX_Y+j]=a[i][j];tempB[i*MAX_Y+j]=b[i][j];}}openTable[0].x=initX;openTable[0].y=initY;openTable[0].depth=depth;openTable[0].id=countNum;openTable[0].Wx=Wx();openTable[0].moveNum=moveNum();}EightDigital::~EightDigital(){}bool EightDigital::safe(int x,int y){if (x>=0&&x<=3&&y>=0&&y<=3){return true;}return false;}bool EightDigital::compare(){int i,j;for (i=0;i<MAX_X;++i){for(j=0;j<MAX_Y;++j){if (openTable[0].a[i][j]!=dst[i][j]){return false;}}}return true;}void EightDigital::print(){int i,j;for (i=0;i<MAX_X;++i){for(j=0;j<MAX_Y;++j){cout<<openTable[0].a[i][j]<<" ";}cout<<endl;}}void EightDigital::search(int x,int y){addCloseTable();if (compare()){AfxMessageBox(L"已经找到解！");}else{++depth;if (safe(x,y-1))addOpenTable(x,y,x,y-1);if (safe(x,y+1))addOpenTable(x,y,x,y+1);if(safe(x-1,y))addOpenTable(x,y,x-1,y);if(safe(x+1,y))addOpenTable(x,y,x+1,y);insertSort();search(openTable[0].x,openTable[0].y);}}void EightDigital::exchange(int x0,int y0,int x1,int y1) {int temp;temp=openTable[0].a[x0][y0];openTable[0].a[x0][y0]=openTable[0].a[x1][y1];openTable[0].a[x1][y1]=temp;}void EightDigital::addOpenTable(int x0,int y0,int x1,int y1) {++countNum;exchange(x0,y0,x1,y1);openTable[countNum].x=x1;openTable[countNum].y=y1;openTable[countNum].depth=depth;openTable[countNum].id=countNum;for (int i = 0; i < MAX_X; i++){for (int j = 0; j < MAX_Y; j++){openTable[countNum].a[i][j]=openTable[0].a[i][j];}}openTable[countNum].moveNum=moveNum();openTable[countNum].Wx=Wx();exchange(x1,y1,x0,y0);}void EightDigital::insertSort(){array temp;for (int i = 1; i < countNum+1; ++i){for (int j=0;j<i;++j){if(openTable[j].moveNum+openTable[j].depth>openTable[i].moveNum+openTable[i].depth) {temp=openTable[i];for (int k=i;k>j;--k){openTable[k]=openTable[k-1];}openTable[j]=temp;}}}}int EightDigital::Wx(){int i,j,countWx=0;for (i=0;i<MAX_X;++i){for(j=0;j<MAX_Y;++j){if (openTable[countNum].a[i][j]!=0)if (openTable[countNum].a[i][j]!=dst[i][j])++countWx;}}}return countWx;}void EightDigital::addCloseTable(){closeTable[countNumClose].id=countNumClose;closeTable[countNumClose].depth=openTable[0].depth;closeTable[countNumClose].Wx=openTable[0].Wx;closeTable[countNumClose].x=openTable[0].x;closeTable[countNumClose].y=openTable[0].y;closeTable[countNumClose].moveNum=openTable[0].moveNum;for (int i=0;i<MAX_X;++i){for(int j=0;j<MAX_Y;++j){closeTable[countNumClose].a[i][j]=openTable[0].a[i][j];}}deleteOpenTable();++countNumClose;}void EightDigital::deleteOpenTable(){openTable[0].Wx=100;openTable[0].moveNum=100;}bool EightDigital::haveSolution(){int p[9]={0};int q[9]={0};int sp=0;int sq=0;for(int i=1;i<9;++i){for(int j=0;j<i;++j)if(tempA[i]<tempA[j]&&tempA[i]!=0&&tempA[j]!=0)++p[i];if(tempB[i]<tempB[j]&&tempB[i]!=0&&tempB[j]!=0)++q[i];}}for(int i=0;i<9;++i)sp+=p[i];for(int i=0;i<9;++i)sq+=q[i];if(sp%2==sq%2)return true;elsereturn false;}int EightDigital::moveNum(){int moveCountNum=0,s=0;for (int i=0;i<MAX_X;++i){for (int j = 0; j < MAX_Y; ++j){if(openTable[countNum].a[i][j]!=dst[i][j]&&openTable[countNum].a[i][j]!=0) {for (int w=0;w<MAX_X;++w){for (int k = 0; k < MAX_Y;++k){if (openTable[countNum].a[i][j]==dst[w][k]){moveCountNum=abs(w-i)+abs(k-j);s+=moveCountNum;}}}}}}return s;}。