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

一、15数码问题的描述及其状态空间法表示（1）15数码问题描述15数码问题又叫移棋盘问题，是人工智能中的一个经典问题。所谓的15数码问题：就是在一个4×4的16宫格棋盘上，摆放有15个将牌，每一个将牌都刻有1～15中的某一个数码。棋盘中留有一个空格，允许其周围的某一个将牌向空格移动，这样通过移动将牌就可以不断改变将牌的布局。这种求解的问题是：给定一种初始的将牌布局或结构(称初始状态)和一个目标布局(称目标状态)，问如何移动数码，实现从初始状态到目标状态的转变，如图1所示。问题的实质就是寻找一个合法的动作序列512114136310142791158123456789101112131415(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*算法是一种有序搜索算法，其特点在于对评价函数的定义上。对于一般的有序搜索，总是选择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）流程图如下所示：开始把n0放入OPEN表，记f=h定义CLOSED表，初始值为空OPEN为空?选取OPEN表上具有最小f值的节点n放入CLOSED表失败退出YNn是目标节点？成功Y扩展n节点，产生其后继节点successorN建立从successor返回n的指针计算g(suc)=g(n)+c(n,suc)n属于OPEN表？n属于CLOSED表？Nsuccessor=m，把它添加到n的后继节点列表中g(suc)g(m)?YY重新确立m的父辈节点为n,并修正父辈节点的g值和n值，记下g(m)Y计算f值把successor放入OPEN表，填进n的后裔表MNN三、实例（1）本文采用C#基于对话框的程序设计，在图形界面上显示出十五数码格局并可以随意设置数码的位置。确定初始状态格局后，使用A*算法进行搜索。本方法实现的程序中用到的估价函数如下：f(n)=h(n)+g(n)。其中，h(n)代表搜索树中节点n的深度，根节点深度是0。启发函数g(n)定义为当前节点与其目标节点相应位置不相同元素的个数。点击初始化按钮，开始执行搜索，成功或失败后提示。（2）程序实例展示1）0步：初始状态，输入0~16的数码输入完毕后，点击初始化，呈下图所示：2）10步：初始态如下图所示：0数码经过上移一次、左移三次、下移三次，右移三次到达目标状态，如下图：（3）性能指标空格不计，则16宫图的某状态为数1到15的一个排列，记为n0nln2n3n4n5n6n7n8n9n10n11n12n13n14n15。两个状态之间是否可达可以通过计算两者的逆序数来判断，若两者逆序数的奇偶性相同则可达，否则不可达。也即对于任一个目标状态节点，有(1/2)×16!=10461394944000个状态可达该节点。据统计，单纯用A*算法要花费几个小时时间才能判断出不能达到目标状态，这时CLOSED表长度为10461394944000。但由于本程序缺陷甚多，所以算法的时间复杂度会更高。四、个人体会初学人工智能时，最先联想到的便是机器人，一直感觉机器人是非常智能且非常神秘的，这也令人工智能在我的思想里笼罩了一层非同寻常的面纱，非常迫切的想要了解它的内涵。经过十几学时的学习，我对人工智能已有了初步了解，也深深的被它吸引，尤其通过本次程序设计，对人工智能的学习兴趣更加浓厚了！15数码问题是人工智能的一个经典的问题。本文中通过设计一个基于A*算法的状态空间搜索程序，对于给定的初始状态，采用f(n)=h(n)+g(n)表示以当前节点与其目标节点相应位置不相同元素的个数与搜索深度之和作为启发函数的度量，并用可视化编程语言C#来实现该问题。在程序的设计与实现过程中，遇到了很多的问题。首先由于初学人工智能，理解上有一定的困难，对A*算法的深入学习是一个曲折的过程。其次，在程序真正的设计及实现过程中，的确需要花费大量的精力来思考，反复试验。所设计的程序能够运行，但缺陷还是非常之大的，如其中重排OPEN表时，没有进行真正意义上的重新排列，只是选出代价最小的放在最先的位置，这实际上对程序的运行效率有很大的影响。同时通过输入大量的初始状态和目标状态发现，在一般情况下都可以找到最优的动作序列。但对某些稍微复杂的初始状态虽能得到正确解却不能完全得到最短的搜索路径，对于某些极其复杂的状态，甚至得不到解。这是有待进一步学习并改进的地方。但本程序还是有些值得肯定之处。界面设计比较友好，容易操作。而且在程序开始时，就判断目标状态是否可达，这样可节约大量的时间。虽然很多地方设计的不尽如意，但这是针对十五数码这个具体问题的一点优化。附录：//ProgramusingSystem;usingSystem.Collections.Generic;usingSystem.Windows.Forms;namespace_15Digital{staticclassProgram{///summary///应用程序的主入口点。////summary[STAThread]staticvoidMain(){Application.EnableVisualStyles();Application.SetCompatibleTextRenderingDefault(false);Application.Run(newForm1());}}}//Form1usingSystem;usingSystem.Collections;usingSystem.Collections.Generic;usingSystem.ComponentModel;usingSystem.Data;usingSystem.Drawing;usingSystem.Text;usingSystem.Windows.Forms;usingSystem.Windows.Forms.ComponentModel;usingSystem.Reflection;namespace_15Digital{publicpartialclassForm1:Form{publicForm1(){InitializeComponent();}privateArrayListresult;//存储初始状态到目标状态的各个变换过程的状态privatestaticintcurrentIndex=0;//记录初始状态到目标状态共需要的步数///summary///对初始状态和目标状态矩阵进行初始化，其中的16个数码为0~15////summaryprivatevoidinitialize(){//定义初始态和目标态矩阵int[][]Start_Matrix=newint[4][];int[][]End_Matrix=newint[4][];for(inti=0;i4;i++){Start_Matrix[i]=newint[4];End_Matrix[i]=newint[4];}//目标状态矩阵的赋值for(inti=0;i4;i++){for(intj=0;j4;j++){End_Matrix[i][j]=4*i+j+1;}}End_Matrix[3][3]=0;//获取初始状态矩阵for(inti=0;i4;i++){for(intj=0;j4;j++){intk=4*i+j+1;TextBoxtbox=(TextBox)this.findTextbox(textBox+k);intk2=16+4*i+j+1;((TextBox)this.findTextbox(textBox+k2)).Text=tbox.Text.ToString();if(tbox.Text==){MessageBox.Show(请将所有空格填写完整！);return;}Start_Matrix[i][j]=Convert.ToInt32(tbox.Text);}}//计算能否在50飞、步之内搜索到目标状态_15Digitalfifteen=new_15Digital(Start_Matrix,