资源描述：
《a星算法求八数码问题实验报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、人工智能矣發板普类務名称：入救碍问题姓名：XX学号：2012210xxXX计算机学晚2014年1力14g一.实验目的掌握A*的思想，启发式搜索，来求解在代价最小的情况下将九宫格从一个状态转为另状态的路径。二.实验内容给定九宫格的初始状态，要求在有限步的操作内，使其转化为目标状态，且所得到的解是代价最小解(即移动的步数最少)并打印出求解路径。例如283164705283164705三、A*算法思想：1、思想：八*算法是一种静态路网中求解最短路最有效的直接搜索方法。估价值与实际值越接近，估价函数取得就越好2、原理：估价函
2、数公式表示为：f(n)=g(n)+h(n),其中f(n)是从初始点经由节点n到0标点的估价函数，g(n)是在状态空间屮从初始节点到n节点的实际代价，h(n)是从n到FI标节点最佳路径的估计代价。保证找到最短路径(最优解的)条件，关键在于估价函数h(n)的选取：估价值h(n)〈=n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。并且如果h(n)=d(n),即距离估计h(n)等于最短距离，那么搜索将严格沿着最短路径进行此时的搜索效率是最高的。如果估价值〉实际值，搜索的点数少，搜索范围
3、小，效率高，但不能保证得到最优解。U!算法流程:否，生成n的所有子状态返冋五、关键技术:1、使用了CreateChild()函数，求得了任意未拓展九宫格的扩展结点，便于拓展子空间，搜索所有情况。关键代码：boolCreateChiId(NOExtendns[]，NOExtendne){inti,j,k=0;for(i=0;i<3;i++){for(j=0;j<3;j++){if(ne.cur_sudoku.nuni[i][j]==0){//寻找九宫格空缺所在的坐标if(i-l〉=0){//将空格向上移动CopySud
4、oku(ns[k].cur_sudoku,ne.cur_sudoku);//先把未改变的九宫格复制给九宫格数组的某一元素ns[k].cur_sudoku.num[i][j]=ne.cur_sudoku.num[i-l][j];//然后仅改变此二维九宫格的两项值即可ns[k].cursudoku.num[i-1][j]=0;ns[k].dx=l;k++;}if(j+l<=2){//将空格向右移动CopySudoku(ns[k].cursudoku,ne.cursudoku);ns[k].cur_sudoku.num[i
5、][j]=ns[k].cur_sudoku.num[i][j+1];ns[k].cursudoku.num[i][j+l]=0;ns[k].dx二1;k++;}if(i+l<=2){//将空格向下移动CopySudoku(ns[k].cursudoku,ne.cursudoku);ns[k].cur_sudoku.nuni[i][j]=ns[k].cur^sudoku.num[i+l][j];ns[k].cur^sudoku.num[i+l][j]=0;ns[k].dx=l;k++;}if(j-l>=0){//将空格
6、向左移动CopySudoku(ns[kLcur_sudoku,ne.cur_sudoku);ns[k].cursudoku.num[i][j]=ns[k].cursudoku.num[i][j-l];ns[k].cur_sudoku.num[i][j-1]=0;ns[k].dx=l;k++;return0;2、用启发式搜索函数寻找求解路径，运用了A*算法的思想，能够更快的求解出最优解。关键代码：boolHeuristicSearch(Sudokustart,Sudokuend){inta=0,b=0,c=0;intc
7、ount=0;NOExtendSudokuns;//未扩展结点表ExtendedSudokues;//已扩艇结点表Pathpath;//求解路径NOExtendfather;//定义父点ns.nonode[a].cursudoku=start;//初始化未拓展结点表ns.nonode[a].dx=0;ns.no_node[a].hx=GetHx(ns.no_node[a].cur_sudoku,end);ns.nonode[a].fx=ns.nonode[a],dx+ns.nonode[a].hx;a++;fathe
8、r=ns.no_node[0];path.pa[c++]=father;DeletcEirst(ns,a);while(a!=0)//当未拓展结点表不为空吋//父节点为为拓展表的第一个结点//记录求解路径//从未拓展表中删除第一个结点if(EqualSudoku(father,cursudoku,end)){//如果找到/目标九宫格则输出求解路
