用A算法解决十五数码问题.docx

该【用A算法解决十五数码问题 】是由【智慧书屋】上传分享，文档一共【8】页，该文档可以免费在线阅读，需要了解更多关于【用A算法解决十五数码问题 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。用A算法解决十五数码问题用A算法解决十五数码问题1用A算法解决十五数码问题一、15数码问题的描述及其状态空间法表示(1)15数码问题描述15数又叫移棋,是人工智能中的一个典。所的15数:就是在一个4×4的16格棋上,放有15个将牌,每一个将牌都刻有1~15中的某一个数。棋中留有一个空格,允其周的某一个将牌向空格移,通移将牌就可以不断改将牌的布局。种求解的是:定一种初始的将牌布局或构(称初始状)和一个目布局(称目状),如何移数,从初始状到目状的,如1所示。的就是找一个合法的作序列512114123413631056781427991011121158131415(a)初始状(b)目状115数的一个例(2)状态空间法表示人工智能的求解是以知表示基的。如何将已得的有关知以算机内部代形式加以合理地描述、存、有效地利用即是表示解决的[1]。当前的知表示方法有十余种,如:一表示法、生式表示法、状空表示法、网格表示法、框架表示法、脚本表示法、面向象表示法等。任何一个定的可能存在多种知表示方法,人能够依照待求解的域知合适的知表示方法。里我只状空表示法。把求解的表示成状、操作、束、初始状和目状。状空就是全部可能的状的会集。求解一个就是从初始状出,不断用可用的操作,在足束的条件下达到目状。求解程就可以看作是状在状空的移。状是描述某不相同事物的差而引入的一最少量q0,q1,?,qn的有序会集。的状空是一个表示全部可能状及其关系的。三元状(S、F、G),其中S全部可能的初始状会集,F操作符会集,G目状会集。十五数的状空法:初始状S[4][4]={5,12,11,4,13,6,3,10,14,2,7,9,1,15,0,8};(0表示空格)目状G[4][4]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0};操作符会集F={空格上移,空格下移,空格左移,空格右移}状空的一个解:是一个有限的操作算子序列,它使初始状化目状:S0-f1->S1-f2->...fk->G。二、A*算法的基根源理、算法步骤、流程图(1)A*算法基根源理用A算法解决十五数码问题用A算法解决十五数码问题8用A算法解决十五数码问题A*算法是一种有序搜寻算法,其特点在于对议论函数的定义上。对于一般的有序搜寻,总是选择f值最小的节点作为扩展节点。因此,f是依照需要找到一条最小代价路径的见解来估计节点的,可考虑将每个节点n的估价函数值分解为两个重量:从初步节点到节点n的最小代价路径的代价与从节点n到目标节点的最小代价路径的代价之和,也就是说f(n)是拘束经过节点n的一条最小代价路径的代价的一个估计。再定义一个函数f*,使得在随意一个节点n上的函数值f*(n)就是从节点S到节点n的一条最正确路径的实质代价加上从节点n到目标节点的一条最正确路径的代价之和,即:*f(n)=g(n)+h(n)议论函数f是f*的一个估计,这个估计可由下式给出:f(n)=g(n)+h(n)其中g是g*的估计,h是h*的估计。g*(n)的估计g(n)就是搜寻树中从初始节点到当前节点n的这段路径的代价,这一代价能够由从初始节点到当前节点n搜寻路径时,把遇到的各段路径的代价加起来给出。h*(n)的估计h(n)依赖于有关问题的领域的启示信息,于是被称作启示函数。在启示函数中,应用的启示信息(问题知识)越多,扩展的节点就越少,这样就能更快地搜寻到目标节点。(2)A*算法基本步骤1)生成一个只包含开始节点n0的搜寻图G,把n0放在一个叫OPEN的列表上。2)生成一个列表CLOSED,它的初始值为空。3)若是OPEN表为空,则失败退出。4)选择OPEN上的第一个节点,把它从OPEN中移入CLPSED,称该节点为n。5)若是n是目标节点,顺着G中,从n到n0的指针找到一条路径,获得解决方案,成功退出(该指针定义了一个搜寻树,在第7步建立)。6)扩展节点n,生成以后继结点集M,在G中,n的祖先不能够在M中。在G中部署M的成员,使他们成为n的后继。7)从M的每一个不在G中的成员建立一个指向n的指针(比方,既不在OPEN中,也不在CLOSED中)。把M1的这些成员加到OPEN中。对M的每一个已在OPEN中或CLOSED中的成员m,若是到当前为止找到的到达m的最好路径经过n,就把它的指针指向n。对已在CLOSED中的M的每一个成员,重定向它在G中的每一个后继,以使它们顺着到当前为止发现的最好路径指向它们的祖先。8)按递加f*值,重排OPEN(相同最小f*值可依照搜寻树中的最深节点来解决)。9)返回第3步。在第7步中,若是搜寻过程发现一条路径到达一个节点的代价比现存的路径代价低,就要重定向指向该节点的指针。已经在CLOSED中的节点后辈的重定向保存了后边的搜寻结果,但是可能需要指数级的计算代价。(3)流程图以下所示:三、实例1)本文采用C#基于对话框的程序设计,在图形界面上显示出十五数码格局并能够随意设置数码的地址。确定初始状态格局后,使用用A算法解决十五数码问题用A算法解决十五数码问题3用A算法解决十五数码问题A*算法进行搜寻。本方法实现的程序中用到的估价函数以下:f(n)=h(n)+g(n)。其中,h(n)用A算法解决十五数码问题用A算法解决十五数码问题4用A算法解决十五数码问题代表搜寻树中节点n的深度,根节点深度是0。启示函数g(n)定义为当前节点与其目标节点相应地址不相同元素的个数。点击初始化按钮,开始执行搜寻,成功或失败后提示。(2)程序实例显现1)0步:初始状态,输入0~16的数码输入达成后,点击初始化,呈以下图所示:2)10步:初始态以以下图所示:数码经过上移一次、左移三次、下移三次,右移三次到达目标状态,以以下图:(3)性能指标空格不计,则16宫图的某状态为数1到15的一个排列,记为n0nln2n3n4n5n6n7n8n9n10n11n12n13n14n15。两个状态之间可否可达能够经过计算两者的逆序数来判断,若两者逆序数的奇偶性相同则可达,否则不能达。也即对于任一个目标状态节点,有(1/2)×16!=0个状态可达该节点。据统计,单纯用A*算法要开销几个小时时间才能判断出不能达到目标状态,这时CLOSED表长度为0。但由于本程序弊端甚多,因此算法的时间复杂度会更高。四、个人领悟初学人工智能时,最先联想到的即是机器人,素来感觉机器人是特别智能且特别奇特的,这也令人工智能在我的思想里笼罩了一层非同平时的面纱,特别迫切的想要认识它的内涵。经过十几学时的学****我对人工智能已有了初步认识,也深深的被它吸引,特别经过本次程序设计,对人工智能的学****兴趣更加浓厚了!15数码问题是人工智能的一个经典的问题。本文中经过设计一个基于A*算法的状态空间搜寻程序,对于给定的初始状态,采用f(n)=h(n)+g(n)表示以当前节点与其目标节点相应地点不相同元素的个数与搜寻深度之和作为启示函数的胸襟,并用可视化编程语言C#来实现该问题。在程序的设计与实现过程中,遇到了很多的问题。第一由于初学人工智能,理解上有必定的困难,对A*算法的深入学****是一个曲折的过程。其次,在程序真切的设计及实现过程中,的确需要开销大量的精力来思虑,屡次试验。所设计的程序能够运行,但弊端还是特别之大的,如其中重排OPEN表时,没有进行真切意义上的重新排列,可是选出代价最小的放在最先的地址,这实质上对程序的运行效率有很大的影响。同时经过输入大量的初始状态和目标状态发现,在一般情况下都能够找到最优的动作序列。但对某些稍微复杂的初始状态虽能获得正确解却不能够完满获得最短的搜寻路径,对于某些极其复杂的状态,甚至得不到解。这是有待进一步学****并改进的地方。但本程序还是有些值得必定之处。界面设计比较友好,简单用A算法解决十五数码问题用A算法解决十五数码问题5用A算法解决十五数码问题操作。而且在程序开始时,就判断目标状态可否可达,这样可节约大量的时间。诚然很多地方设计的不尽如意,但这是针对十五数码这个详尽问题的一点优化。附录:Mainext=();if==""){用A算法解决十五数码问题用A算法解决十五数码问题6用A算法解决十五数码问题("请将全部空格填写完满!");return;}Start_Matrix[i][j]=;}}oString();}}currentIndex=(++currentIndex)%;if(currentIndex==0)=false;}=i;digitalPos[matrix[i][j]].y=j;}}returndigitalPos;}privateintcost;publicintCost{get{returncost;}set{cost=value;}}<3&&!=1){_15DigitalNodechildNode=new_15DigitalNode,this,+1,2);swap(ref[digitalPos[0].x][digitalPos[0].y],ref[digitalPos[0].x+1][digitalPos[0].y]);(objectDigitalPos);(childNode);}>0&&!=2){用A算法解决十五数码问题用A算法解决十五数码问题7用A算法解决十五数码问题_15DigitalNodechildNode=new_15DigitalNode,this,+1,1);swap(ref[digitalPos[0].x][digitalPos[0].y],ref[digitalPos[0].x-1][digitalPos[0].y]);用A算法解决十五数码问题用A算法解决十五数码问题8用A算法解决十五数码问题(objectDigitalPos);(childNode);}<3&&!=3){_15DigitalNodechildNode=new_15DigitalNode,this,+1,4);swap(ref[digitalPos[0].x][digitalPos[0].y],ref[digitalPos[0].x][digitalPos[0].y+1]);(objectDigitalPos);(childNode);}>0&&!=4){_15DigitalNodechildNode=new_15DigitalNode,this,+1,3);swap(ref[digitalPos[0].x][digitalPos[0].y],ref[digitalPos[0].x][digitalPos[0].y-1]);(objectDigitalPos);(childNode);}returnchildNodes;}ost>((_15DigitalNode)openList[i]).Cost)min=i;}objecttemp=openList[min];openList[min]=openList[0];openList[0]=temp;}evel!=0){(((_15DigitalNode)result[-1]).parentNode);}();returnresult;}}}用A算法解决十五数码问题用A算法解决十五数码问题9用A算法解决十五数码问题