一种基于A*算法与8数码问题的特征映射与估价方法

【摘要】    本文提出一种基于A*算法与8数码问题的特征映射与估价模型ENet，将神经网络的思想应用到估价函数中，使算法本身更具鲁棒性和高效性。同时，本文还将构筑了一个有关8数码问题的数据集ENumbers，并给出一种基于8数码问题的算法评价标准。实验显示，ENet方法相比其它经典方法更加有效，能够更加精确地拟合A*算法背景下的8数码问题，就皮尔逊相关系数这一精度指标对经典方法提升了約4.025%。

【关键词】    神经网络    启发式搜索    图搜索    8数码问题

引言：

A*算法[1]是在静态网络中求解最短路径问题下最有效的直接搜索方法之一。作为一种历史悠久而效率较高的人工智能方法，A*算法自提出以来，已经被广泛应用于诸如防反弹袭击[2]、机器人的自主无碰行动[3]、物流管理中的车辆问题[4-5]及类似的资源管理资源配置等路径规划与图搜索问题。

8数码问题是一种A*算法的经典应用场景与理论探索空间。所谓八数码问题起源于一种游戏：将分别标有数字0，1，2，3，…，8的八块正方形数码牌任意地放在一块3*3的数码盘上。规定0代表一个可以自由移动的空格，现在要求按照每次只能将与空格相邻的数码牌与空格交换的原则，将摆放完毕的数码盘样式（称初始状态）逐步摆成某种给定的数码盘样式（称目标状态）。如图1给出了一种8数码问题的常见形式。

一、相关工作

（一）A*算法流程

A*算法[1]是启发式搜索中的一个门类，所谓启发式搜索，与DFS和BFS这类盲目型搜索最大的不同，就在于当前搜索结点往下选择下一步结点时，可以通过一个启发函数来进行选择，选择代价最少的结点作为下一步搜索结点而跳转其上（遇到有一个以上代价最少的结点，不妨选距离当前搜索点最近一次展开的搜索点进行下一步搜索）。而A*算法得以从其它启发式搜索中脱颖而出的部分，就在于它的一个估值函数的设计上：

f（n）=g（n）+h（n）                                              （1）

其中f（n）是每个可能试探点的估值，它由两部分组成：一部分为g（n），它表示从起始搜索点到当前点的代价。另一部分h（n），它表示当前结点到目标结点的估值，h（n）设计的好坏，直接影响A*算法的效率。

（二）关于8数码问题经典的估价函数计算方法

在一般的A*算法8数码问题学习过程中，我们通常采用起始状态与目标状态之间的矩阵差分（matrix differences）来度量距离[9]。在衡量相对简单的矩阵差异时，矩阵差分法和曼哈顿距离法都拥有相当理想的实验效果。

然而，很容易发现的是，这两种方法在差异点分布较远的情况下，会给出明显错误的计算结果。这是因为空间位置的差异未必能够反应移动所需的步数，即使矩阵之间看上去只有细微的差别，实际计算的过程中也可能耗费大量的成本。

综上所述，以上经典计算方法虽然拥有在简单情况下适用的性质，然而面对一些特殊情况，它们反而更容易陷入误判的泥沼。因此，提出一种全新的距离衡量方法，有其必要性与进步性。

二、本文算法研究

（一）8数码问题数据集及其精度判定标准

首先，为了衡量不同方法在8数码问题上的效率和精度，我们构筑了一个有关8数码问题的数据集ENumbers。该数据集由3个文档文件组成，前两个文档文件各有10000行，分别表示初始状态与目标状态，共包含10000对8数码矩阵。第三个文档则存储状态间的最短距离。

（二）ENet特征映射分类模型

为了改善传统A*算法与8数码问题中广泛存在的估值函数误差大与鲁棒性不足等问题，我们利用BP神经网络搭建了ENet深度学习模型，通过多层感知机将原本仅3*3的输入特征图映射到1*59049维的高层次特征空间中。再利用降维操作，对高层次特征逐步进行细化分类，最终输出一个起始状态到目标状态距离的预测值。

实验发现，在实际应用于8数码问题时，将矩阵差分法与ENet输出结果结合起来，往往能够起到更优良的效果。在这种情况下，模型的最终输出结果可以被表示为：

output（x）=v*ENet（x）+difference（x）-0.5                         （2）

