基于A算法求解八数码问题-哈尔滨工程大学

1、基于A算法求解八数码问题-哈 尔滨工程大学作者: 日期:人工智能课程项目报告基于A*算法求解八数码问题班级：20110616学号：2011061618姓名：唐宗林摘要：利用人工智能中的经典启发式搜索算法求解八数码问题，在启发式搜索算法上对A*算法的左 义进行了解释，详细的描述了启发式A*搜索算法，并将之运用至解决八数码问题，对八数码问题求 解过程进行了详细解释，取得了预期的搜索解，达到了本实验课程的预期目的。关键词：人工智能：启发式搜索算法：A*算法；八数码问题 本组成员：唐宗林，陶涛，汤芦山本人分工：主要承担A*算法中启发函数的设讣、八数码问题解存在问题判断等工作。1引言在信息社会中，人们越

2、来越依赖于搜索技术来获取有用的信息，搜索是人工智能中的一个基本 问题，是推理不可分割的一部分，它直接关系到智能系统的性能及运行效率。通常搜索策略的主要 任务是确泄如何选取规则的方式。一般有两种方式：一种是不考虑所给问题所具有的的特左知识系 统根据事先确左好的某种固左排序，一次调用规则或随机调用规则，这实际上是盲目搜索的策略； 另一种是考虑问题领域可应用的知识，动态的确泄规则的排序，优先调用较合适的规则排序，这就 是通常所称为的启发式搜索策略。启发式搜索是利用问题所拥有的启发式信息来引导搜索，以达到 减少搜索范围，降低问题复杂度的目的。在本课程实验中我们以八数码问题为背景，运用启发式搜索算法来达

3、到求解目的。通过解决八 数码问题来加深对A*算法的理解及运用，以更好地将课堂所学知识运用到实际问题的解决之中。在 实验中我的任务主要是A*算法中启发函数的设计、八数码问题解存在问题判断等工作，所以接下来 的叙述也将围绕这几项工作来展开。2算法原理与系统设计2.1八数码问题八数码游戏（八数码问题）描述为：在3x3组成的九宫格棋盘上，摆有八个将牌，每一个将牌 都刻有1-8八个数码中的某一个数码。棋盘中留有一个空格，允许其周用的某一个将牌向空格移动, 这样通过移动将牌就可以不断改变将牌的布局。这种游戏求解的问题是：给左一种初始的将牌布局 或结构（称初始状态）和一个目标的布局（称目标状态），问如何移动

4、将牌，实现从初始状态到目标 状态的转变。初始状态：8个数字将牌和空格在九宫格棋盘上的所有格局组成了问题的状态空间。其中，状态空间中的 任一种状态都可以作为初始状态。后继函数：通过移动空格（上、下、左、右）和周围的任一棋子一次，到达新的合法状态。目标测试：比较当前状态和目标状态的格局是否一致。路径消耗：每一步的耗散值为1，因此整个路径的耗散值是从起始状态到目标状态的棋子移动的总步数。人工智能课程项目报告2.2八数码解存在判断在对八数码问题进行正式求解前，我们会首先对八数码是否有解作出判断。我们对一个任意的棋局状态p=c 1 c2c3c4c5c6c7c8进行分析:引理1：如果交换任何两个相邻的棋子

5、，那么棋子数列的逆序数将发生奇偶性互变(奇偶性 互变是指由奇数变为偶数，或由偶数变为奇数，下同)。引理2：如果棋子数列经过n次相邻棋子交换后，若n为偶数，则数列逆序数奇偶性不变： 若n为奇数，则数列逆序数将发生奇偶性互变。引理3：在满足上述约左的八数码问题中，空格与相邻棋子的交换不会改变棋局中棋子数列的逆序数的奇偶性。定理1 :(1) 当初始状态棋局的棋子数列的逆序数是奇数时，八数码问题无解：(2) 当初始状态棋局的棋子数列的逆序数是偶数时，八数码问题有解。23启发式搜索启发式搜索算法的基本思想是：左义一个评价函数f，对当前的搜索状态进行评估，找出一个最 有希望的节点来扩展。24启发信息启发性

6、信息是指那种与具体问题求解过程有关的，并可指导搜索过程朝着最有希望的方向前进 的控制信息。有余下三种启发性信息：有效的帮助确定扩展节点的信息；有效的帮助决定那些后记节点被生成的信息；能决定在扩展一个节点时那些节点应从搜索树上删除的信息；2.5估价函数f*(n)=g*(n)+h*(n)上式中g歆n)表示从初始节点s到当前节点n的最短路径的耗散值；h*(n)表示从当前节点n到目 标节点g的最短路径的实际耗散值，f*(n)表示从初始节点s经过n到目标节点g的最短路径的耗散 值。2.6 A*算法如果我们分别以g(n)及h(n)代替g*(n)及h*(n)，其中g(n)是对g*的一个合理估计，它们可能不

