基于A-Star路径搜索预测算法优化策略的研究与实现

基于A-Star路径搜索预测算法优化策略的研究与实现

曾浩1，曾奕杰2，盛攀龙1

（1．西安欧亚学院，陕西 西安 710065；2．西安科技大学 计算机科学与技术学院，陕西 西安 710699）

摘要：一般在寻找路径时，从起点到终点的过程中有许许多多的路径，其中有距离最短的路径，也有距离最长的路径，找最短路径的过程中往往会花费大量的时间。路径搜索算法的作用是用于解决最短路径问题的算法。有时，它也被称作“最短路径算法”，目前，最短路径算法最常用的有：Dijkstra算法，Bellman-Ford算法，Floyd算法、SPFA算法和A-Star算法（也被称为A*算法、A星算法、A*搜索算法）。它的独特之处是检查最短路径的每个可能的节点时引入了全局信息，对当前节点距终点的距离做出估计，并作为评价该节点处于最短路径上的可能性的量度。A-Star算法改变了它自己行为的能力基于启发式代价函数，启发式函数在游戏中非常有用，在速度和精确度之间取一个折衷的方法会让游戏运行的更快。文中提出了A-Star路径搜索预测算法优化策略的研究与实现，首先，实现一个经典的A-Star搜索算法，描绘A-Star路径搜索算法的基本工作原理和过程。其次，提出引入深度优先搜索和广度优先搜索的解决方案进行纵向和横向的评估，进一步增强算法的有效性。最后，根据以上研究内容可以得出结论，根据现实中的实际情况，用于解决更大规模、多阻塞、模糊求解的、具有高效率要求的路径搜索的问题

关键词：A-Star算法；路径搜索算法；最短路径；高效率

ABSTRACT

ZENG Hao1,ZENG Yijie2,SHENG Panlong1

(1.Xi’an Eurasia University,Xian 710065,China;2.College of Computer Science and Technology, Xi’an University of Science and Technology,Xian 710699,China)

Abstract: Generally, when finding a path, there are many paths in the process from the starting point to the end point, including the path with the shortest distance and the path with the longest distance. The process of finding the shortest path often takes a lot of time. The role of the path search algorithm is the algorithm used to solve the shortest path problem. Sometimes, it is also called "shortest path algorithm". At present, the most commonly used shortest path algorithms are: Dijkstra algorithm, Bellman-Ford algorithm, Floyd algorithm, SPFA algorithm and A-Star algorithm (also known as A* algorithm, A star algorithm, A* search algorithm). It is unique in that it introduces global information when examining each possible node of the shortest path, and estimates the distance of the current node from the end point as a measure of the probability that the node is on the shortest path. The ability of the A-Star algorithm to change its own behavior is based on a heuristic cost function. Heuristic functions are very useful in games where a compromise between speed and accuracy will make the game run faster. In this paper, the research and implementation of the optimization strategy of A-Star path search prediction algorithm are proposed. First, a classic A-Star search algorithm is implemented, and the basic working principle and process of the A-Star path search algorithm are described. Secondly, a solution introducing depth-first search and breadth-first search is proposed for vertical and horizontal evaluation to further enhance the effectiveness of the algorithm. Finally, according to the above research content, it can be concluded that according to the actual situation in reality, it is used to solve the problem of larger-scale, multi-blocking, fuzzy solution, and high-efficiency path search.

Keywords: A-Star algorithm; Path search algorithm; Shortest path; High efficiency.

1  绪论

路径搜索算法如今被广泛的应用到各个领域，它根据引入的数据，寻找最短路径，可能是距离最短的路径，也可能是时间最短的路径，路径搜索算法也被称为最短路径搜索算法[1]。本章节主要讲述了常用的路径搜索算法的优缺点。

传统的A-Star搜索算法是常用的最短路径搜索算法之一，虽然该算法是静态路网中寻找最短路径效率最高的算法，但是每次利用传统的A-Star搜索算法寻找最小代价的点时，需要将周围的八个点全部遍历一遍，进而找到代价最小的节点作为下一步要走的节点，如果每一次最小代价的节点刚好在最后一个位置上，这时便会浪费极大的空间。其次，如果传统的A-Star搜索算法中没有最短路径，则传统的A-Star搜索算法会穷举所有的可能，这样对空间的需求及大。深度优先搜索和广度优先搜索是图形搜索算法中常用的两种算法。它们可以有效的处理遇到相同大小的节点时优先选取哪一个节点作为下一步要走的节点，在一定程度上节省了时间。本章节主要通过广度优先搜索算法、深度优先搜索算法对传统的A-Star搜索算法进行适当的改进，并且将改进后的获取的大量数据进行对比，得出结论。

