人工智能关于八数码问题论文

枣庄学院计算机科学系课程设计任务书题目：用A*算法解决八数码问题学号：**************姓名：*******专业：计算机科学与技术课程：人工智能指导教师：****职称：讲师完成时间：2011年12月----2011年12月枣庄学院计算机科学系制2011年12月01日摘要：八数码问题是人工智能中一个很典型的智力问题。本文以状态空间搜索的观点讨论了八数码问题，给出了八数码问题的Java算法与实现的思想，分析了A算法的可采纳性等及系统的特点。关键词九宫重排，状态空间，启发式搜索，A算法1引言九宫重排问题是人工智能当中有名的难题之一。问题是在3×3方格盘上，放有八个数码，剩下一个位置为空，每一空格其上下左右的数码可移至空格。问题给定初始位置和目标位置，要求通过一系列的数码移动，将初始状态转化为目标状态。状态转换的规则：空格四周的数移向空格，我们可以看作是空格移动，它最多可以有４个方向的移动，即上、下、左、右。九宫重排问题的求解方法，就是从给定的初始状态出发，不断地空格上下左右的数码移至空格，将一个状态转化成其它状态，直到产生目标状态。一、问题描述1.1待解决问题的解释八数码游戏（八数码问题）描述为：在3×3组成的九宫格棋盘上，摆有八个将牌，每一个将牌都刻有1-8八个数码中的某一个数码。棋盘中留有一个空格，允许其周围的某一个将牌向空格移动，这样通过移动将牌就可以不断改变将牌的布局。这种游戏求解的问题是：给定一种初始的将牌布局或结构（称初始状态）和一个目标的布局（称目标状态），问如何移动将牌，实现从初始状态到目标状态的转变。1.2问题的搜索形式描述（4要素）初始状态：8个数字将牌和空格在九宫格棋盘上的所有格局组成了问题的状态空间。其中，状态空间中的任一种状态都可以作为初始状态。后继函数：通过移动空格（上、下、左、右）和周围的任一棋子一次，到达新的合法状态。目标测试：比较当前状态和目标状态的格局是否一致。路径消耗：每一步的耗散值为1，因此整个路径的耗散值是从起始状态到目标状态的棋子移动的总步数。1.3解决方案介绍（原理）对于八数码问题的解决，首先要考虑是否有答案。每一个状态可认为是一个1×9的矩阵，问题即通过矩阵的变换，是否可以变换为目标状态对应的矩阵？由数学知识可知，可计算这两个有序数列的逆序值，如果两者都是偶数或奇数，则可通过变换到达，否则，这两个状态不可达。这样，就可以在具体解决问题之前判断出问题是否可解，从而可以避免不必要的搜索。如果初始状态可以到达目标状态，那么采取什么样的方法呢？常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找，直到找到目标为止。深度优先是按照一定的顺序前查找完一个分支，再查找另一个分支，以至找到目标为止。广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不预测的情况下就不可取了。他的效率实在太低，甚至不可完成。由于八数码问题状态空间共有9!个状态，对于八数码问题如果选定了初始状态和目标状态，有9!/2个状态要搜索，考虑到时间和空间的限制，在这里采用A*算法作为搜索策略。在这里就要用到启发式搜索启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无畏的搜索路径，提到了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。启发中的估价是用估价函数表示的，如：f(n)=g(n)+h(n)其中f(n)是节点n的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。在此八数码问题中，显然g(n)就是从初始状态变换到当前状态所移动的步数，估计函数f(n)我们就可采用当前状态各个数字牌不在目标状态未知的个数，即错位数。二、算法介绍2.1搜索算法一般介绍不管哪种搜索，都统一用这样的形式表示：搜索的对象是一个图，它面向一个问题，不一定有明确的存储形式，但它里面的一个结点都有可能是一个解（可行解），搜索的目的有两个方面，或者求可行解，或者从可行解集中求最优解。搜索算法可分为两大类：无信息的搜索算法和有信息的搜索算法。无信息的搜索又称盲目搜索，其特点是只要问题状态可以形式化表示，原则上就可用使用无信息的搜索，无信息搜索有如下常见的几种搜索策略：广度优先搜索、代价一致搜索、深度优先搜索、深度有限搜索、迭代深入优先搜索、双向搜索。我们说DFS和BFS都是蛮力搜索，因为它们在搜索到一个结点时，在展开它的后续结点时，是对它们没有任何‘认识’的，它认为它的孩子们都是一样的‘优秀’，但事实并非如此，后续结点是有好有坏的。好，就是说它离目标结点‘近’，如果优先处理它，就会更快的找到目标结点，从而整体上提高搜索性能。为了改善上面的算法，我们需要对展开后续结点时对子结点有所了解，这里需要一个估值函数，估值函数就是评价函数，它用来评价子结点的好坏，因为准确评价是不可能的，所以称为估值。这就是我们所谓的有信息搜索。如果估值函数只考虑结点的某种性能上的价值，而不考虑深度，比较有名的就是有序搜索（Ordered-Search），它着重看好能否找出解，而不看解离起始结点的距离（深度）。如果估值函数考虑了深度，或者是带权距离（从起始结点到目标结点的距离加权和），那就是A*如果不考虑深度，就是说不要求最少步数，移动一步就相当于向后多展开一层结点，深度多算一层，如果要求最少步数，那就需要用A*。简单的来说A*就是将估值函数分成两个部分，一个部分是路径价值，另一个部分是一般性启发价值，合在一起算估整个结点的价值，考虑到八数码问题的特点，在本实验中使用A*算法求解。A*搜索是一种效的搜索算法，它把到达节点的耗散g(n)和从该节点到目标节点的消耗h(n)结合起来对节点进行评价：f(n)=g(n)+h(n)。当h(n)是可采纳时，使用Tree-Search的A*算法将是最优的。2.2算法伪代码算法的功能：产生8数码问题的解(由初始状态到达目标状态的过程）输入：初始状态，目标状态输出：从初始状态到目标状态的一系列过程算法描述：Begin：读入初始状态和目标状态，并计算初始状态评价函数值f；根据初始状态和目标状态，判断问题是否可解；If(问题可解)把初始状态假如open表中；While（未找到解&&状态表非空）①在open表中找到评价值最小的节点，作为当前结点；②判断当前结点状态和目标状态是否一致，若一致，跳出循环；否则跳转到③；③对当前结点，分别按照上、下、左、右方向移动空格位置来扩展新的状态结点，并计算新扩展结点的评价值f并记录其父节点；④对于新扩展的状态结点，判断其是否重复，若不重复，把其加入到open表中；⑤把当前结点从open表中移除；EndwhileEndif输出结果；End算法流程如下：三、算法实现3.1实验环境与问题规模实验环境：硬件环境：PC机。软件环境：WindowsXP;VC++6.0。问题规模：对于任一给定可解初始状态，状态空间有9!/2=181440个状态；当采用不在位棋子数作为启发函数时，深度超过20时，算法求解速度缓慢；3.2数据结构是目标节点是o开始读入棋局初始状态是否可解在open表中找到评价值最小的节点，作为当前结点初始状态加入open表扩展新状态，把不重复的新状态加入open表中当前结点从open表移除输出结果结束否o否o是ostaticinttarget[9]={1,2,3,8,0,4,7,6,5};全局静态变量，表示目标状态classeight_num{private:intnum[9];定义八数码的初始状态intnot_in_position_num;定义不在正确位置八数码的个数intdeapth;定义了搜索的深度inteva_function;评价函数的值，每次选取最小的进行扩展public:eight_num*parent;指向节点的父节点eight_num*leaf_next;指向open表的下一个节点eight_num*leaf_pre;指向open表的前一个节点初始状态的构造函数eight_num(intinit_num[9]);eight_num(intnum1,intnum2,intnum3,intnum4,intnum5,intnum6,intnum7,intnum8,intnum9){}eight_num(void){}计算启发函数g(n)的值voideight_num::cul_para(void){}显示当前节点的状态voideight_num::show(){}复制当前节点状态到一个另数组中voideight_num::get_numbers_to(intother_num[9]){}设置当前节点状态(欲设置的状态记录的other数组中)voideight_num::set_num(intother_num[9]){}eight_num&eight_num::operator=(eight_num&another_8num){}eight_num&eight_num::operator=(intother_num[9]){}inteight_num::operator==(eight_num&another_8num){}inteight_num::operator==(intother_num[9]){}空格向上移intmove_up(intnum[9]){}空格向下移intmove_down(intnum[9]){}空格向左移intmove_left(intnum[9]){}空格向右移intmove_right(intnum[9]){}判断可否解出inticansolve(intnum[9],inttarget[9]){}判断有无重复intexisted(intnum[9],eight_num*where){}寻找估价函数最小的叶子节点eight_num*find_OK_leaf(eight_num*start){}}3.3实验结果h:启发函数（不在位将牌数）初始状态目标状态是否有解启发函数用时步数321804765123804765否h--104273856123804765是h2875ms21103824765123804765是h0ms13.4系统中间及最终输出结果（要求有屏幕显示）目标状态默认为123804765.a)初始状态是321804765，用h作为启发函数结果都如下：b)初始状态是104273856，用h作为启发函数结果都如下：中间略b)初始状态是103824765，用h作为启发函数结果都如下：四、参考文献[1]ArtificialIntelligence——AModernApproach.StuartRussell,PeterNorvig.人民邮电出版社,2004[2]ArtificialIntelligence,RobCallan.电子工业出版社,2004附录—源代码及其注释#includestdafx.h#includeiostream.h#includetime.h#includestdio.h#includedos.h#includeconio.hstaticinttarget[9]={1,2,3,8,0,4,7,6,5};//classdefinitionclasseight_num{private:intnum[9];intnot_in_position_num;intdeapth;inteva_function;public:eight_num*parent;eight_num*leaf_next;eight_num*leaf_pre;eight_num(intinit_num[9]);eight_num(intnum1,intnum2,intnum3,intnum4,intnum5,intnum6,intnum7,intnum8,intnum9){num[0]=num1;