八数码问题实验报告

《八数码问题》实验报告一、实验目的：熟练掌握启发式搜索A算法。二、实验内容：使用启发式搜索算法求解8数码问题。编制程序实现求解8数码问题A算法，采用估价函数wnfndnpn，其中：dn是搜索树中结点n的深度；wn为结点n的数据库中错放的棋子个数；pn为结点n的数据库中每个棋子与其目标位置之间的距离总和。三、实验原理：1.问题描述：八数码问题也称为九宫问题。在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格（以数字0来表示），与空格相邻的棋子可以移到空格中。要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。所谓问题的一个状态就是棋子在棋盘上的一种摆法。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。2.原理描述：启发式搜索（1）原理启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。（2）估价函数计算一个节点的估价函数，可以分成两个部分：1、已经付出的代价（起始节点到当前节点）；2、将要付出的代价（当前节点到目标节点）。节点n的估价函数)(nf定义为从初始节点、经过n、到达目标节点的路径的最小代价的估计值，即)(*nf=)(*ng+)(*nh。)(*ng是从初始节点到达当前节点n的实际代价；)(*nh是从节点n到目标节点的最佳路径的估计代价。)(*ng所占的比重越大，越趋向于宽度优先或等代价搜索；反之，)(*nh的比重越大，表示启发性能就越强。（3）算法描述：①把起始节点S放到OPEN表中，并计算节点S的)(Sf；②如果OPEN是空表，则失败退出，无解；③从OPEN表中选择一个f值最小的节点i。如果有几个节点值相同，当其中有一个为目标节点时，则选择此目标节点；否则就选择其中任一个节点作为节点i；④把节点i从OPEN表中移出，并把它放入CLOSED的已扩展节点表中；⑤如果i是个目标节点，则成功退出，求得一个解；⑥扩展节点i，生成其全部后继节点。对于i的每一个后继节点j：计算)(jf；如果j既不在OPEN表中，又不在CLOCED表中，则用估价函数f把它添入OPEN表中。从j加一指向其父节点i的指针，以便一旦找到目标节点时记住一个解答路径；如果j已在OPEN表或CLOSED表中，则比较刚刚对j计算过的f和前面计算过的该节点在表中的f值。如果新的f较小，则(I)以此新值取代旧值。(II)从j指向i，而不是指向他的父节点。(III)如果节点j在CLOSED表中，则把它移回OPEN表中。⑦转向②，即GOTO②。（3）算法流程图：四、实验结果输入矩阵：目标矩阵：283123145804760765五、实验小结通过本次试验，我对启发式搜索有了更加深入的了解。在实验中，通过对两种启发式搜索所扩在的节点数来看，)(np看来比)(n更加有效，能在复杂情况下求得更加优质的解，避免不必要的节点的扩展。所以，要更好地定义一个估价函数还有待深入讨论。源代码：#includestdio.h#definenum3//宏定义数码的行列数为3/*显示当前待调整数码矩阵*/voidshow(intbegin[num][num]){for(inti=0;inum;i++){for(intj=0;jnum;j++)printf(%d,begin[i][j]);printf(\n);}printf(\n);}/*交换数码中的begin[row_one][column_one]与begin[row_two][column_two]这两个数*/voidexchange(intbegin[num][num],introw_one,intcolumn_one,introw_two,intcolumn_two){inttemp;temp=begin[row_two][column_two];begin[row_two][column_two]=begin[row_one][column_one];begin[row_one][column_one]=temp;}/*判断待调整的数码与最终数码相比正确位置数码的个数*/intjudge(intbegin[num][num],intend[num][num]){intcount=0;//count记录数码中正确位置的个数for(inti=0;inum;i++)//检查当前图形的正确度for(intj=0;jnum;j++){if(begin[i][j]==end[i][j]&&end[i][j]!=0)count++;}returncount;//返回数码中正确位置的个数}/*将待调整数码从开始位置移动到终止位置，并将其过程输出*/intyidong(intbegin[num][num],intend[num][num],intright,intjishu,intji_shu[50][3][3],intbiaoji,introw,intcolumn)//biaoji存储上一轮移动的反方向代号{inttemp_zhi;show(begin);//显示数组矩阵if(jishu=20)return0;intnode;//,node为标记inttemp;//存储当前待调整数码正确的个数for(intq=0;qjishu;q++)//检查交换后的end[][]图形是否先前已经遍历过了{node=1;for(intw=0;wnum&&node;w++)for(intr=0;rnum&&node;r++)if(ji_shu[q][w][r]!=begin[w][r])node=0;if(node==1)//如果先前遍历过，返回0{return0;}}for(inti=0;inum;i++)for(intj=0;jnum;j++)ji_shu[jishu][i][j]=begin[i][j];if(right==num*num-1)//如果待调整数码与最终数码完全相同时，返回1return1;if(row0&&biaoji!=0)//存储0的位置不是在第一行{exchange(begin,row-1,column,row,column);//将0与其上面的元素交换存储位置temp=judge(begin,end);if(tempright)//如果交换后正确数码的个数不大于原来正确数码的个数exchange(begin,row-1,column,row,column);//再将其交换回来elseif(temp=right)//如果交换后正确数码的个数大于或等于原来正确数码的个数{temp_zhi=yidong(begin,end,temp,jishu+1,ji_shu,2,row-1,column);if(temp_zhi==1)//进行下一步的移动return1;exchange(begin,row-1,column,row,column);//再将其交换回来}}if(column0&&biaoji!=1){exchange(begin,row,column-1,row,column);//将0与其左边的元素交换存储位置temp=judge(begin,end);if(tempright)exchange(begin,row,column-1,row,column);elseif(temp=right){temp_zhi=yidong(begin,end,temp,jishu+1,ji_shu,3,row,column-1);if(temp_zhi==1)return1;exchange(begin,row,column-1,row,column);}}if(rownum-1&&biaoji!=2){exchange(begin,row+1,column,row,column);//将0与其下面的元素交换存储位置temp=judge(begin,end);if(tempright)exchange(begin,row+1,column,row,column);elseif(temp=right){temp_zhi=yidong(begin,end,temp,jishu+1,ji_shu,0,row+1,column);if(temp_zhi==1)return1;exchange(begin,row+1,column,row,column);}}if(columnnum-1&&biaoji!=3){exchange(begin,row,column+1,row,column);//将0与其右边的元素交换存储位置temp=judge(begin,end);if(tempright)exchange(begin,row,column+1,row,column);elseif(temp=right){temp_zhi=yidong(begin,end,temp,jishu+1,ji_shu,1,row,column+1);if(temp_zhi==1)return1;exchange(begin,row,column+1,row,column);}}return0;//移动失败，返回0}/*有用户输入待调整的数码矩阵最初状态的数，并将其存入到begin[][]数组中*/voidshuru(intbegin[][num],intblank[]){inttemp,node,zero=0;for(inti=0;inum;i++)for(intj=0;jnum;j++){node=1;printf(请输入第%d行，第%d列的元素的值：,i+1,j+1);scanf(%d,&temp);for(intq=0;q=i&&node==1;q++)//当输入的值有重复的，提示重新输入for(intw=0;wj;w++)if(temp==begin[q][w]){printf(输入重复，请重新输入\n);node=0;j--;break;}if(temp0||tempnum*num-1)//当输入的值不是在数码的区间范围内时，提示重新输入{printf(请输入从%d到%d的数\n,zero,num*num-1);node=0;j--;}if(node==1)//如果输入满足条件{if(temp==0)//如果输入的值为零，由blank[0]记录行号，blank[1]记录列号{blank[0]=i;blank[1]=j;}begin[i][j]=temp;//将满足条件的值存储起来}}}intmain(){intjishu=0,ji_shu[50][3][3];//jishu存储已经遍历过的八数码图形的个数，jishu[][][]存储已经遍历过的八数码图形的形状introw;//存储数字零的行数intcolumn;//存储数字零的列数intbegin[num][num],blank[2],count=1;intend[num][num]={1,2,3,8,0,4,7,6,5};//给最终状态的数码矩阵赋值printf(-------%d数码游戏开始！--------\n,num);shuru(begin,blank);//输入带调整状态的数码矩阵的值row=blank[0];column=blank[1];if(yidong(begin,end,judge(begin,end),jishu,ji_shu,4,row,column)==0)printf(\n此8数码的问题可能无解！);elseshow(begin);getchar();getchar();return0;}