1、人工智能论文讲解滨江学院 课程论文课程名称: 人工智能 院 系 滨江学院 专 业 自动化 学 号 * 姓 名 周程 指导老师 孙玉宝 二一六 年 六 月 二十 日摘要人工智能是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、 技术及应用系统的一门新的技术科学。 人工智能的研究方向、研究领域、应用领域值得我们关注和探讨。本文以状态空间搜索的观点讨论了八数码问题，给出了八数码问题的Java算法与实现的思想，分析了A*算法的可采纳性等及系统的特点。关键词:九宫重排，状态空间，启发式搜索，A*算法引言九宫重排问题是人工智能当中有名的难题之一。问题是在33方格盘上，放有八个数码，剩下一个位置为空，每
2、一空格其上下左右的数码可移至空格。问题给定初始位置和目标位置，要求通过一系列的数码移动，将初始状态转化为目标状态。状态转换的规则：空格四周的数移向空格，我们可以看作是空格移动，它最多可以有个方向的移动，即上、下、左、右。九宫重排问题的求解方法，就是从给定的初始状态出发，不断地空格上下左右的数码移至空格，将一个状态转化成其它状态，直到产生目标状态。 一、 问题描述1.1 待解决问题的解释 八数码游戏（八数码问题）描述为：在33组成的九宫格棋盘上，摆有八个将牌，每一个将牌都刻有1-8八个数码中的某一个数码。棋盘中留有一个空格，允许其周围的某一个将牌向空格移动，这样通过移动将牌就可以不断改变将牌的布
3、局。这种游戏求解的问题是：给定一种初始的将牌布局或结构（称初始状态）和一个目标的布局（称目标状态），问如何移动将牌，实现从初始状态到目标状态的转变。 1.2 问题的搜索形式描述（4要素） 初始状态：8个数字将牌和空格在九宫格棋盘上的所有格局组成了问题的状态空间。其中，状态空间中的任一种状态都可以作为初始状态。后继函数：通过移动空格（上、下、左、右）和周围的任一棋子一次，到达新的合法状态。目标测试：比较当前状态和目标状态的格局是否一致。路径消耗：每一步的耗散值为1，因此整个路径的耗散值是从起始状态到目标状态的棋子移动的总步数。1.3 解决原理对于八数码问题的解决，首先要考虑是否有答案。每一个状态
4、可认为是一个19的矩阵，问题即通过矩阵的变换，是否可以变换为目标状态对应的矩阵？由数学知识可知，可计算这两个有序数列的逆序值，如果两者都是偶数或奇数，则可通过变换到达，否则，这两个状态不可达。这样，就可以在具体解决问题之前判断出问题是否可解，从而可以避免不必要的搜索。 常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找，直到找到目标为止。深度优先是按照一定的顺序前查找完一个分支，再查找另一个分支，以至找到目标为止。 广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法。于八数码问题状态空间共有9!个状态，对于八
5、数码问题如果选定了初始状态和目标状态，有9!/2个状态要搜索，考虑到时间和空间的限制，在这里采用A算法作为搜索策略。在这里就要用到启发式搜索启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无畏的搜索路径，提到了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。二、 算法介绍2.1 搜索算法一般介绍不管哪种搜索，都统一用这样的形式表示：搜索的对象是一个图，它面向一个问题，不一定有明确的存储形式，但它里面的一个结点都有可能是一个解，搜索的目的有两个方面，或者求可行解，或者从可行解集中求最优解。
6、搜索算法可分为两大类：无信息的搜索算法和有信息的搜索算法。无信息的搜索又称盲目搜索，其特点是只要问题状态可以形式化表示，原则上就可用使用无信息的搜索，无信息搜索有如下常见的几种搜索策略：广度优先搜索、代价一致搜索、深度优先搜索、深度有限搜索、迭代深入优先搜索、双向搜索。为了改善上面的算法，我们需要对展开后续结点时对子结点有所了解，这里需要一个估值函数，估值函数就是评价函数，它用来评价子结点的好坏，因为准确评价是不可能的，所以称为估值。这就是我们所谓的有信息搜索。如果估值函数只考虑结点的某种性能上的价值，而不考虑深度，比较有名的就是有序搜索，它着重看好能否找出解，而不看解离起始结点的距离（深度）
7、。如果估值函数考虑了深度，或者是带权距离（从起始结点到目标结点的距离加权和），那就是A*如果不考虑深度，就是说不要求最少步数，移动一步就相当于向后多展开一层结点，深度多算一层，如果要求最少步数，那就需要用A*。简单的来说A*就是将估值函数分成两个部分，一个部分是路径价值，另一个部分是一般性启发价值，合在一起算估整个结点的价值，考虑到八数码问题的特点，在本实验中使用A*算法求解。A*搜索是一种效的搜索算法，它把到达节点的耗散g(n)和从该节点到目标节点的消耗h(n)结合起来对节点进行评价：f(n)=g(n)+h(n)。当h(n)是可采纳时，使用Tree-Search的A*算法将是最优的。2.2
8、算法伪代码算法的功能：产生8数码问题的解(由初始状态到达目标状态的过程）输入：初始状态，目标状态输出：从初始状态到目标状态的一系列过程算法描述：Begin： 读入初始状态和目标状态，并计算初始状态评价函数值f； 根据初始状态和目标状态，判断问题是否可解； If(问题可解) 把初始状态假如open表中； While（未找到解&状态表非空） 在open表中找到评价值最小的节点，作为当前结点；判断当前结点状态和目标状态是否一致，若一致，跳出循环；否则跳转到；对当前结点，分别按照上、下、左、右方向移动空格位置来扩展新的状态结点，并计算新扩展结点的评价值f并记录其父节点；对于新扩展的状态结点，判断其是否
9、重复，若不重复，把其加入到open表中；把当前结点从open表中移除； End while End if输出结果； End算法流程如下：问题规模：对于任一给定可解初始状态，状态空间有9!/2=181440个状态；当采用不在位棋子数作为启发函数时，深度超过20时，算法求解速度缓慢；三、数据介绍3.1 数据结构 static int target9=1,2,3,8,0,4,7,6,5; 全局静态变量，表示目标状态class eight_numprivate: int num9; 定义八数码的初始状态 int not_in_position_num; 定义不在正确位置八数码的个数 int deapt
10、h; 定义了搜索的深度 int eva_function; 评价函数的值，每次选取最小的进行扩展public: eight_num* parent; 指向节点的父节点 eight_num* leaf_next; 指向open表的下一个节点 eight_num* leaf_pre; 指向open 表的前一个节点 初始状态的构造函数 eight_num(int init_num9); eight_num(int num1,int num2,int num3,int num4,int num5,int num6,int num7,int num8,int num9)eight_num(void) 计
11、算启发函数g(n)的值void eight_num:cul_para(void)显示当前节点的状态void eight_num:show()复制当前节点状态到一个另数组中void eight_num:get_numbers_to(int other_num9)设置当前节点状态(欲设置的状态记录的other数组中)void eight_num:set_num(int other_num9)eight_num& eight_num:operator=(eight_num& another_8num)eight_num& eight_num:operator=(int other_num9)int
12、eight_num:operator=(eight_num& another_8num)int eight_num:operator=(int other_num9)空格向上移int move_up(int num9)空格向下移int move_down(int num9)空格向左移int move_left(int num9)空格向右移int move_right(int num9)判断可否解出int icansolve(int num9,int target9)判断有无重复int existed(int num9,eight_num *where)寻找估价函数最小的叶子节点eight_nu
13、m* find_OK_leaf(eight_num* start)3.2 实验结果h: 启发函数（不在位将牌数）初始状态目标状态是否有解启发函数用时步数3 2 18 0 47 6 5 1 2 3 8 0 4 7 6 5 否h-1 0 42 7 38 5 6 1 2 3 8 0 4 7 6 5是h2875ms211 0 38 2 47 6 5 1 2 3 8 0 4 7 6 5是h0ms13.3 系统中间及最终输出结果（要求有屏幕显示）目标状态默认为1 2 3 8 0 4 7 6 5 .a) 初始状态是3 2 1 8 0 4 7 6 5，用h作为启发函数结果都如下：b)初始状态是1 04 2 7
14、 3 8 5 6，用h作为启发函数结果都如下：b)初始状态是1 0 3 8 2 4 7 6 5，用h作为启发函数结果都如下：参考文献1合成生物学与人工生命体 作者:叶邦策王建军 来源:科学杂志；2量子神经网络及其应用南京邮电学院信号与信息处理研究所李飞; 郑宝玉; 赵生妹；3人工神经网络在组织网络化发展评价中的应用 朱启红 张 钢计算机应用研究 2007年第06期；4神经网络研究的发展趋势 廖晓峰李传东 5中科院半导体研究所半导体人工神经网络实验室；5专家系统的现状及发展趋势 方景文; 机器人, Robot, 编辑部邮箱 1986年 06期；6主体与协同: 专家系统的发展方向 中科院计算所 张子云 曹鹏（计算机世界报2007年102日第41期 B11）专家系统的原理、现状和发展趋势 杨叔子; 郑小军; 水利电力机械。