2  路径搜索算法的种类

路径搜索算法包含Dijkstra算法、SPFA算法、A-Star算法、Bellman-Ford算法、Floyd-Warshall算法、Johnson算法[2]。目前常用的路径搜索算法有：Dijkstra算法、A-Star算法、Bellman-Ford算法、Floyd-Warshall算法。A-Star算法作为启发式搜索算法的典型代表之一，更是被经常应用于全局路径的规划[3]。

3  经典的A-Star算法

3.1经典的A-Star算法介绍

A-Star算法是一种静态路网中寻找最短路径最有效的直接搜索方法，它也是一种启发式搜索算法。启发式搜索即按照建立的启发式搜索规则在空间范围内进行搜索。经典的A-Star算法根据F值即从起点开始的移动代价G值与从指定的点移动到终点的估算成本H值相加来衡量下一步将要选择的节点。一个高效率的启发式搜索规则可以在一定程度上减少使用A-Star算法寻找最短路径的空间复杂度，反之，则会大量的浪费时间和空间，甚至会产生在具有最短路径的前提下，最短路径搜索失败的可能性。

3.2经典的A-Star算法的优缺点

A-Star算法的优点：首先，它是静态路网中寻找最短路径效率最高的算法。其次，它可以使用自己规定的启发式规则寻找下一个节点，一个高效率的启发式规则比低效率的启发式规则会更加有效，并且成功率也会大大的提高。

A-Star算法的缺点：首先，每次寻找最小代价的点时，需要将周围相邻的八个节点全部遍历一遍，进而找到代价最小的节点作为下一步要走的节点，如果每一次最小代价的节点刚好在最后一个位置，这时候就会浪费极大的时间。其次，A-Star算法的空间需求太大，若一个地图中没有最短路径，则A-Star算法会穷举所有的可能，这样就导致无论是时间还是空间的利用率都很低。

3.3经典的A-Star算法的基本框架

A-Star算法是Dij算法和BFS算法优点的集中体现，该算法主要通过计算每次当前访问的节点与其相邻的八个节点的代价（距离），然后选取最小代价的相邻点，作为下一次要访问的点。A-Star作为经典的启发式搜索算法之一，是根据特定的启发式搜索规则对下一个要走的节点进行搜索。如图2-1所示[4]。

图2-1 初始图

图中绿色表格为起点，红色表格为终点，蓝色表格为障碍物（墙），如果要利用A-Star算法从A点走到B点，首先需要将地图划分成若干个正方形方格，利用二维数组来标识它，并且将每一个方格的中心称为“节点”，这里网上有许多的文章都在询问为什么不直接描述正方形而要用节点进行描述，因为有时候可能把地图划分成其他任意图形，例如：五边形，六边形，七边形等。如果是其他任意图形，则可能在边上，也可能在中心。二维数组中的每一项都代表地图中的每一个方格，每个方法都具有两种状态，分别是：走过（False）和未走过（True）。通过启发式函数对地图上每一个点到终点的代价进行有效的评估和预测，最后再完成从A点到B点的最短路径的寻找。

4  广度优先搜索算法与广度优先搜索的A-Star算法

4.1广度优先搜索算法介绍

广度优先搜索算法是图形搜索算法的一种。它通过系统的方法搜索数据中的节点，经常用于最短路径搜索和路径规划等应用[5]。该算法借助队列存放下一层的节点来实现，它是按照每一层进行遍历的，它不能按照深度优先搜索算法来使用递归实现。它的基本工作原理是：首先，选取一个节点作为顶点，访问该点，并且从该点开始搜索。其次，将该点的下一层都加入到队列中，按照搜索规则找到下一层需要访问的节点，访问下一层需要访问的节点，然后按照队列的“先进先出”的规则，每次出去一个节点，就将该节点的下一层没有被访问过的相邻节点全部加入到队列中，重复上述过程，直到找到最优路径则可以停止。

4.2广度优先搜索算法的优缺点

广度优先搜索算法的优点：首先，无论问题的本质有多么不同，用广度优先搜索算法解题的步骤是相同的。其次，广度优先搜索算法使用的是无溯回操作，即出栈和入栈的结果，所以广度优先搜索算法比深度优先搜索算法所占用的时间少。最后，当节点之间的权值和节点的深度成正比时，特别是每个节点到根节点的权值都等于深度时，广度优先搜索算法比深度优先搜索算法更容易寻找到最优解。

