a星算法实现8数码问题c语言,A星算法求八数码问题实验报告.doc

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

人工智能实验报告实验名称八数码问题姓名xx学号2012210 xx xx计算机学院 2014年1月14日1 实验目的 掌握A*的思想，启发式搜索，来求解在代价最小的情况下将九宫格从一个状态转为另状态的路径。2 实验内容给定九宫格的初始状态，要求在有限步的操作内，使其转化为目标状态，且所得到的解是代价最小解即移动的步数最少并打印出求解路径。例如28 316470528 31647053、 A*算法思想1、 思想A*算法是一种静态路网中求解最短路最有效的直接搜索方法。估价值与实际值越接近，估价函数取得就越好2、 原理 估价函数公式表示为 fngnhn, 其中 fn 是从初始点经由节点n到目标点的估价函数，gn 是在状态空间中从初始节点到n节点的实际代价，hn 是从n到目标节点最佳路径的估计代价。保证找到最短路径(最优解的)条件，关键在于估价函数hn的选取估价值hn n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。并且如果hndn，即距离估计hn等于最短距离，那么搜索将严格沿着最短路径进行此时的搜索效率是最高的。如果估价值实际值,搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。4、 算法流程Heuristic_Search启发式搜索While(未拓展表不为空)是从未拓展表中删除第一个状态nN为目标状态 是，输出路径否，生成n的所有子状态Case此子状态在拓展表Case此子状态在未拓展表中Case此子状态不在拓展表和未拓展表中记录比已有的路径更短的路径记录比已有的路径更短的路径计算该子状态的估价函数值；返回5、 关键技术1、 使用了CreateChild()函数，求得了任意未拓展九宫格的扩展结点，便于拓展子空间，搜索所有情况。关键代码bool CreateChildNOExtend ns,NOExtend neint i,j,k0;fori0;i3;iforj0;j3;jifne.cur_sudoku.numij0 寻找九宫格空缺所在的坐标ifi-10 将空格向上移动CopySudokunsk.cur_sudoku,ne.cur_sudoku;先把未改变的九宫格复制给九宫格数组的某一元素nsk.cur_sudoku.numijne.cur_sudoku.numi-1j;然后仅改变此二维九宫格的两项值即可nsk.cur_sudoku.numi-1j0;nsk.dx1;k;ifj12 将空格向右移动CopySudokunsk.cur_sudoku,ne.cur_sudoku;nsk.cur_sudoku.numijnsk.cur_sudoku.numij1;nsk.cur_sudoku.numij10;nsk.dx1;k;ifi12 将空格向下移动CopySudokunsk.cur_sudoku,ne.cur_sudoku;nsk.cur_sudoku.numijnsk.cur_sudoku.numi1j;nsk.cur_sudoku.numi1j0;nsk.dx1;k;ifj-10 将空格向左移动CopySudokunsk.cur_sudoku,ne.cur_sudoku;nsk.cur_sudoku.numijnsk.cur_sudoku.numij-1;nsk.cur_sudoku.numij-10;nsk.dx1;k;return 1;return 0;2、用启发式搜索函数寻找求解路径，运用了A*算法的思想，能够更快的求解出最优解。关键代码bool Heuristic_SearchSudoku start,Sudoku endint a0,b0,c0;int count0;NOExtend_Sudoku ns; 未扩展结点表Extended_Sudoku es; 已扩展结点表Path path; 求解路径NOExtend father; 定义父节点ns.no_nodea.cur_sudokustart; 初始化未拓展结点表ns.no_nodea.dx0; ns.no_nodea.hxGetHxns.no_nodea.cur_sudoku,end; ns.no_nodea.fxns.no_nodea.dxns.no_nodea.hx; a;whilea0 当未拓展结点表不为空时 fatherns.no_node0; 父节点为为拓展表的第一个结点 path.pacfather; 记录求解路径 DeleteFirstns,a; 从未拓展表中删除第一个结点 a; ifEqualSudokufather.cur_sudoku,end 如果找到了目标九宫格则输出求解路径 ShowPathpath,c; return 1; NOExtend child4; 因为九宫格只能拓展上下左右四个方向所以拓展出的结点最多有四个 CreateChildchild,father; 生成父节点的扩展结点 ifCreateChildchild,father continue; 如果没有扩展结点就跳出进行下一次循环 forint i0;i4;i ifchildi.dx1 对于父节点可以生成的每个子结点 ifExistNOExtendns,childi.cur_sudokuExistExtendedes,childi.cur_sudoku如果未拓展表和已拓展表中都没有此状态，则添加此状态到未拓展表中 Valuechildi,father,end;获取此结点的估价值 ns.no_nodeachildi; ns.no_node_fatherafather; a; continue; ifExistNOExtendns,childi.cur_sudoku如果未拓展表中有此状态，此求得当前状态的估价值并且与表中存在的此状态的估价值比较若估价值大就放弃此结点，更小，就加入此结点 Valuechildi,father,end; ifchildi.fxfather.fx ns.no_nodeachildi; ns.no_node_fatherafather; a; continue; ifExistExtendedes,childi.cur_sudoku如果已拓展表中有此状态，此求得当前状态的估价值并且与表中存在的此状态的估价值比较若估价值大就放弃此结点，更小，就加入此结点 Valuechildi,father,end; ifchildi.fxes.node0.value当子状态的价值小与已经扫描过的状态时 ns.no_nodeachildi; ns.no_node_fatherafather; a;a为未拓展表中的元素个数 continue; es.nodeb.cur_sudokufather.cur_sudoku; 将已经生成完拓展结点的父节点放入已拓展表中 es.nodeb.valuefather.fx; b; b为已拓展表中的元素个数 SortNoExtendns,a; 根据估价函数值，从小到大重新排列未拓展表，每次只搜索估价值最小的结点的路径 ifcountMAXPATH break;return 0;6、 实验心得1、 学习了新的算法A*算法，结合了伪代码和网上的一些教程，实现了八数码问题的求解，这是对我编程能力的一种提升，也让我懂了更多做题的方法。2、 在这次实验中，存在着许许多多细节上的小问题，是因为自己的编程基础不牢靠而产生的，通过这次实验又让我懂了许多细节上的问题，以后就不会发生类似的问题了。