基于八数码问题的搜索算法对比研究_热西旦木·吐尔洪太.pdf

本期推荐本栏目责任编辑：谢媛媛Computer Knowledge and Technology电脑知识与技术第19卷第1期(2023年1月）E-mail：http：/Tel：+86-551-65690963 65690964ISSN 1009-3044Computer Knowledge and Technology电脑知识与技术Vol.19,No.1,January2023基于八数码问题的搜索算法对比研究热西旦木 吐尔洪太，王慧玲（伊犁师范大学 网络安全与信息技术学院，新疆 伊犁835000)摘要：文章以八数码问题为例，对比两种搜索算法宽度优先算法和A*算法的性能。在同一初始结点和目标结点的情况下对两种算法所用步骤、时间和节点数进行比较，通过具体的实验数据分析，进一步验证各算法的性能。关键词：宽度优先算法；A*算法；八数码问题中图分类号：TP18文献标识码：A文章编号：1009-3044(2023)01-0001-03开放科学（资源服务）标识码(OSID)：问题求解是人工智能的核心问题之一，但因所需求解对象多数为难以获取全部信息的非结构化或结构不良的问题，故而通常无法以既有算法来求解。从问题实际出发，持续寻求可用知识以构造出最小代价的推理路线，最终解决问题的过程被称为搜索1。其中盲目搜索和启发式搜索在人工智能领域被广泛使用。前者是以事先预定的控制策略为依据进行搜索，其控制策略不会因搜索过程中所产生的“中间信息”而改变。后者则通过向搜索过程注入与所求问题相关且具有启发性的信息的方式，持续地将搜索过程引向有望之途，最终获致最优解。本文采用对比实验的思路，即对于同一八数码问题，分别运用属于盲目搜索的宽度优先算法和属于启发式搜索的A*算法进行解决，而后对比验证盲目和启发式两种搜索算法的性能。1算法描述1.1宽度优先搜索算法宽度优先搜索算法(Breadth-FirstSearch，BFS)是一种先生成的节点先扩展的策略。其搜索过程是：从初始节点S0开始逐层向下扩展，在第n层节点还没有全部搜索完之前，不进入第n+1层节点的搜索2。图1树状图模型说明BFS算法的工作过程及原理。图1树状图模型1)将初始节点 S0放入队列 queue 中，标记为已遍历；2)从队列中取出队列头的节点S0，找出与节点S0邻接的节点 S1S2S3，放入队列 queue 中并标记为已遍历；3)从queue中取出队列头的节点S1，找出与节点S1邻接的节点S0S4S5，由于S0已遍历，故排除；标记S4S5为已遍历，然后放入queue中；4)从queue中取出队列头的节点S2，找出与S2邻接的节点S0S6S7，由于S0已遍历，排除；标记S6S7为已遍历，然后放入queue中；5)沿该规律继续往下，一直到从queue中取出队列头的节点S8，找出与节点S8邻接的节点S3，而S3属于已遍历节点，不作下一步操作；6)此时队伍为空，BFS遍历结束。1.2A*算法A*算法由Stanford研究院的PeterHart等人于1968年发表，是目前被广泛使用的搜索方法3。A*算法是以A算法为基础的启发式搜索方法。A算法以估计函数f(n)=g(n)+h(n)为依据，赋予诸待扩展节点以顺序，进而择取其中估价值最小者加以拓展。其中f(n)为由S0（初始节点）出发，经过n（约束节点），最终到达Sg（目标节点）的所有可行路径中代价最小者的估计值4；其中g(n)为由S0出发抵达n所付出的实际代价；其中h(n)为由n出发，以最优路径抵达Sg的估价代价。A*算法的估价函数用f(n)=g(n)+h(n)表达，其中g(n)和h(n)是对应于g(n)和h(n)的最小代价，由于f(n)不能预先知道，可以在A算法的基础上计算收稿日期：2022-10-08基金项目：伊犁师范大学博士科研启动基金项目：基于深度学习的遥感影像分类方法研究（项目编号：2020YSBS005)作者简介：热西旦木 吐尔洪太(1980)，女（维吾尔族），新疆伊犁人，讲师，博士，主要研究方向为机器学习、自然语言处理；王慧玲(1981)，女，新疆伊犁人，副教授，硕士，主要研究方向为图像处理。1DOI:10.14004/ki.ckt.2023.0054本栏目责任编辑：谢媛媛本期推荐Computer Knowledge and Technology电脑知识与技术第19卷第1期(2023年1月）得到。A*算法要满足以下两个条件：其一，g(n)表示对最小代价g(n)的估计，且g(n)0，其二，h(n)表示最小代价h(n)的下界，即是说对任意节点而言，均有h(n)=0，其满足A*算法的第一个条件，h(n)=w(n)为“不在位”的数码个数，可以得出至少要移动w(n)步才能达到目标，显然有w(n)=h(n)，满足A*算法的第二个限制条件。搜索过程从所有待遍历节点中选择估值最小的一个节点进行扩展。图4 八数码问题使用A*算法的搜索图2)A*算法估价函数的改进对于八数码问题，如果把不在位的数码个数作为估价函数，不足以描述该节点到目标节点的路径长度，因此本文对A*算法的估价函数进一步改进，取另一种启发式函数f(n)=d(n)+p(n)来描述两个状态节点之间的差距，其中d(n)为每一个节点的深度，跟上例一致，p(n)定义为每一个数码与其目标位置之间距离（不考虑夹在其间的数码）的总和，可以断定至少要移动p(n)步才能到达目标节点，因此有p(n)=h(n)，即满足A*算法的第二个限制条件。使用改进了的估价函数对图4中的八数码问题进行遍历，能够取得更好的搜索效果。其搜索过程所得到的搜索树如图5所示。图5 八数码问题使用改进A*算法的搜索图3)两种算法所耗步骤与时间比较选择不同的初始节点，分别采用BFS算法、A*算法和改进后的A*算法进行遍历，求出达到目标节点的步数和搜索程序的运行时间。表1实验数据分析初始状态283164705203584716710862453361245087581260743382716045458032761BFS步骤5171820212223BFS时间(ms)683172727333034374342044489A*步骤5171820212223A*时间(ms)36785817302113246626422979改进A*算法时间(ms)15445289410011145120313783.2结果分析由图3和图4可知，尽管通过BFS能够找到问题的最优解，但该算法所产生的节点数将远超过A*算法。其原因在于，A*算法在搜索过程中可以忽略一部分节点的遍历，而BFS则不能。特别是当某一八数码问题的初始状态与目标状态差距较大时，BFS将产生更多的无用节点。从表1可知，从同一个初始节点出发，分别采用BFS与A*算法，两者到达目标节点所用的步数数目相同，但所耗的时间却不一样，由于A*算法访问的节点数较少，所耗时间会更短。虽然BFS算法能够保证在搜索树中找到一条通向目标节点的最短路径，但其时间和空间复杂度都比较高。因此，对于复杂的搜索问题A*算法更具有针对性，可以缩小搜索范围，并提高搜索效率。从图5可以看出对A*算法估价函数进行优化后遍历的节点数为11个，比改进之前的遍历节点减少了2个，虽然空间利用率与A*算法差距不大，但从表1可以看出改进后的A*算法时间复杂度更低。因此A*算法如果针对具体的问题能选择最为合理的估价函数，可以进一步提高搜索的效率。参考文献：1 王万森.人工智能原理及其应用M.2版.北京:电子工业出版社,2007.2 曹刚.基于迷宫问题宽度优先捜索算法解析J.华夏教师,2018(34):29-30.3 熊伟,张仁平,刘奇韬,等.A*算法及其在地理信息系统中的应用J.计算机系统应用,2007,16(4):14-174 杨璐,汪博涵,张雪洁.基于A*算法的AGV路径规划研究J.公路与汽运,2014(4):47-49.5 陈岩,李涛,印明昂.基于改进A*算法的管路自动敷设研究J.兵器装备工程学报,2018,39(10):91-95,104.【通联编辑：代影】3