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

1、 基于A*算法求解八数码问题班级：20110616学号：2011061618姓名：唐宗林摘要：利用人工智能中的经典启发式搜索算法求解八数码问题，在启发式搜索算法上对A*算法的定义进行了解释，详细的描述了启发式A*搜索算法，并将之运用至解决八数码问题，对八数码问题求解过程进行了详细解释，取得了预期的搜索解，达到了本实验课程的预期目的。关键词：人工智能；启发式搜索算法；A*算法；八数码问题本组成员：唐宗林，陶涛，汤芦山本人分工：主要承担A*算法中启发函数的设计、八数码问题解存在问题判断等工作。1引言在信息社会中，人们越来越依赖于搜索技术来获取有用的信息，搜索是人工智能中的一个基本问题，是推理不可分

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

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

4、空间。其中，状态空间中的任一种状态都可以作为初始状态。后继函数：通过移动空格（上、下、左、右）和周围的任一棋子一次，到达新的合法状态。目标测试：比较当前状态和目标状态的格局是否一致。路径消耗：每一步的耗散值为1，因此整个路径的耗散值是从起始状态到目标状态的棋子移动的总步数。2.2八数码解存在判断在对八数码问题进行正式求解前，我们会首先对八数码是否有解作出判断。我们对一个任意的棋局状态p=clc2c3c4c5c6c7c8进行分析：引理1：如果交换任何两个相邻的棋子，那么棋子数列的逆序数将发生奇偶性互变(奇偶性互变是指由奇数变为偶数，或由偶数变为奇数，下同)。引理2：如果棋子数列经过n次相邻棋子交

5、换后，若n为偶数，则数列逆序数奇偶性不变；若n为奇数，则数列逆序数将发生奇偶性互变。引理3：在满足上述约定的八数码问题中，空格与相邻棋子的交换不会改变棋局中棋子数列的逆序数的奇偶性。定理l：当初始状态棋局的棋子数列的逆序数是奇数时，八数码问题无解；当初始状态棋局的棋子数列的逆序数是偶数时，八数码问题有解。2.3启发式搜索启发式搜索算法的基本思想是：定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。2.4启发信息启发性信息是指那种与具体问题求解过程有关的，并可指导搜索过程朝着最有希望的方向前进的控制信息。有余下三种启发性信息：有效的帮助确定扩展节点的信息；有效的帮助决定

6、那些后记节点被生成的信息；能决定在扩展一个节点时那些节点应从搜索树上删除的信息；估价函数f*(n)=g*(n)+h*(n)上式中g*(n)表示从初始节点s到当前节点n的最短路径的耗散值；h*(n)表示从当前节点n到目标节点g的最短路径的实际耗散值，f*(n)表示从初始节点s经过n到目标节点g的最短路径的耗散值。A*算法如果我们分别以g(n)及h(n)代替g*(n)及h*(n)，其中g(n)是对g*的一个合理估计，它们可能不相等：g(n)=g*(n)只有当发现了到状态n的最短路径时它们才是相等的。同理，以对到目标状态的最小代价的启发式估计h(n)代替h*(n)，如果评估函数满足h(n)=h*(n

7、)，我们把它称为A*算法。信息度更高的启发是更好的启发，A*算法的信息度越高，要得到最优解而需要展开的空间就越小。但采用高信息度的启发所需的计算量可能会增大，以至于抵消了搜索数量降低而带来的优势。算法描述算法的功能：产生8数码问题的解(由初始状态到达目标状态的过程)输入：初始状态，目标状态输出：从初始状态到目标状态的一系列过程算法描述：Begin：读入初始状态和目标状态，并计算初始状态评价函数值f;根据初始状态和目标状态，判断问题是否可解；If（问题可解）把初始状态假如open表中；While（未找到解&状态表非空）在open表中找到评价值最小的节点，作为当前结点；判断当前结点状态和目标状态是

8、否一致，若一致，跳出循环；否则跳转到；对当前结点，分别按照上、下、左、右方向移动空格位置来扩展新的状态结点，并计算新扩展结点的评价值f并记录其父节点；对于新扩展的状态结点，判断其是否重复，若不重复，把其加入到open表中；把当前结点从open表中移除；EndwhileEndif输出结果；End2.8算法流程图算法流程图如下图2.8所示：曰否否曰是否可解结束是否是目标节点丄开始在Open表中找到评价值最小的节点，作为当前节点扩展新状态，把不重复的新状态加入Open表中初始状态加入Open表当前节点从Open表移除读入棋局初始状态输出结果图2.8算法流程图系统实现3.1启发式函数设计3.1.1启发

9、函数1启发函数1数出每个状态与目标状态相比错位的牌数错位牌数最少的状态可能最接近预期目标，所以它是接下来要分析的最佳状态。缺点是没有使用从棋盘上得到的全部信息。因为它没有把牌要移动的距离纳入到考虑之中关键代码：intcamp(stringstr1,stringstr2)intsum=0;for(inti=0;i9;i+)if(str1i!=str2i)sum+;coutsumps;strings=s0;inth=0;inttemp，tempg;for(inti=0;i=8;i+)if(si=0)continue;/。的距离已经包含在其他数字的移动过程中，所以应该舍去temp=strchr(ps

10、，si)-ps;tempg=strchr(psg，si)-psg;h+=abs(temp/3-tempg/3)+abs(temp%3-tempg%3);returnh;3.1.3启发函数3启发函数3：对每一个相互颠倒(两张相邻的牌要满足目标位置必须交换顺序)乘以一个小的数字(例如2)但这种启发函数的问题是如果当前状态如果不存在直接颠倒，则不能对当前状态做出正确的评估。关键代码：intcamp(stringstrl，stringstr2)intsum=0;for(inti=0;i9;i+)if(str1i=0)continue;for(intj=0;j9;j+)if(str1i=str2j&st

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

12、;i=8;i+)if(s0i=0)continue;for(j=0;ji;j+)if(s0j=0)continue;if(s0j-0)(s0i-0)i0+;for(i=0;i=8;i+)if(sgi=0)continue;for(j=0;ji;j+)if(sgj=0)continue;if(sgj-0)(sgi-0)ig+;couti0igendl;return(i0-ig)%2=0);实验或测试结果4.1有解状况分析有解状况分析如下图4.1所示，目标状态默认为123804765，初始状态为283164750。觇別斷戎恋:23B2BM31&4750图4.1有解状态分析4.2无解状态分析无解状况

13、分析如下图4.2所示，目标状态默认为123804765,初始状态为823164705。|31&4706汗蛉直趟拼團图4.2无解状态分析5结论通过本实验中对八数码问题的解决，我加深了对启发式搜索算法的理解与运用，更加深刻的理解了A*算法的实质，同时加深了我对人工智能课程的兴趣。在本课程实验中我主要负责A*算法中启发函数的设计及八数码问题解存在判断等工作，通过这些内容我深深理解了实践的重要性，课本中学到的知识只有通过实际问题的解决才能真正被掌握与吸收。在完成实验的过程中，我参考了许多参考资料，认真的学习了启发函数的设计原理，同时比较了常用几种启发函数的优缺点，加深了理解。在实验中的不足之处是由于时间原因没有对这几种启发函数进行实际效率比对，只是在理论上进行了比较。通过本课程提高了我的解决实际问题的自信心，但同时也让我更加深刻的认识