A星算法求八数码问题实验报告(共7页)

1、精选优质文档-倾情为你奉上人工智能实验报告实验名称：八数码问题姓名：xx学号：xx xx计算机学院 2014年1月14日1 实验目的 掌握A*的思想，启发式搜索，来求解在代价最小的情况下将九宫格从一个状态转为另状态的路径。2 实验内容给定九宫格的初始状态，要求在有限步的操作内，使其转化为目标状态，且所得到的解是代价最小解(即移动的步数最少)并打印出求解路径。例如28 316470528 31647053、 A*算法思想：1、 思想：A*是一种静态路网中求解最短路最有效的直接搜索方法。估价值与实际值越接近，估价函数取得就越好2、 原理： 估价函数公式表示为： f(n)=g(n)+h(n), 其中

2、 f(n) 是从初始点经由节点n到目标点的估价函数，g(n) 是在中从初始节点到n节点的实际代价，h(n) 是从n到目标节点最佳路径的估计代价。保证找到（最优解的）条件，关键在于估价函数h(n)的选取：估价值h(n)<= n到目标的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。并且如果h(n)=d(n)，即距离估计h(n)等于最短距离，那么搜索将严格沿着最短路径进行此时的搜索效率是最高的。如果估价值>实际值,的点数少，搜索范围小，效率高，但不能保证得到最优解。4、 算法流程：Heuristic_Search(启发式搜索)While（未拓展表不为空？）是从

3、未拓展表中删除第一个状态nN为目标状态？ 是，输出路径否，生成n的所有子状态Case:此子状态在拓展表Case:此子状态在未拓展表中Case:此子状态不在拓展表和未拓展表中记录比已有的路径更短的路径记录比已有的路径更短的路径计算该子状态的估价函数值；返回5、 关键技术：1、 使用了CreateChild（）函数，求得了任意未拓展九宫格的扩展结点，便于拓展子空间，搜索所有情况。关键代码：bool CreateChild(NOExtend ns,NOExtend ne)int i,j,k=0;for(i=0;i<3;i+)for(j=0;j<3;j+)if(ne.cur_sudoku.

4、numij=0) /寻找九宫格空缺所在的坐标if(i-1>=0) /将空格向上移动CopySudoku(nsk.cur_sudoku,ne.cur_sudoku);/先把未改变的九宫格复制给九宫格数组的某一元素nsk.cur_sudoku.numij=ne.cur_sudoku.numi-1j;/然后仅改变此二维九宫格的两项值即可nsk.cur_sudoku.numi-1j=0;nsk.dx=1;k+;if(j+1<=2) /将空格向右移动CopySudoku(nsk.cur_sudoku,ne.cur_sudoku);nsk.cur_sudoku.numij=nsk.cur_su

5、doku.numij+1;nsk.cur_sudoku.numij+1=0;nsk.dx=1;k+;if(i+1<=2) /将空格向下移动CopySudoku(nsk.cur_sudoku,ne.cur_sudoku);nsk.cur_sudoku.numij=nsk.cur_sudoku.numi+1j;nsk.cur_sudoku.numi+1j=0;nsk.dx=1;k+;if(j-1>=0) /将空格向左移动CopySudoku(nsk.cur_sudoku,ne.cur_sudoku);nsk.cur_sudoku.numij=nsk.cur_sudoku.numij-1

6、;nsk.cur_sudoku.numij-1=0;nsk.dx=1;k+;return 1;return 0;2、用启发式搜索函数寻找求解路径，运用了A*算法的思想，能够更快的求解出最优解。关键代码：bool Heuristic_Search(Sudoku start,Sudoku end)int a=0,b=0,c=0;int count=0;NOExtend_Sudoku ns; /未扩展结点表Extended_Sudoku es; /已扩展结点表Path path; /求解路径NOExtend father; /定义父节点ns.no_nodea.cur_sudoku=start; /初

7、始化未拓展结点表ns.no_nodea.dx=0; ns.no_nodea.hx=GetHx(ns.no_nodea.cur_sudoku,end); ns.no_nodea.fx=ns.no_nodea.dx+ns.no_nodea.hx; a+;while(a!=0) /当未拓展结点表不为空时 father=ns.no_node0; /父节点为为拓展表的第一个结点 path.pac+=father; /记录求解路径 DeleteFirst(ns,a); /从未拓展表中删除第一个结点 a-; if(EqualSudoku(father.cur_sudoku,end) /如果找到了目标九宫格则

8、输出求解路径 ShowPath(path,c); return 1; NOExtend child4; /因为九宫格只能拓展上下左右四个方向所以拓展出的结点最多有四个 CreateChild(child,father); /生成父节点的扩展结点 if(!CreateChild(child,father) continue; /如果没有扩展结点就跳出进行下一次循环 for(int i=0;i<4;i+) if(childi.dx=1) /对于父节点可以生成的每个子结点 if(!ExistNOExtend(ns,childi.cur_sudoku)&&!ExistExtend

9、ed(es,childi.cur_sudoku)/如果未拓展表和已拓展表中都没有此状态，则添加此状态到未拓展表中 Value(childi,father,end);/获取此结点的估价值 ns.no_nodea=childi; ns.no_node_fathera=father; a+; continue; if(ExistNOExtend(ns,childi.cur_sudoku)/如果未拓展表中有此状态，此求得当前状态的估价值并且与表中存在的此状态的估价值比较/若估价值大就放弃此结点，更小，就加入此结点 Value(childi,father,end); if(childi.fx<fa

10、ther.fx) ns.no_nodea=childi; ns.no_node_fathera=father; a+; continue; if(ExistExtended(es,childi.cur_sudoku)/如果已拓展表中有此状态，此求得当前状态的估价值并且与表中存在的此状态的估价值比较/若估价值大就放弃此结点，更小，就加入此结点 Value(childi,father,end); if(childi.fx<es.node0.value)/当子状态的价值小与已经扫描过的状态时 ns.no_nodea=childi; ns.no_node_fathera=father; a+;/a为未拓展表中的元素个数 continue; es.nodeb.cur_sudoku=father.cur_sudoku; /将已经生成完拓展结点的父节点放入已拓展表中 es.nodeb.value=father.fx; b+; /b为已拓展表中的元素个数 SortNoExtend(ns,a); /根据估价函数值，从小到大重新排列未拓展表，每次只搜索估价值最小的结点的路径 if(count+>MAXPATH) break;r