一、15数码问题的描述及其状态空间法表示
（1）15数码问题描述
15数码问题又叫移棋盘问题，是人工智能中的一个经典问题。所谓的15数码问题：就是在一个4×4的16宫格棋盘上，摆放有15个将牌，每一个将牌都刻有1～15中的某一个数码。棋盘中留有一个空格，允许其周围的某一个将牌向空格移动，这样通过移动将牌就可以不断改变将牌的布局。这种求解的问题是：给定一种初始的将牌布局或结构(称初始状态)和一个目标布局(称目标状态)，问如何移动数码，实现从初始状态到目标状态的转变，如图1所示 。问题的实质就是寻找一个合法的动作序列
5 13 14 1 12 6 2 15 11 3 7 4 10 9 8 1 5 9 13 2 6 10 14 3 7 11 15 4 8 12 (a)初始状态 (b)目标状态
图1 15数码问题的一个实例
（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为空?Y失败退出N选取OPEN表上具有最小f值的节点n放入CLOSED表n是目标节点？Y成功N扩展n节点，产生其后继节点successor建立从successor返回n的指针计算g(suc)=g(n)+c(n,suc)Yn属于OPEN表？Nsuccessor=m，把它添加到n的后继节点列表中Yn属于CLOSED表？Ng(suc) （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。但由于本程序缺陷甚多，所以算法的时间复杂度会更高。