广度优先搜索算法的缺点：首先，广度优先搜索算法需要遍历地图所有的点，所以该算法所占用的存储空间比深度优先搜索算法更大更多，因此，在程序中要时刻注意队列溢出和节省内存空间的问题。其次，广度优先搜索算法没有入队和出队的操作，所以运行速度比深度优先搜索算法快。

4.3广度优先搜索的A-Star算法的介绍

由于传统的A-Star算法是通过启发式函数寻找最小代价所对应的节点作为下一步要走的节点，如上所述的传统A-Star算法的缺点，因此，采用广度优先搜索算法对传统A-Star算法寻找最小节点进行改进，通过将该算法中的启发式函数改进为首先计算水平方向的相邻节点对应的代价，其次计算垂直方向的相邻节点所对应的代价。按照这个顺序，若找到最小代价所对应的相邻节点，则直接将该节点作为下一步要走的节点，若找到多个最小的相同代价的相邻节点，则按照优先考虑水平方向的相邻节点，后考虑垂直方向的相邻节点的顺序去选取下一步要走的节点。

在通过广度优先搜索算法改进的基础上，利用在百分之二十随机障碍物的分布情况、百分之三十随机障碍物的分布情况、百分之四十随机障碍物的分布情况和百分之六十随机障碍物的分布情况中，分别对百分之二十随机障碍物的分布情况、百分之三十随机障碍物的分布情况、百分之四十随机障碍物的分布情况和百分之六十随机障碍物中各获取2000组横向图和2000组纵向图的广度优先搜索的A-Star算法，并且通过对百分之二十随机障碍物的4000组数据、百分之三十随机障碍物的的4000组数据、百分之四十随机障碍物的4000组数据和百分之六十随机障碍物的4000组数据进行对比，得出该改进点的优点。

大致流程如下图2-2所示。

图2-2 广度优先搜索的A-Star算法流程图

5  深度优先搜索算法与深度优先搜索的A-Star算法

5.1深度优先搜索算法介绍

深度优先搜索算法是图形搜索算法的一种，被人们广泛的使用，从遍历节点，到判断图的连通性，再到路径规划以及最短路径的搜索[6]，都用到了深度有限搜索算法。深度优先搜索算法是通过堆栈实现的。该算法描述的是一开始选择一个节点，将该节点当成顶点，然后开始遍历，首先，沿着一条路径进行穷尽式的寻找，记住每一个搜索过的节点，直到该路径上所有的节点都被访问过。这时退回到上一个被访问过的节点，开始寻找该节点的其他没有被访问过的邻接点进行访问，并且沿着该方向继续进行穷尽式搜索。不断的重复上述的过程，直到图中所有节点都被访问过则停止寻找。

5.2深度优先搜索算法的优缺点

深度优先搜索算法的优点：首先，深度优先搜索有两种方式，一种是递归方式，一种是非递归方式，碰到明显的递归问题时，可以使用递归方式，递归方式可以使程序的结构变得简单易懂，否则就使用非递归方式[7]，当数据集所包含的节点比较多时，由于堆栈容量的限制，使用递归方式容易令堆栈溢出，此时则适合使用非递归方式。其次，深度优先搜索算法包含全部保留和不全部保留节点这两种情况，其中不保留全部节点属于常用的回溯方法，它每一次将节点从数据库中弹出，所以，当图中节点数量较多时，使用该方法，可以有效的减少它所占有的空间，此时深度优先搜索算法是一种非常高效的方法。最后，深度优先搜索算法相比于广度优先搜索算法，由于它具有提前找到终点的可能，所以降低了内存的消耗，同时也降低了时间的消耗[8]。

深度优先搜索算法的缺点：首先，如上所述，当该算法的数据集合所包含的节点较多时，使用递归方法会造成堆栈的溢出。其次，深度优先搜索算法在没有限制条件的情况下，容易陷入死循环或者进行大量无效的搜索。

5.3深度优先搜索的A-Star算法的介绍

如上所述的传统A-Star算法的缺点，因此，决定采用深度优先搜索算法对传统A-Star算法选取最小代价对应的节点作为下一步要走的节点进行改进，将优先计算垂直方向的相邻节点，其次再计算水平方向上的相邻节点，若找到了代价最小的相邻节点，则将该节点作为下一步要走的节点，若找到多个最小的相同代价的相邻节点，则按照优先考虑垂直方向的相邻节点，后考虑水平方向的相邻节点的顺序去选择下一步要走的节点。

