基于八数码问题的搜索算法对比研究

热西旦木·吐尔洪太　王慧玲

摘要：文章以八数码问题为例，对比两种搜索算法——宽度优先算法和A*算法的性能。在同一初始结点和目标结点的情况下对两种算法所用步骤、时间和节点数进行比较，通过具体的实验数据分析，进一步验证各算法的性能。

关键词：宽度优先算法；A*算法；八数码问题

中图分类号：TP18      文献标识码：A

文章编号：1009-3044（2023）01-0001-03

问题求解是人工智能的核心问题之一，但因所需求解对象多数为难以获取全部信息的非结构化或结构不良的问题，故而通常无法以既有算法来求解。从问题实际出发，持续寻求可用知识以构造出最小代价的推理路线，最终解决问题的过程被称为搜索[1]。其中盲目搜索和启发式搜索在人工智能领域被广泛使用。前者是以事先预定的控制策略为依据进行搜索，其控制策略不会因搜索过程中所产生的“中间信息”而改变。后者则通过向搜索过程注入与所求问题相关且具有启发性的信息的方式，持续地将搜索过程引向有望之途，最终获致最优解。本文采用对比实验的思路，即对于同一八数码问题，分别运用属于盲目搜索的宽度优先算法和属于启发式搜索的A*算法进行解决，而后对比验证盲目和启发式两种搜索算法的性能。

1算法描述

1.1宽度优先搜索算法

宽度优先搜索算法（Breadth-FirstSearch，BFS）是一种先生成的节点先扩展的策略。其搜索过程是：从初始节点S0开始逐层向下扩展，在第n层节点还没有全部搜索完之前，不进入第n+1层节点的搜索[2]。图1树状图模型说明BFS算法的工作过程及原理。

1）将初始节点S₀放入队列queue中，标记为已遍历；

2）从队列中取出队列头的节点S₀，找出与节点S₀邻接的节点S₁S₂S₃，放入队列queue中并标记为已遍历；

3）从queue中取出队列头的节点S₁，找出与节点S₁邻接的节点S₀S₄S₅，由于S₀已遍历，故排除；标记S₄S₅为已遍历，然后放入queue中；

4）从queue中取出队列头的节点S₂，找出与S₂邻接的节点S₀S₆S₇，由于S₀已遍历，排除；标记S₆S₇为已遍历，然后放入queue中；

5）沿该规律继续往下，一直到从queue中取出队列头的节点S₈，找出与节点S₈邻接的节点S₃，而S₃属于已遍历节点，不作下一步操作；

6）此时队伍为空，BFS遍历结束。

1.2A*算法

A*算法由Stanford研究院的PeterHart等人于1968年发表，是目前被广泛使用的搜索方法[3]。A*算法是以A算法为基础的启发式搜索方法。A算法以估计函数f（n）=g（n）+h（n）为依据，赋予诸待扩展节点以顺序，进而择取其中估价值最小者加以拓展。其中ｆ（n）为由S₀（初始节点）出发，经过n（约束节点），最终到达S_g（目标节点）的所有可行路径中代价最小者的估计值[4]；其中g（n）为由S₀出发抵达n所付出的实际代价；其中h（n）为由n出发，以最优路径抵达S_g的估价代价。A*算法的估价函数用f（n）=g（n）+h（n）表达，其中g（n）和h（n）是对应于g（n）和h（n）的最小代价，由于f（n）不能预先知道，可以在A算法的基础上计算得到。A*算法要满足以下两个条件：

其一，g（n）表示对最小代价g（n）的估计，且g（n）>0，

其二，h（n）表示最小代价h（n）的下界，即是说对任意节点而言，均有h（n）<=h（n）。

A*算法中需要建立两个数据结构。其一是用以存放新生成的、尚未得以扩展的节点的Open表（亦称未扩展节点表），其二是用以存放已然或即将扩展的节点的Closed表（亦称已扩展节点表）[5]。

A*算法的工作过程及原理：

1） Open表起初只存放初始节点S₀；

2） 查看Open表为空与否，若为空，则意味着问题無解，搜索失败；

3） 将Open表中首个节点放入Closed表中，并将其标记为已遍历节点n；

4） 对已遍历节点n进行检验，若恰为目标节点，则意味着找到了问题的解，搜索成功结束；

5） 若节点n无法扩展，则需转至第二步；