7、相等：g(n)>= g*(n)只有当发现了到状态n的最短路径时它们才是相等的。同理，以对到目标状态的 最小代价的启发式估计h(n)代替h*(n),如果评估函数满足h(n)<=h*(n)，我们把它称为A*算法。信息度更髙的启发是更好的启发，A*算法的信息度越髙，要得到最优解而需要展开的空间就越 小。但采用高信息度的启发所需的il算量可能会增大，以至于抵消了搜索数量降低而带来的优势。2.7算法描述算法的功能：产生8数码问题的解(由初始状态到达目标状态的过程)输入：初始状态，目标状态输出：从初始状态到目标状态的一系列过程算法描述：Begin：读入初始状态和盲标状态，并计算初始状态评价函数

8、值f:根据初始状态和目标状态，判断问题是否可解：If（问题可解）把初始状态假如open表中：While （未找到解&&状态表非空） 在open表中找到评价值最小的节点，作为当前结点； 判断当前结点状态和目标状态是否一致，若一致，跳出循环：否则跳转到： 对当前结点，分别按照上、下、左、右方向移动空格位巻来扩展新的状态结点，并计算新扩 展结点的评价值f并记录其父节点； 对于新扩展的状态结点，判断英是否重复，若不重复，把其加入到open表中： 把当前结点从open表中移除：End whileEnd if输出结果：End2.8算法流程图算法流程图如下图2.8所示：图2.8算法流程图3系

9、统实现3.1启发式函数设计3丄1启发函数1 启发函数1：数出每个状态与目标状态相比错位的牌数错位牌数最少的状态可能最接近预期目标，所以它是接下来要分析的最佳状态。 缺点是没有使用从棋盘上得到的全部信息。因为它没有把牌要移动的距离纳入到考虑之中。关键代码：int canip( string strLstring str2)int sum=O:for(int i=0;i<9;i+)if(strli!=str2i)sum+;cout«sum«endl;3.1.2启发函数2 启发函数2：对错位的牌要移动的距离进行求和。为了到达目标位置，每张牌必须要移动的每个方格算做一个单位。

10、不足之处是没有颠倒牌的难度，也就是说如果两张牌是相互相邻的，要把它们放到适当的位置 移动的次数远不止两次，因为每张牌必须相互绕来绕去。关键代码：intgeth(pS ml) /求状态ml的h值，h是除0外尚未到达目的的数字离目的距离之和，(此处的距 离是指行差加列差的和)char* ps=ml->ps;string s=sO;int h=0;int tempjempg;for(int i=0;i<=8;i+)if(si='O') continuc：/0的距离已经包含在其他数字的移动过程中，所以应该舍去 temp=strchr(ps,si)-ps;tenipg=str

11、chr(psg,si)-psg;h+=abs(tcmp/3-tempg/3)+abs(temp%3-tempg%3);return h:313启发函数3 启发函数3：对每一个相互颠倒(两张相邻的牌要满足目标位置必须交换顺序)乘以一个 小的数字(例如2)但这种启发函数的问题是如果当前状态如果不存在直接颠倒，则不能对当前状态做出正确 的评估。关键代码：int canip(string strLstring str2)int sum=O:for(int i=0;i<9;i+)if(strli=O,) continue;for(int j=O;j<9;j+)if(strli=str2j &

12、amp;&sti2j=str2i)sum+; cout«sum/2«endl;3.1.4启发函数4 启发函数4：把错位牌的距离与直接颠倒数的二倍相加。这样就综合了启发函数2和启发函数3的优点，克服了单纯颠倒启发的不足之处，加强了评估 函数的准确性。32八数码问题解存在判断bool cansolve(string sO.string sg)检验用户输入的初始状态是否有解/*当初始状态的逆序数和目标状态的逆序数的奇偶性相同时，问题有解：否则问题无解。逆序数建义如下：把三行数展开排成一行,并且丢弃数字0不计入其中，所有的数之前比该数小的数字的个数之和是该状态的逆序数。*/

13、int iOJgjj;iO=ig=O;for( i=0;i<=8;i+)if (sOi=V) continue;for(j=0:j<i:j+)if (sO(j=O') continue;if(s0j-O)<(s0iW)i0+;for( i=0;i<=8;i+)if (sgi=fOr) continue;for( j=O:j<i:j+)if (sgj=,O,) continue;if(sgj-'O')<(sgi-'O')ig卄;cout«iO«, ,«ig«endl;return(

14、i0-ig)%2=0);4实验或测试结果4.1有解状况分析有解状况分析如下图4.1所示，目标状态默认为123804765,初始状态为283164750。图4.1有解状态分析4.2无解状态分析无解状况分析如下图4.2所示，目标状态默认为123804765,初始状态为823164705。L.2!囂态无解请输入g位的初蜡迖査序列c由8尢个頼孝 誠）|82S164705图4.2无解状态分析5结论通过本实验中对八数码问题的解决，我加深了对启发式搜索算法的理解与运用，更加深刻的理 解了 A*算法的实质，同时加深了我对人工智能课程的兴趣。在本课程实验中我主要负责A*算法中启发函数的设计及八数码问题解存在判断等工作，通过这 些内容我深深理解了实践的重要性，课本中学到的知识只有通过实际问题的解决才能貞正被掌握与 吸收。在完成实验的过程中，我参考了许多参考资料，认真的学习了启发函数的设汁原理，同时比 较了常用几种启发函数的优缺点，加深了理解。在实验中的不足之处是由于时间原因没有对这几种 启发函数进行实际效率比对，只是在理论上进行了比较。通过本课程提高了我的解决实际问题的自信心，但同时