资源描述：
《用A算法解决十五数码问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、一、15数码问题的描述及其状态空间法表示（1）15数码问题描述15数码问题又叫移棋盘问题，是人工智能中的一个经典问题。所谓的15数码问题：就是在一个4×4的16宫格棋盘上，摆放有15个将牌，每一个将牌都刻有1～15中的某一个数码。棋盘中留有一个空格，允许其周围的某一个将牌向空格移动，这样通过移动将牌就可以不断改变将牌的布局。这种求解的问题是：给定一种初始的将牌布局或结构(称初始状态)和一个目标布局(称目标状态)，问如何移动数码，实现从初始状态到目标状态的转变，如图1所示。问题的实质就是寻找一个合法的动作序列5121141363101427911581234567
2、89101112131415(a)初始状态(b)目标状态图115数码问题的一个实例（2）状态空间法表示人工智能问题的求解是以知识表示为基础的。如何将已获得的有关知识以计算机内部代码形式加以合理地描述、存储、有效地利用便是表示应解决的问题[1]。目前的知识表示方法有十余种，如：一阶谓词逻辑表示法、产生式表示法、状态空间表示法、语义网格表示法、框架表示法、脚本表示法、面向对象表示法等。任何一个给定的问题可能存在多种知识表示方法，人们可以根据待求解问题的领域知识选择适当的知识表示方法。这里我们只强调状态空间表示法。把求解的问题表示成问题状态、操作、约束、初始状态和目标
3、状态。状态空间就是所有可能的状态的集合。求解一个问题就是从初始状态出发，不断应用可应用的操作，在满足约束的条件下达到目标状态。问题求解过程就可以看成是问题状态在状态空间的移动。状态是为描述某类不同事物间的差别而引入的一组最少变量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
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的最小代价路
5、径的代价与从节点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寻找路径时，把遇到的各段路径的
6、代价加起来给出。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步建立
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步
8、。在第7步中，如果搜索过
