人工智能实验报告-八数码问题

实验一启发式搜索算法姓名：尹鹏飞学号：S201407031日期：2014/10/22一、实验目的：熟练掌握启发式搜索A算法及其可采纳性。二、实验内容：使用启发式搜索算法求解8数码问题。编制程序实现求解8数码问题A算法，采用估价函数wnfndnpn，其中：dn是搜索树中结点n的深度；wn为结点n的数据库中错放的棋子个数；pn为结点n的数据库中每个棋子与其目标位置之间的距离总和。本实验采用)(nd+pn作为启发式函数.三、实验原理：1.问题描述：八数码问题也称为九宫问题。在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格（以数字0来表示），与空格相邻的棋子可以移到空格中。要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。所谓问题的一个状态就是棋子在棋盘上的一种摆法。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。2.原理描述：2.1有序搜索算法：（1）原理：在搜索过程中，OPEN表中节点按照其估价函数值以递增顺序排列，选择OPEN表中具有最小估价函数值的节点作为下一个待扩展的节点，这种搜索方法称为有序搜索。在本例中，估价函数中的)(ng取错放的棋子个数)(nd，)(nh为节点n的状态与目标状态之间错放的个数，即函数pn。（2）算法描述：①把起始节点S放到OPEN表中，并计算节点S的)(Sf；②如果OPEN是空表，则失败退出，无解；③从OPEN表中选择一个f值最小的节点i。如果有几个节点值相同，当其中有一个为目标节点时，则选择此目标节点；否则就选择其中任一个节点作为节点i；④把节点i从OPEN表中移出，并把它放入CLOSED的已扩展节点表中；⑤如果i是个目标节点，则成功退出，求得一个解；⑥扩展节点i，生成其全部后继节点。对于i的每一个后继节点j：计算)(jf；如果j既不在OPEN表中，又不在CLOCED表中，则用估价函数f把它添入OPEN表中。从j加一指向其父节点i的指针，以便一旦找到目标节点时记住一个解答路径；如果j已在OPEN表或CLOSED表中，则比较刚刚对j计算过的f和前面计算过的该节点在表中的f值。如果新的f较小，则(I)以此新值取代旧值。(II)从j指向i，而不是指向他的父节点。(III)如果节点j在CLOSED表中，则把它移回OPEN表中。⑦转向②，即GOTO②。（3）算法流程图：2.2启发式搜索技术（1）原理启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。（2）估价函数计算一个节点的估价函数，可以分成两个部分：1、已经付出的代价（起始节点到当前节点）；2、将要付出的代价（当前节点到目标节点）。节点n的估价函数)(nf定义为从初始节点、经过n、到达目标节点的路径的最小代价的估计值，即)(*nf=)(*ng+)(*nh。)(*ng是从初始节点到达当前节点n的实际代价；)(*nh是从节点n到目标节点的最佳路径的估计代价，体现出搜索过程中采用的启发式信息（背景知识），称之为启发函数。)(*ng所占的比重越大，越趋向于宽度优先或等代价搜索；反之，)(*nh的比重越大，表示启发性能就越强。本实验中我们使用函数)(np，其值是节点n与目标状态节点相比较，每个错位棋牌在假设不受阻拦的情况下，移动到目标状态相应位置所需走步（移动次数）的总和。显然)(np比)(n更接近于)(*nh，因为)(np不仅考虑了错位因素，还考虑了错位的距离。（3）算法描述：参考有序搜索算法描述，基本相同。流程图亦参考有序算法流程图。四、实验程序及其说明：程序开发语言采用C#和面向对象的设计思想,设计的类内容如下:类视图SplashForm用来显示启动界面;MainForm用来显示数据设置界面;ShowForm用来显示结果界面;Number用来记录每个节点当前的状态和权值;属性:privateint[]num;//保存当前输入的八数码状态privateintw,p;//分别记录当前的八数码搜索深度和不在位棋子数privateNumbernext;//指向下一个节点privateNumberparent;//指向父节点privateintindex;//定义当前0所在的位置方法://复写父类比较方法publicoverrideboolEquals(Objectnum)//两个对象的比较方法publicboolCompareLow(Numbernum)NumberUtil类,工具类,对八数码的各种状态进行控制管理privateQueuenumQueue;//八数码队列,保存open表privateint[]soure;//初始状态privateint[]target;//目标状态privateNumberresult;//结果集方法:publicboolControl(Numbernum)//控制策略publicboolCalculate()//计算结果Queue用来作为程序的open表,扩展节点privateNumberhead;//定义队列的头privateArrayListlistClose;//close表保存所有出现的状态表//添加新的元素,并按照A*算法的计算值递增排序publicvoidaddNumber(Numbernum)//出队一个元素publicNumberequeue()五、实验小结通过本次试验，我对启发式搜索有了更加深入的了解。在实验中，通过对两种启发式搜索所扩在的节点数来看，)(np看来比)(n更加有效，能在复杂情况下求得更加优质的解，避免不必要的节点的扩展。但是对于估价函数)(*nh来说，它的定义趋向多元化，)(np只是它的一个比较好的特例，对一复杂的搜索问题，如国际象棋问题，他就显得较简单。所以，要更好地定义一个估价函数还有待深入讨论。在寻找最佳扩展路径的过程中我发现，最佳扩展路基上的节点均在CLOSED表中，利用标志flag，以及它们之间的父子关系，我很容易的就找到了扩展路径，避免了再用一个路径指针path来找到路径，这样节省了存储空间，更利于搜索。通过实验结果来看，这两个函数都是可采纳的，尽管)(n存在不必要的扩展。六、实验代码及输出结果1.源代码：classQueue{privateNumberhead;//定义队列的头privateArrayListlistClose;//close表保存所有出现的状态表publicQueue(){listClose=newArrayList();head=newNumber();head.Next=null;}internalNumberHead{get{returnhead;}set{head=value;}}privateintcount=0;//队列中的元素publicintCount{get{returncount;}set{count=value;}}publicvoidshow(){Numbern=head.Next;while(n!=null){Console.WriteLine(n.ToString());n=n.Next;}}//添加新的元素,并按照A*算法的计算值递增排序publicvoidaddNumber(Numbernum){//如果该状态已出现则不再加入其中if(listClose.IndexOf(num)=0){Console.WriteLine(listClose.IndexOf(num)+-------);return;}listClose.Add(num);Numbern=head.Next;//获取头元素Numberfront=head;//前节点if(n==null)head.Next=num;else{for(;n!=null;n=n.Next)//遍历所有元素{//采用头插法将数据插入后面if(num.CompareLow(n)){//如果num比当前对象小,则直接插入前面num.Next=n;front.Next=num;//插入成功count++;//增加当前的节点数目return;}front=n;}}front.Next=num;//直接插入尾部count++;//增加当前的节点数目}//出队列publicNumberequeue(){if(count==0)returnnull;Numbern=head.Next;head.Next=head.Next.Next;count--;returnn;}}}usingSystem;usingSystem.Collections.Generic;usingSystem.Linq;usingSystem.Text;namespaceAICode{classNumberUtil{privateQueuenumQueue;//八数码队列,保存open表privateint[]soure;//初始状态publicint[]Soure{get{returnsoure;}set{soure=value;}}privateint[]target;//目标状态publicint[]Target{get{returntarget;}set{target=value;}}privateNumberresult;//结果集internalNumberResult{get{returnresult;}set{result=value;}}privateintindex;//当前的0所在数组中的下标publicintIndex{get{returnindex;}set{index=value;}}publicNumberUtil(){numQueue=newQueue();//}//获取结果栈对象publicStackNumbergetResult(){StackNumbers=newStackNumber();if(result!=null){for(Numbern=result;n!=null;n=n.Parent){s.Push(n);}}returns;}//对A,B两个数组进行比较publicboolcompareArray(int[]a,int[]b){for(inti=0;i=8;i++){if(a[i]!=b[i])returnfalse;}returntrue;}//A*算法策略publicvoidA(Numbern,int[]t){intcountP=0;for(inti=0;i=8;i++){inttemp=n.Num[i];if(n.Num[i]!=t[i]){for(intj=0;j=8;j++){if(t[j]==temp){intr=Math.Abs(j%3-i%3);intc=Math.Abs(j/3-i/3);countP+=r+c;}}}}n.P=countP;}publicboolCalculate(){//计算结果//首先将首元素添加到队列中Numbern=newNumber();n.Index=index;n.Num=(int[])soure.Clone();A(n,target);//计算权值n.D=1;numQueue.addNumber(n);intMAXCount=0;while(numQueue.Count0){//从队首出对一个元素Numbernum=numQueue.equeue();if(!Control(num)){returntrue;};//numQueue.show();//Console.WriteLine(============);MAXCount++;if(MAXCount10000){returnfalse;}}returnfalse