人工智能实验报告-八数码演示程序文件

./人工智能实验报告八数码演示程序姓名：处添加内容学号：处添加内容计算机科学与技术专业所学专业：计算机科学与技术专业八数码演示程序报告题目：八数码演示程序20XX4月9日提交日期：20XX4月9日八数码演示程序问题描述1.1八数码问题的解释八数码问题是人工智能经典难题之一。问题是在3×3方格盘上,放有八个数码,剩下一个为空,每一空格其上下左右的数码可移至空格。问题给定初始位置和目标位置,要求通过一系列的数码移动,将初始位置转化为目标位置。本文介绍用A星算法,采用估计值h〔n〔曼哈顿距离和g<m><当前深度>的和作为估计函数。1.2八数码问题的搜索形式描述初始状态：初始状态向量,规定向量中各分量对应的位置,各位置上的初始数字<0,1,3,4,5,6,7,8,2>后继函数：移动规则,按照某条规则移动数字得到的新向量<0,1,3,4,5,6,7,8,9>转移到<4,1,3,0,5,6,7,8,2>目标测试：新向量是否是目标状态,也即为<0,1,2,3,4,5,6,7,8>路径耗散函数：在搜索时,每深入一层则当前步数代价加1,代价总和由当前步数和可能还需要移动的步数之和。1.3解决方案介绍首先,A*算法需要个估价<评价>函数:f<x>=g<x>+h<x>g<x>通常表示移动至当前状态需要的步数,h<x>则是启发函数。在算法进行的时候,我们将对每一个可能移动到的状态做评价,计算其f<x>,然后将其放入一个OPEN数组中,最后我们选取OPEN中f<x>值最小的状态作为下一步,再重复上述过程,因为f<x>值最小的状态意味着它最有可能<不是一定>最接近最终状态。算法介绍2.1搜索算法一般介绍A*算法是一种启发式搜索算法,是常用的最短路搜寻算法,在游戏领域中有广泛的应用。所谓启发式算法,它与常规的搜索方法最大的不同是在执行过程中始终有一个提示性的信息在引导着算法的进行,使得我们不断靠近目标而不是盲目的遍历,这个提示信息就是由启发函数产生的,启发函数的好坏将直接影响算法的效率,从几篇文献看来,A*算法和广度优先、深度优先算法相比是有很明显的效率优势的。2.2算法伪代码InitializeOPEN、CLOSE、初始状态source,最终状态dest;Push<source,OPEN>;While<!OPEN.isEmpty<>>{FindFirstElementOfOpen<>;cuNode=Pop<OPEN>;If isTheSame<cuNode,dest>Thenexit;Push<cuNode,close>Extend<cuNode>;}ExtendNewNode<NewNode>{If CLOSE.NOTcontains<NewNode> Then If OPEN.NOTcontains<NewNode>Push<NewNode,OPEN>;Else IfOPEN.get<NewNode>.f>NewNode.f ThenPush<NewNode,OPEN>;}算法实现3.1实验环境与问题规模本文采用java语言进行程序设计,在图形界面上可以显示八数码格局,并可以随机生成新的起始状态和目标状态。问题规模为8,解决八数码问题,但可以比较容易就能修改为对15数码问题的求解。3.2数据结构1.类Node,表示一个结点,也即搜索过程中的某一个状态,其内部数据成员有ID〔可以唯一地表示一个状态结点,parentID〔该状态结点的母结点,保存这个值是为了在找到目标结点时可以回溯其路径,a[][]〔一个二维数组,用于存放当前八数码的状态,g〔表示从起始状态结点开始到当前状态结点所走过的步数,h〔表示从当前状态结点到目标状态结点有可能还要走多少步数,f〔就是g值与h值的和。2.OPEN表,实现的时候使用的是HashMap,以保证所存的每一个状态的唯一性；Open表的用途是存放产生的可能的新状态,这些新状态有待于扩展。3.CLOSE表,实现的时候使用的是HashMap,以保证所存的每一个状态的唯一性；存放ID=>Node结点键值对,用途是记录已经访问过的状态。3.3实验结果起始状态210785436终结状态012345678目标可达,总执行步数为21步,搜索算法所耗时间为31毫秒3.4系统中间及最终输出结果〔要求有屏幕显示1.无解时的情形：2.有解时的情形：起始状态：自动演示时的移动过程截图：最后达到目标状态：参考文献人工智能游戏编程真言 <美>SteveRabin主编 Java项目开发实践 陆正武,张志立编著 JavaSE6.0编程指南 吴亚峰,纪超编著 数据结构经典算法实现与习题解答 汪杰等编著 SwingHacks:100个业界最尖端的技巧和工具 JoshuaMarinacci,ChrisAdamson著 Java综合实例经典 吴其庆编著 附录—源代码及其注释〔算法部分,不包括界面设计的代码：packageMyAI;importjava.util.HashMap;importjava.util.Iterator;importjava.util.Map;importjava.util.Vector;importjava.util.Map.Entry;classNode{ LongID; LongparentID; inta[][]; intg; inth; intf; Node<longID,longparentID,inta[][],intg,inth>{ this.ID=ID; this.parentID=parentID; this.a=a; this.g=g; this.h=h; this.f=g+h; }}publicclassEightNumber{ privateMap<Long,Node>open=newHashMap<Long,Node><>; privateMap<Long,Node>close=newHashMap<Long,Node><>; privateint[][]source=null; privateint[][]dest=null; publicEightNumber<int[][]source,int[][]dest>{ this.source=source; this.dest=dest; } publicVector<Node>process<>{ Nodes=newNode<computeID<source>,0,source,0,computeH<source, dest>>;//令起始结点的母结点ID为0 Noded=newNode<computeID<dest>,0,dest,0,0>;//目标状态的母结点未知,g值未知 System.out.println<"起始状态">; printNode<s>; System.out.println<"终结状态">; printNode<d>; if<!resolvable<this.source,this.dest>>{ returnnull; } push<s,open>; NodecuNode=s; //intcount=0; while<!open.isEmpty<>>{ //count++; cuNode=pop<open>; if<isTheSame<cuNode,d>>{ System.out.println<"找到目标">; break; } push<cuNode,close>; extendNode<cuNode,d>; } returnprintResult<cuNode>; } privateVector<Node>printResult<NodecuNode>{ intcount=0; Vector<Node>result=newVector<Node><>; while<cuNode.parentID!=0>{ count++; result.add<cuNode>; printNode<cuNode>; cuNode=close.get<cuNode.parentID>; } printNode<cuNode>; System.out.println<"总共经过"+count+"步数">; returnresult; } privatevoidprintNode<NodecuNode>{ for<inti=0;i<3;i++>{ for<intj=0;j<3;j++>{ System.out.print<cuNode.a[i][j]+"">; } System.out.println<>; } System.out.println<"">; } privatevoidextendNode<NodecuNode,Nodedest>{ intheng=0,zong=0;//i,j分别为0的横纵坐标 for<inti=0;i<3;i++> for<intj=0;j<3;j++> if<cuNode.a[i][j]==0>{ heng=i; zong=j; break; } if<zong-1>=0>{//如果0可以往左边移动 int[][]state=newint[3][3]; for<inti=0;i<3;i++> for<intj=0;j<3;j++> state[i][j]=cuNode.a[i][j]; state[heng][zong]=cuNode.a[heng][zong-1]; state[heng][zong-1]=0; extend<state,cuNode,dest>; } if<zong+1<=2>{//如果0可以往右边移动 int[][]state=newint[3][3]; for<inti=0;i<3;i++> for<intj=0;j<3;j++> state[i][j]=cuNode.a[i][j]; state[heng][zong]=cuNode.a[heng][zong+1]; state[heng][zong+1]=0; extend<state,cuNode,dest>; } if<heng-1>=0>{//如果0可以往上边移动 int[][]state=newint[3][3]; for<inti=0;i<3;i++> for<intj=0;j<3;j++> state[i][j]=cuNode.a[i][j]; state[heng][zong]=cuNode.a[heng-1][zong]; state[heng-1][zong]=0; extend<state,cuNode,dest>; } if<heng+1<=2>{//如果0可以往下边移动 int[][]state=newint[3][3]; for<inti=0;i<3;i++> for<intj=0;j<3;j++> state[i][j]=cuNode.a[i][j]; state[heng][zong]=cuNode.a[heng+1][zong]; state[heng+1][zong]=0; extend<state,cuNode,dest>; } } privatevoidextend<int[][]state,NodecuNode,Nodedest>{ Nodenode=newNode<computeID<state>,cuNode.ID,state,cuNode.g+1, computeH<state,dest.a>>; if<!close.containsKey<node.ID>>{ if<!open.containsKey<node.ID>> push<node,open>; else{ if<open.get<node.ID>.f>node.f> push<node,open>; } } } privatebooleanisTheSame<NodecuNode,Noded>{ if<cuNode.ID.equals<d.ID>> returntrue; returnfalse; } privatevoidpush<Nodea,Map<Long,Node>open2>{ open2.put<a.ID,a>; } privateNodepop<Map<Long,Node>open2>{ Iterator<Entry<Long,Node>>it=open.entrySet<>.iterator<>; Map.Entry<Long,Node>e=it.next<>; intfmin=e.getValue<>.f; Nodenode=e.getValue<>; while<it.hasNext<>>{ e=it.next<>; if<e.getValue<>.f<fmin>{ fmin=e.getValue<>.f; node=e.getValue<>; } } returnopen2.remove<node.ID>; } publicstaticbooleanresolvable<int[][]source,int[][]dest>{ intcount1=0; intcount2=0; int[]starts=transform1<source>; int[]ends=transform1<dest>; for<inti=0;i<9;i++>{ for<intj=0;j<i;j++> if<starts[i]<starts[j]&&starts[i]!=0> count1++;//统计初始状态的逆序数 } for<inti=0;i<9;i++>{ for<intj=0;j<i;j++> if<ends[i]<ends[j]&&ends[i]!=0> count2++;//统计目标状态的逆序数 } if<count1%2==count2%2>{ System.out.println<"有解">; returntrue; }else{ System.out.println<"无解">; returnfalse; } } privatelongcomputeID<inta[][]>{ longsum=0; for<inti=0;i<3;i++> for<intj=0;j<3;j++>{ sum=sum*10+a[i][j]; } returnsum; } privateintcomputeH<intnode[][],intdest[][]>{ intcount=0; for<inti=0;i<=2;i++> for<intj=0;j<=2;j++> for<intg=0;g<=2;g++> for<intk=0;k<=2;k++>{ if<node[i][j]==dest[g][k]&&node[i][j]!=0>//a[][]为初始的,b[][]为目标 { count+=Math.abs<i-g>+Math.abs<j-k>;