其中，v为ENet融合权重，ENet（x）表示ENet的模型输出，difference（x）表示输入数据使用矩阵差分法得到的输出值，为平衡二分类模型输出系数。

二、实验分析

本次实验数据集为ENumbers8数码问题数据集，随机选取起始状态与目标状态数据7000对进行训练，另有3000对数据按2：1比例随机划分为测试集和验证集，我们将在验证集上对实验结果进行评估和检测。

（一） 评价指标

其次，考虑到A*算法本身在实现过程中，因数据结构的不同和数据集大小的限制，我们使用皮尔森相关系数来度量模型预测的整体精度，其公式为：

（3）

在这种判断标准下，前述的两种方法精度为：

针对本文提出的A*算法数据集，我们分别对矩阵差分和曼哈顿距离法进行了皮尔逊相关系数测试，实验发现曼哈顿距离与实际标签之间的相关性较差，而矩阵差分与实际标签之间具有一定的相关性，但仍存在较大的改进空间。

（二）实验参数设置

本文的ENet模型使用pytorch架构实现，Block Loss采用二分类输出，实验采用二分类交叉熵损失函数，训练选用Adam优化器，设置初始学习率为5*10^-4，每20次训练后衰减一次，衰减权重为0.05.设置实验。输入数据为两个1*9数码问题序列。

（三）實验结果分析

对模型输出结果和矩阵差分法进行复合，其结果在验证集上进行评估，使用皮尔逊相关系数作为评价标准，可以得到如下图4的输出结果和点阵图。

五、结束语

A*算法作为一种经典的路径规划与图搜索算法，在民用领域与军用领域都有广泛应用。本文针对A*算法中能够特定表征知识的启发函数部分，融合先进的神经网络模型，就皮尔逊相关系数这一指标对矩阵差分方法提升了约4.025%。同时，本文还提出了关于8数码问题的数据集，更新了有关该问题背景下的判别指标。

作者单位：顾宇轩    安徽大学

参  考  文  献

[1] Hart P E ， MEMBER， IEEE， et al. A Formal Basis for the Heuristic Determination of Minimum Cost Paths[J]. IEEE Transactions on Systems Science and Cybernetics， 2007， 4（2）：100-107.

[2]楚孟慧， 吴姝瑶. 基于八数码问题的搜索算法的研究[J]. 电子制作， 2021（14）：3.

[3]刘建娟，薛礼啟，张会娟，刘忠璞. 融合改进A*与DWA算法的机器人动态路径规划[J]. 计算机工程与应用， 2021（73-81）.

[4]江洪，姜民.基于变步长A*与车身稳态转向模型的UGV路径规划[J].计算机系统应用，2021，30（10）：240-247.DOI：10.15888/j.cnki.csa.008142.

[5]冯来春， 梁华为， 杜明博，等. 基于A*引导域的RRT智能车辆路径规划算法[J]. 计算机系统应用， 2017， 26（8）：7.

[7]龙振海， 林泓. 8数码问题求解算法的改进与实现[J]. 中国高新技术企业， 2010（2）：3.

[8]陈万军， 梁敏， 于洪志. 人工智能中A*算法的改进及其在8数码问题中的应用[J]. 西北民族大学学报：自然科学版， 2003， 24（4）：4.

[9]张信一， 黎燕. 基于A^*算法的八数码问题的程序求解[J]. 现代计算机， 2003（5）：5.

[10]胡敏杰. A*算法的探讨及其对八数码问题的实现[J]. 漳州师范学院学报：自然科学版， 2005（3）：45-50.

[11] Yang L ，  Tian Y ，  Chen Y ， et al. Multi-pattern recognition of sEMG based on improved BP neural network algorithm[C]// 中国控制会议. 2010.

[12]Zhang Y ，  Jing H E ，  Kan X ， et al. Summary of road extraction methods for remote sensing images[J]. Computer Engineering and Applications， 2018.

[13] Jie H ，  Li S ，  Gang S ， et al. Squeeze-and-Excitation Networks[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2017， PP（99）.

[14]Vaswani A， Shazeer N， Parmar N， et al. Attention is all you need[C]//Advances in neural information processing systems. 2017： 5998-6008.

[15] Kip F  T N ，  Welling M . Semi-Supervised Classification with Graph Convolutional Networks[J].  2016.