搜索
实验报告姓名：叶子烽学号：2220132380班级：软件二班实验名称：启发式搜索课程名称：人工智能实验日期：2015.11.09实验环境：VisualC++实验目的以及内容：1、实验内容：使用启发式搜索算法求解八数码问题。（1）编制程序实现求解八数码问题A*算法，采用估价函数其中：d(n)是搜索树中节点n的深度；w(n)为节点n的数据库中错放的棋子个数；p(n)为节点n的数据库中的每个棋子与其目标位置之间的距离的总和。（2）分析上述（1）中的两种估价函数求解八数码问题的效率差别，给出一个是p(n)的上界的h(n)的定义，并测试使用该估价函数是否使算法失去可采纳性。2、实验目的：熟练的掌握启发式搜索A*算法及其可采纳性。3.实验原理：八数码问题是在3行和3列构成的九宫棋盘上放置数码为1到8的8个棋盘，剩下一个空格的移动来不断改变棋盘的布局，求解这类问题的方法是：给定初始布局（即初始状态）和目标布局（即目标状态），定义操作算子的直观方法是为每个棋牌制定一套可能的走步》上，下，左，右四种移动，再根据所定义的启发式搜索函数在搜索过程中选择最合适的操作算子，得到最优的路径。代码：#includestdio.h#definenum3voidshow(intbegin[num][num]){for(inti=0;inum;i++){for(intj=0;jnum;j++)printf(%d,begin[i][j]);printf(\n);}printf(\n);}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;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){inttemp_zhi;show(begin);if(jishu=20)return0;intnode;inttemp;for(intq=0;qjishu;q++){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){return0;}}for(inti=0;inum;i++)for(intj=0;jnum;j++)ji_shu[jishu][i][j]=begin[i][j];if(right==num*num-1)return1;if(row0&&biaoji!=0){exchange(begin,row-1,column,row,column);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);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);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);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;}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]=i;blank[1]=j;}begin[i][j]=temp;}}}intmain(){intjishu=0,ji_shu[50][3][3];introw;intcolumn;intbegin[num][num],blank[2],count=1;intend[num][num]={1,2,3,8,0,4,7,6,5};printf(-------8数码游戏开始！--------\n);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;}实验截图：实验总结：1、A*搜索算法：取g(n)=d(n)，h(n)=w(n)，其中w(n)表示以目标为基准，结点n的状态中每一个数码牌与其目标位置之间的距离（不考虑夹在其间的数码牌）的总和，由于从结点n转换成目标结点至少需要w(n)步，所以对任意n，恒有w(n)≤h*(n)。所以该估价函数并未失去其可采纳性。2、在做这个实验前,我以为不会难做,直到做完测试实验时,我才知道其实并不容易做,但学到的知识与难度成正比,在这次实验中，我学到很多东西，加强了我的动手能力，并且培养了我的独立思考能力，使我受益匪浅。