6） 若节点n能够扩展，则实施拓展以获得其子节点n_i（i=1，2，...），进而对n_i的估价值f（ni）（i=1，2，...）进行计算，对从子节点到父节点的指针进行设置，而后将其放入Open表中；

7） 将Open表中的所有节点按估价函数值由小到大的顺序加以重排；

8） 转至第二步。

2八数码问题描述

八数码问题，也称九宫格问题，系人工智能状态搜索问题中的典型。其规则可表述为：在一个纵横各三路的九宫格棋盘上已摆入八枚棋子，其中每枚棋子以数字1至8为标号，且互不重复。棋盘上尚留有一空格，与其四邻的棋子皆可以出入空格。对此问题，图2（a）给出初始状态，图2（b）则给出目标状态。从初始状态到目标状态过程中的每次移棋皆应视为空格四邻的一个棋子（数码）出入空格。

为了便于描述，每一个状态用数列来表示，如图2中初始状态表示为S₀=283164705，目标状态表示为S_g=123804765或123456780。

八数码问题的可解性。事实上只有部分八数码问题是有解的，一个八数码问题有解的前提是其初始状态数列的逆序数与目标状态数列的逆序数在奇偶性上一致。具体而言，在由某一八数码问题引出的数列中任意选取一对数，若这两个数的序位关系与大小关系相反（序位居先者较大，而序位居后者较小），便可称这两个数为一个逆序（空格对应的数字0不纳入考虑），而该数列中逆序的总数即是逆序数。以图2为例，其初始状态数列S₀=283164705中的数对83、31、64、75等均是逆序。通过计算、对比可知，其初始状态数列S₀的逆序数为11（1+3+1+2+1+3），而其目标状态数列S_g=123804765的逆序数为7（1+1+2+3），两者皆是奇数，奇偶性一致。故而图2所示的八数码问题有解。

当图2中的空格向左右移动时，逆序数的大小不会随之改变；当空格上下移动时，逆序数可能会随之改变，但变动幅度仅可能为±2，其奇偶性仍保持不变。由此可知，有解八数码问题中的空格移动所得到的数字排列方式并不影响其是否有解。

3两种算法在八数码问题上的性能对比

3.1问题描述

实验给出几个用来进行效率对比的变量：节点数：搜索过程中所遍历的节点总数；估价函数：用来估计节点重要性的函数；时间：搜索程序的运行时间（单位为毫秒，ms），每种搜索过程执行3次，取其平均数作为最终结果时间；步数：从初始节点到目标节点的路径长度。实验结果如表1和图3到图5所示。

1）两种算法节点数比较

BFS算法中先生成的节点排在队列的前面，后生成的节点排在队列后面，每次取出队列头部的节点进行遍历。

A*算法中设估价函数f（n）=d（n）+w（n），其中g（n）=d（n），为每一个节点的深度，由于d（n）>=0，其满足A*算法的第一个条件，h（n）=w（n）为“不在位”的数码个数，可以得出至少要移动w（n）步才能达到目标，显然有w（n）<=h（n），满足A*算法的第二个限制条件。搜索过程从所有待遍历节点中选择估值最小的一个节点进行扩展。

2）A*算法估价函数的改进

对于八数码问题，如果把不在位的数码个数作为估价函数，不足以描述该节点到目标节点的路径长度，因此本文对A*算法的估价函数进一步改进，取另一种启发式函数f（n）=d（n）+p（n）来描述两个状态节点之间的差距，其中d（n）为每一个节点的深度，跟上例一致，p（n）定义为每一个数码与其目标位置之间距离（不考虑夹在其间的数码）的总和，可以断定至少要移动p（n）步才能到达目标节点，因此有p（n）<=h（n），即满足A*算法的第二个限制条件。使用改进了的估价函数对图4中的八数码问题进行遍历，能够取得更好的搜索效果。其搜索过程所得到的搜索树如图5所示。

3）两种算法所耗步骤与时间比较

选择不同的初始节点，分别采用BFS算法、A*算法和改进后的A*算法进行遍历，求出达到目标节点的步数和搜索程序的运行时间。

3.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-17．

[4] 杨璐，汪博涵，张雪洁.基于A*算法的AGV路径规划研究[J].公路与汽运，2014（4）：47-49.

[5] 陈岩，李涛，印明昂.基于改进A*算法的管路自动敷设研究[J].兵器装备工程学报，2018，39（10）：91-95，104.

【通联编辑：代影】