2022年用A算法解决十五数码问题.pdf

一、 15 数码问题的描述及其状态空间法表示（1）15 数码问题描述15数码问题又叫移棋盘问题，是人工智能中的一个经典问题所谓的 15数码问题： 就是在一个 44的16宫格棋盘上，摆放有15个将牌，每一个将牌都刻有115中的某一个数码棋盘中留有一个空格，允许其周围的某一个将牌向空格移动，这样通过移动将牌就可以不断改变将牌的布局这种求解的问题是：给定一种初始的将牌布局或结构(称初始状态 )和一个目标布局 (称目标状态 )，问如何移动数码， 实现从初始状态到目标状态的转变，如图 1所示问题的实质就是寻找一个合法的动作序列5 12 11 4 13 6 3 10 14 2 7 9 1 15 8 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 (a)初始状态(b)目标状态图1 15数码问题的一个实例（2）状态空间法表示人工智能问题的求解是以知识表示为基础的如何将已获得的有关知识以计算机内部代码形式加以合理地描述、存储、有效地利用便是表示应解决的问题1目前的知识表示方法有十余种，如：一阶谓词逻辑表示法、产生式表示法、状态空间表示法、语义网格表示法、框架表示法、 脚本表示法、 面向对象表示法等。

任何一个给定的问题可能存在多种知识表示方法，人们可以根据待求解问题的领域知识选择适当的知识表示方法这里我们只强调状态空间表示法把求解的问题表示成问题状态、操作、约束、初始状态和目标状态状态空间就是所有可能的状态的集合求解一个问题就是从初始状态出发，不断应用可应用的操作，在满足约束的条件下达到目标状态问题求解过程就可以看成是问题状态在状态空间的移动状态是为描述某类不同事物间的差别而引入的一组最少变量q0，q1，, ， qn的有序集合问题的状态空间是一个表示该问题全部可能状态及其关系的图记为三元状态(S、F、G)，其中 S所有可能的问题初始状态集合，F操作符集合， G 目标状态集合十五数码的状态空间法：初始状态 S44=5,12,11,4,13,6,3,10,14,2,7,9,1,15,0,8 ；(0 表示空格 ) 目标状态 G44=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*算法基本原理名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 25 页 - - - - - - - - - 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 ，称该节点为n5）如果 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）流程图如下所示：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 25 页 - - - - - - - - - 开始把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 步：初始状态，输入016 的数码名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 25 页 - - - - - - - - - 输入完毕后，点击初始化，呈下图所示：2）10 步：初始态如下图所示：0 数码经过上移一次、左移三次、下移三次，右移三次到达目标状态，如下图：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 25 页 - - - - - - - - - （3）性能指标空格不计，则 16宫图的某状态为数1到15的一个排列，记为n0nln2n3n4n5n6n7n8n9n10n11n12n13n14n15。

两个状态之间是否可达可以通过计算两者的逆序数来判断， 若两者逆序数的奇偶性相同则可达，否则不可达也即对于任一个目标状态节点，有(1/2)16 !=10461394944000 个状态可达该节点据统计， 单纯用 A*算法要花费几个小时时间才能判断出不能达到目标状态，这时CLOSED 表长度为 10461394944000 但由于本程序缺陷甚多，所以算法的时间复杂度会更高名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 25 页 - - - - - - - - - 四、个人体会初学人工智能时， 最先联想到的便是机器人，一直感觉机器人是非常智能且非常神秘的，这也令人工智能在我的思想里笼罩了一层非同寻常的面纱，非常迫切的想要了解它的内涵经过十几学时的学习，我对人工智能已有了初步了解，也深深的被它吸引，尤其通过本次程序设计，对人工智能的学习兴趣更加浓厚了！15数码问题是人工智能的一个经典的问题本文中通过设计一个基于A* 算法的状态空间搜索程序， 对于给定的初始状态，采用 f(n)=h(n)+g(n) 表示以当前节点与其目标节点相应位置不相同元素的个数与搜索深度之和作为启发函数的度量，并用可视化编程语言C#来实现该问题。

在程序的设计与实现过程中，遇到了很多的问题首先由于初学人工智能，理解上有一定的困难，对 A*算法的深入学习是一个曲折的过程其次，在程序真正的设计及实现过程中，的确需要花费大量的精力来思考，反复试验所设计的程序能够运行，但缺陷还是非常之大的，如其中重排OPEN表时，没有进行真正意义上的重新排列，只是选出代价最小的放在最先的位置，这实际上对程序的运行效率有很大的影响同时通过输入大量的初始状态和目标状态发现，在一般情况下都可以找到最优的动作序列但对某些稍微复杂的初始状态虽能得到正确解却不能完全得到最短的搜索路径，对于某些极其复杂的状态，甚至得不到解这是有待进一步学习并改进的地方但本程序还是有些值得肯定之处界面设计比较友好，容易操作而且在程序开始时，就判断目标状态是否可达，这样可节约大量的时间虽然很多地方设计的不尽如意，但这是针对十五数码这个具体问题的一点优化名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 25 页 - - - - - - - - - 附录：/Program using System; using System.Collections.Generic; using System.Windows.Forms; namespace _15Digital static class Program / / 应用程序的主入口点。

/ STAThread static void Main() Application.EnableVisualStyles(); Application.SetCompatibleTextRenderingDefault(false); Application.Run(new Form1(); /Form1 using System; using System.Collections; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Text; using System.Windows.Forms; using System.Windows.Forms.ComponentModel; using System.Reflection; namespace _15Digital public partial class Form1 : Form。