本期推荐本栏目责任编辑：谢媛媛ComputerKnowledgeandTechnology电脑知识与技术第19卷第1期(2023年1月）E-mail：software@dnzs.comhttp：//www.dnzs.net.cnTel：+86-551-6569096365690964ISSN1009-3044ComputerKnowledgeandTechnology电脑知识与技术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)沿该规律继续往下，一直到从que...
