A星算法求八数码问题实验报告

人工智能实验报告实验名称：八数码问题姓名：xx学号：2012210xxxx计算机学院2014年1月14日一．实验目的掌握A*的思想，启发式搜索，来求解在代价最小的情况下将九宫格从一个状态转为另状态的路径。二．实验内容给定九宫格的初始状态，要求在有限步的操作内，使其转化为目标状态，且所得到的解是代价最小解(即移动的步数最少)并打印出求解路径。例如283164705283164705三、A*算法思想：1、思想：A*算法是一种静态路网中求解最短路最有效的直接搜索方法。估价值与实际值越接近，估价函数取得就越好2、原理：估价函数公式表示为：f(n)=g(n)+h(n),其中f(n)是从初始点经由节点n到目标点的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取：估价值h(n)=n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。并且如果h(n)=d(n)，即距离估计h(n)等于最短距离，那么搜索将严格沿着最短路径进行此时的搜索效率是最高的。如果估价值实际值,搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。四、算法流程：是是，输出路径否，生成n的所有子状态Heuristic_Search(启发式搜索)While（未拓展表不为空？）从未拓展表中删除第一个状态nN为目标状态？Case:此子状态不在拓展表和未拓展表中Case:此子状态在未拓展表中Case:此子状态在拓展表计算该子状态的估价函数值；记录比已有的路径更短的路径记录比已有的路径更短的路径返回五、关键技术：1、使用了CreateChild（）函数，求得了任意未拓展九宫格的扩展结点，便于拓展子空间，搜索所有情况。关键代码：boolCreateChild(NOExtendns[],NOExtendne){inti,j,k=0;for(i=0;i3;i++){for(j=0;j3;j++){if(ne.cur_sudoku.num[i][j]==0){//寻找九宫格空缺所在的坐标if(i-1=0){//将空格向上移动CopySudoku(ns[k].cur_sudoku,ne.cur_sudoku);//先把未改变的九宫格复制给九宫格数组的某一元素ns[k].cur_sudoku.num[i][j]=ne.cur_sudoku.num[i-1][j];//然后仅改变此二维九宫格的两项值即可ns[k].cur_sudoku.num[i-1][j]=0;ns[k].dx=1;k++;}if(j+1=2){//将空格向右移动CopySudoku(ns[k].cur_sudoku,ne.cur_sudoku);ns[k].cur_sudoku.num[i][j]=ns[k].cur_sudoku.num[i][j+1];ns[k].cur_sudoku.num[i][j+1]=0;ns[k].dx=1;k++;}if(i+1=2){//将空格向下移动CopySudoku(ns[k].cur_sudoku,ne.cur_sudoku);ns[k].cur_sudoku.num[i][j]=ns[k].cur_sudoku.num[i+1][j];ns[k].cur_sudoku.num[i+1][j]=0;ns[k].dx=1;k++;}if(j-1=0){//将空格向左移动CopySudoku(ns[k].cur_sudoku,ne.cur_sudoku);ns[k].cur_sudoku.num[i][j]=ns[k].cur_sudoku.num[i][j-1];ns[k].cur_sudoku.num[i][j-1]=0;ns[k].dx=1;k++;}return1;}}}return0;2、用启发式搜索函数寻找求解路径，运用了A*算法的思想，能够更快的求解出最优解。关键代码：boolHeuristic_Search(Sudokustart,Sudokuend){inta=0,b=0,c=0;intcount=0;NOExtend_Sudokuns;//未扩展结点表Extended_Sudokues;//已扩展结点表Pathpath;//求解路径NOExtendfather;//定义父节点ns.no_node[a].cur_sudoku=start;//初始化未拓展结点表ns.no_node[a].dx=0;ns.no_node[a].hx=GetHx(ns.no_node[a].cur_sudoku,end);ns.no_node[a].fx=ns.no_node[a].dx+ns.no_node[a].hx;a++;while(a!=0)//当未拓展结点表不为空时{father=ns.no_node[0];//父节点为为拓展表的第一个结点path.pa[c++]=father;//记录求解路径DeleteFirst(ns,a);//从未拓展表中删除第一个结点a--;if(EqualSudoku(father.cur_sudoku,end)){//如果找到了目标九宫格则输出求解路径ShowPath(path,c);return1;}NOExtendchild[4];//因为九宫格只能拓展上下左右四个方向所以拓展出的结点最多有四个CreateChild(child,father);//生成父节点的扩展结点if(!CreateChild(child,father))continue;//如果没有扩展结点就跳出进行下一次循环for(inti=0;i4;i++){if(child[i].dx==1){//对于父节点可以生成的每个子结点if(!ExistNOExtend(ns,child[i].cur_sudoku)&&!ExistExtended(es,child[i].cur_sudoku)){//如果未拓展表和已拓展表中都没有此状态，则添加此状态到未拓展表中Value(child[i],father,end);//获取此结点的估价值ns.no_node[a]=child[i];ns.no_node_father[a]=father;a++;continue;}if(ExistNOExtend(ns,child[i].cur_sudoku)){//如果未拓展表中有此状态，此求得当前状态的估价值并且与表中存在的此状态的估价值比较//若估价值大就放弃此结点，更小，就加入此结点Value(child[i],father,end);if(child[i].fxfather.fx){ns.no_node[a]=child[i];ns.no_node_father[a]=father;a++;continue;}}if(ExistExtended(es,child[i].cur_sudoku)){//如果已拓展表中有此状态，此求得当前状态的估价值并且与表中存在的此状态的估价值比较//若估价值大就放弃此结点，更小，就加入此结点Value(child[i],father,end);if(child[i].fxes.node[0].value){//当子状态的价值小与已经扫描过的状态时ns.no_node[a]=child[i];ns.no_node_father[a]=father;a++;//a为未拓展表中的元素个数continue;}}}}es.node[b].cur_sudoku=father.cur_sudoku;//将已经生成完拓展结点的父节点放入已拓展表中es.node[b].value=father.fx;b++;//b为已拓展表中的元素个数SortNoExtend(ns,a);//根据估价函数值，从小到大重新排列未拓展表，每次只搜索估价值最小的结点的路径if(count++MAXPATH){break;}}return0;}六、实验心得1、学习了新的算法——A*算法，结合了伪代码和网上的一些教程，实现了八数码问题的求解，这是对我编程能力的一种提升，也让我懂了更多做题的方法。2、在这次实验中，存在着许许多多细节上的小问题，是因为自己的编程基础不牢靠而产生的，通过这次实验又让我懂了许多细节上的问题，以后就不会发生类似的问题了。