人工智能课程大作业
基于A星算法的八数码问题求解
学号： 姓名：
摘要：在人工智能领域中, 八数码问题一直都是一个游戏难题。介绍了八数码问题, 然后在启发式搜
索算法上对A * 算法定义进行了解释, 并在其旨在提高搜索效率的方面作了比较详尽的介绍,
详细描述了基于图搜索算法的解决此类问题的一种启发式搜索算法： A* 算法。再依据这种
算法用可视化编程语言VC+ + 6. 0 来实现八数码问题的求解过程, 取得了预期的搜索解, 提
高了搜索效率。
关键词：八数码问题; 启发式搜索; A* 算法
本组成员：
本人分工：主要负责进行问题分析，提出解决方案，进行系统设计，算法上具体负责主函数的编写。
1 引言
八数码问题是人工智能的一个经典的问题。文中通过设计一个基于A* 算法的状态空间搜索程
序, 对于给定的初始状态, 采用h ( n ) = p ( n ) 表示以每一个将牌与目标位置之间距离的总和
作为启发函数的度量, 并用可视化编程语言VC+ + 来实现该问题。 2 算法原理与系统设计
1）A*算法思想
A*算法是对A算法的估价函数f(n)=g(n)+h(n)加上某些限制后得到的一种启发式搜索算法。A*
算法对A算法中的g(n)和h(n)分别提出如下限制：第一，g(n)是对最小代价g*(n)的估计，且g(n)>0；
第二，h(n)是最小代价h*(n)的下界，即对任意节点n 均有h(n)≤h*(n)。即满足上述两条限制的A算
法称为A*算法。
2）估价函数
用来估算节点希望程度的量度，叫估价函数f(x)，f(x)=g(x)+h(x)。g(x)为从初始节点到当前节点
已经付出的代价，h(x)为从当前节点到目标节点的最优路径的估计代价。本算法中令g(x)为当前节点
的深度depth，h(x)为当前节点每个数字位与目标节点数字位间距离和dist，进一步考虑当前结点与
目标结点的距离信息，令启发函数h ( n )为当前8个数字位与目标结点对应数字位距离和（不考虑中
1
人工智能课程大作业
间路径），满足h ( n ) <= h * ( n )， 且对于目标节点有 h ( t ) = 0，对于结点m和n （n 是m的子结点） 有h ( m ) – h ( n ) <= 1满足单调限制条件。
3）open和closed表的数据结构表示
对open表的操作，每次需要得到所有待扩展结点中 f 值最小的那个结点。closed表存储已扩展的结点间的扩展关系，主要用于输出路径。closed表中任意一个结点都存储有它的前驱结点的信息，考虑closed表中任意一个结点，如果它是初始结点，它没有前驱结点，如果不是根结点，扩展该结点时它的前驱结点已经记录。从而在closed表中形成扩展关系的树状结构。因为只需要前驱点的下标位置，可以用数组实现。每个结点记录８数码格局和它的前驱结点的下标。
4）问题分析
首先，八数码问题包括一个初始状态(src) 和 目标状态(dest)，所谓解八数码
问题就是在两个状态间寻找一系列可过渡状态。这个状态是否存在就是我们要解决的第一个问题。 解决八数码问题，主要面临的问题有：
Q1）开始状态S到目标状态D是否可解；
Q2）扩展节点的选择；
Q3）扩展待扩展节点，该节点是否已扩展过；
Q4）判断是否已达目标节点D；
问题Q 1）通过逆序数的奇数偶数来判断。因为在空白移动过程中，数码的逆序数不改变。左右移动，数码序列不变。上下移动，数码序列中某个数字则移动了两位。问题的实质就是：如果是N*N的数码盘的话，左右移动，数码序列不变；上下移动则数码序列变动N-1位。若N为奇数则在变动过程中其逆序数不会改变。而八数码问题为3*3矩阵，3为奇数，故逆序数不作改变。故可通过判断当前状态S的逆序数以及目标状态SD的数字序列的逆序数的奇偶性是否相同来判断该问题是否可解。
问题Q2）扩展节点的选择通过getmin函数，根据估价函数f来获得代价最小的节点。
问题Q3）扩展节点即为上下左右四个方向移动空格到没有扩展过的节点中去，要判断是否扩展过，只要跟之前的状态做比较即可。
问题Q4）是否达到目标节点，将当前节点和目标节点进行比较。
算法的功能：产生8数码问题的解(由初始状态到达目标状态的过程）
输入：初始状态，目标状态
2
人工智能课程大作业
输出：从初始状态到目标状态的一系列过程
算法描述：
Begin：
读入初始状态和目标状态，并计算初始状态评价函数值f； 根据初始状态和目标状态，判断问题是否可解； If(问题可解) 把初始状态假如open表中； While（未找到解&&状态表非空） ①在open表中找到评价值最小的节点，作为当前结点；
②判断当前结点状态和目标状态是否一致，若一致，跳出循环；否则跳转到③； ③对当前结点，分别按照上、下、左、右方向移动空格位置来扩展新的状态结点，并计算新扩展结点的评价值f并记录其父节点；
④对于新扩展的状态结点，判断其是否重复，若不重复，把其加入到open表中； ⑤把当前结点从open表中移除；
End while End if
输出结果；
End
算法流程如下：
3
人工智能课程大作业
3 系统实现
5、main函数，主程序运行步骤为： （1）先读入八数码初始状态src，以及目标状态dest。通过open表的push_back()函数，把初始状态src存入open中。
4
人工智能课程大作业
（2）A*算法搜索开始，设置while循环，直到找到目标状态或者open表为空或者无解的情况下结束。
（3）不同的八数码初始状态和目标状态不一定有解，所以要根据两种状态下的奇偶性是否一致来判断（详见实验思想的问题分析）。
5
人工智能课程大作业
（4）若奇偶性一致，则继续搜索。如果测试到open表为空，没有找到目标状态，则表示无解，判断open表是否为空，函数如下：
（5）open非空，搜索未结束，则寻找open表中最小估价值节点进行扩展。
设置int temp,du,dd,dr,dl; Node nu,nd,nr,nl; temp为临时变量,d*为向上下左右移动后的距离dist， n*为向上下左右移动后的八数码状态节点，扩展节点就是通过空格的上下左右移动来获得子节点。
6
人工智能课程大作业
其中，扩展节点之前得先判断节点是否可扩展，即是否未扩展过，不存在于open,close表中。
Distance函数是用来计算当前状态到目标状态的距离，即坐标差绝对值之和。
7
人工智能课程大作业
（6）最后，如果发现扩展的节点与目标节点一样，则表示找到最优解使得估价函数值最小，将搜索步骤打印出来。
4 实验或测试结果
1．无解的情况
2、有解的情况
8
人工智能课程大作业
9
人工智能课程大作业
5 结论
通过本次实验，我更加深入的了解了A*算法、启发函数以及搜索方法。启发式搜索有很多种方法，比如：局部择优搜索法，最好优先搜索法等等，其中也包括了A*算法，这些算法都使用了启发函数，但在具体的选取最佳搜索节点时的策略不同。A*是众多搜索方法中综合效果最好的。使用A*算法，也要懂得构建估价函数，不同的估计函数对实验结果影响很大。比如该实验，对于f(n)的考虑最简单的便是比较每个状态与目标状态相比错位的牌数。这个启发意味着如果其他条件相同，那么错位的牌数最少的状态可能最接近目标状态。然而这个启发没有使用从棋盘格局中可以得到的所有信息，因为它没有把牌必要的移动距离纳入考虑。一个―更好一点‖的启发是对错位的牌必须要移动的距离求和，为了达到这个目的，每张牌必须要移动的每个方格算为一个距离单位。这两种启发都存在一种不足，就是没有认识到点到牌的难度。也就是说，如果两张牌是彼此相邻的，而且目标是要求互相颠倒它们的位置，那么要把它们放到适当的位置需要远不止两次的移动，因为各张牌必须相互绕来绕去。这个实验中，我采取的是把距离加上深度，来作为估价函数值。除此之外，还有很多细节都可以影响实验，这里就不一一列举了。
参考文献
[1] Artificial Intelligence——A Modern Approach. Stuart Russell, Peter Norvig. 人民邮电出版社,2004
[2] Artificial Intelligence, Rob Callan. 电子工业出版社,2004
[ 3]林尧瑞, 马少平. 人工智能导论[ M] . 北京: 清华大学出版社, 1989.
[ 4]马少平, 朱小燕, 人工智能[ M] . 北京: 清华大学出版社, 2004.
[ 5]尼尔逊N J. 人工智能原理[ M] . 北京: 科学出版社, 1983.
10
第二篇：人工智能大作业
内蒙古科技大学2012/2013 学年第一学期
《人工智能》大作业
课程号： 67111317
考试方式：大作业
任课教师：陈淋艳
使用专业、年级
班级：
学号：
姓名：
一、 （15分）智能、智力、能力的含义是什么？什么
是人工智能？人类研究人工智能的最终目标是什么？
二、 （15分）传教士与野人问题：有三个传教士和三
个野人来到河边，河边只有一条一次最多可供两个人过河的小船，传教士如何用这条小船过河才能使河两边的野人数目决不会超过传教士的数目？
指定状态描述的格式，开始状态和目标状态；画出状态空间图。
（只要画出河两边野人数目不会超过传教士数目的状态即可）。
三、 (10分)用谓词公式表示下列语句：因为老百姓授法
律管制，所以晁盖劫了生辰纲，触犯了宋王朝的法律，受到官府追究；而达官贵人和恶少不受法律管制，所以高衙内强抢民女，虽然也违法，却可以横行无忌。
四、 (20分)什么是演绎推理？他的推理规则是什么？
试用谓词演算语句集合表示下面这段话；并用归结反演的方法回答下列问题：
设TONY，|MIKE和JOHN属于ALPINE俱乐部，
ALPINE俱乐部的成员不是滑雪运动员就是登山运动员。登山运动员不喜欢下雨，而且任何不喜欢雪的人都不是滑雪运动员。MIKE讨厌TONY所喜欢的一切东西，而喜欢TONY所讨厌的一切东西。TONY喜欢雨和雪。试问有没有ALPINE俱乐部的成员，他是一个登山运动员但不是滑雪运动员。
五、(20分)在主观Bayes推理中，LS和LN的意义是什么？
设系统中有如下规则：
R1：IF E1 THEN （50 0，0.01）H1
R2 IF E2 THEN （1，100）H1
R3：IF E3 THEN （1000，1）H2
R4：IF H1 THEN （20，1）H2
并且已知P(H1)=0.1， P(H2)=0.1， P(H3)=0.1，初始
证据的概率为P(E1|S1)=0.5 ，P(E2|S2)=0 ，P(E3|S3)=0.8，用主观Bayes方法求H2的后验概率P(H2|S1& S2& S3)。
结课报告题目:
1、总结知识表达技术。（选取三种知识表达放法加以介绍，并进行比较）
2、查找两篇或三篇已发表的与人工智能理论相关的论文，从文章所论述的问题，阐述的理论，其社会效益，与原有的方法相比，他的优缺点等。
3、介绍一已有的专家系统。
4、写一篇文章介绍人工神经网络。（应用领域，人工神经元模型，学习方法）
要求：选以上题目之一或自选题目写一篇5000字左右的报告，要有关键字，图要有图号，最后要有参考资料。