在通过深度优先搜索算法对A-Star算法改进的基础上，利用在不同障碍物复杂程度的情况下，各自获取2000组横向图与纵向图的数据进行对比，得出该改进点的优点。大致流程如图2-3所示。

图2-3 深度优先搜索的A-Star算法流程图

6  深度优先搜索的A-Star

算法与广度优先搜索的A-Star算法对比

通过上述对广度优先搜索的A-Star算法与深度优先搜索的A-Star算法的描述，采用两种改进方法分别获取了2000组数据，并绘制成簇状柱形图和折线图。

广度深度横向对比如图2-4所示。

图2-4 广度深度横向对比图

广度深度纵向对比如图2-5所示。

图2-5 广度深度纵向对比图

通过对广度深度横向对比图和广度深度纵向对比图的对比分析，并将广度优先搜索的A-Star和深度优先搜索的A-Star的比例进行汇总，绘制成广度深度横纵对比图。

广度深度横纵对比图如图2-6所示。

图2-6 广度深度横纵比图

由图2-4和图2-5可知：首先，在不同的障碍物复杂度的情况下，伴随着复杂度的变化，横向图和纵向图中的深度优先搜索的A-Star算法和广度优先搜索的A-Star算法变化相同。其次，在同一复杂度的条件下，横向图的深度优先搜索的A-Star算法和广度优先搜索的A-Star算法与纵向图中的深度优先搜索的A-Star算法和广度优先搜索的A-Star算法的变化趋势相同，值相近。

由图2-6可知：伴随着障碍物复杂度的升高，横图与纵图的深度与广度比的差距变化不大。

综上所述：通过两种改进方法获取的数据有效，印证了横向图中广度优先搜索的A-Star算法比深度优先搜索的A-Star算法好，纵向图中深度优先搜索的A-Star算法比广度优先搜索的A-Star算法好，并且能根据现实中的实际情况，用于解决更大规模、多阻塞、模糊求解的、具有高效率要求的路径搜索与预测任务中。

7  总结

路径搜索算法在日常中被广泛的应用到各个领域，从即时战略游戏、开放世界的MMORPG游戏为代表的大型游戏，到日常生活中所使用的百度地图、高德地图等电子地图，再到以淘宝、拼多多为首的收发快递，都充分使用了“路径规划”，而“最短路径搜索”是“路径规划”中不可或缺的重要组成部分。

首先，本次研究基于经典的A-Star搜索算法描述了经典A-Star路径搜索算法的基本框架。

其次，阐述了该算法的具体实现步骤，主要包含了四个步骤，分别是：1）划分区域与随机生成障碍物。2）开始搜索。3）路径排序。4）继续搜索。

最后，引入不同的搜索方法与A-Star算法进行对比。一开始，基于经典的A-Star算法的缺点，讲述了通过广度优先搜索和深度优先搜索对经典A-Star算法的改进后的广度优先搜索的A-Star算法和深度优先搜索的A-Star算法的改进点以及基本工作原理。然后针对横向图和纵向图在不同障碍物复杂度的基础上，利用广度优先搜索的A-Star算法和深度优先搜索的A-Star算法分别获取2000组数据进行对比，进而对这两种改进方法进行评估。

参考文献

[1]谷月, 张德育, 晋峰高. 基于改进A*算法的机器人路径搜索的研究[J]. 现代信息科技, 2020, 4(13): 30-32.

[2] 魏为民, 陆致静, 叶语亭. 一种基于A*算法改进的最短路径搜索方法[J]. 上海电力学院学报, 2018, 34(02): 180-184.

[3] 郭银景, 孟庆良, 孔芳, 吕文红. AUV路径规划算法研究现状与展望[J]. 计算机科学与探索, 2020, 14(12): 1981-1994.

[4] 南湖Giser: 最短路径搜寻之A*算法. 简书网站. 2018年12月08日. https: // www. jianshu. com/ p/ 352b348d24ec.

[5] 黎利辉. 基于深度优先搜索的连连看游戏路径查找算法[J]. 福建电脑. 2019(01): 16-18.

[6] 陈波, 高成发, 管玉琦. 基于生成树的控制网最小独立异步环搜索方法研究[J]. 测绘工程. 2018(04): 54-59.

[7] 张超超, 房建东. 基于定向加权A*算法的自主移动机器人路径规划[J]. 计算机应用. 2017, 37(S2): 77-81.

[8] 余星乐. 基本搜索算法的实现[J]. 通讯世界. 2019(03): 297-298.

1