最短路径搜索中的A算法改进应用

段明玮

摘 要 最短路径搜索中的A算法，多用于导航、路线动态规划等领域。而在最短路径搜索时，传统A、Dihkstra算法，因不同场景内标记结点数量存在差異性，使得算法实现速率难以保障。因此，本文基于最短路径搜索中的A算法改进思路，对A算法的内部优化、应用展开研究，借此明确最短路径的最优求解方式，提高A算法使用水平。

关键词 最短路径;A算法;标记结点

引言

A算法属于高效率、高精度的启发式搜索算法，在应用A算法时，相关人员需预先搜索图内的最短路径，以获取数据信息。为进一步优化改进A算法。提高其在最短路径搜索时的搜索效率，创新其数据结点存储结构。本文对最短路径搜索中的A算法改进应用展开分析，希望给予相关从业者建议与参考。

1最短路径搜索中的A算法改进思路

原始Dihkstra算法，可将网络结点划分为临时性、未标记、永久性等标记结点。其中算法网络中初始结点属于未标记结点，而搜索期间，以及与最短路径向衔接的端口属于临时性的标记点[1]。其中，不同时期的循环可在搜索距源点时，从临时标记结点，选出路径长度较短的结点出，作为永久性标记结点，同时结束算法。但在原有Dihkstra算法中，由于临时标记节点多存储与无须表内，使得该算法在实际应用中，所经标记结点较多，影响算法实现效率。因此，可将网络内临时标记结点，以最短路径进行排序，可避免在搜索过程中，历经多个标记结点，进而在保障算法质量的基础上，提高算法实现效率。

2A算法在最短路径搜索中的改进应用

2.1 算法实现

A算法是现阶段，较为流行的搜索算法，可基于估价函数，灵活选择最优、最短路径的搜索算法。而在最短路径搜索中，A算法改进思路，在于将现存临时标记结点、源点之间的最短路径，以及标记结点的最小费用，和算法中临时标记结点中，存在的属性值。然后将该属性值作为该标记点集合中，永久标记点的选择依据。此种创新手段，属于A算法的改进应用思路，其中临时标记结点函数可定义为：F（j）=g（j）+h（j-1）[2]。A算法在最短路径搜索中优化改进后，可基于该函数，从A算法搜索方向中，减少算法中结点历经次数，提高整体搜索速度

其一，运行结构。最短路径搜索中，A算法改进应用时，可借助“优先级”队列组成实现。而该队列的产生是通过删除所有元素中，优先级最高的某一元素。在此期间，为避免搜索过程中，反复搜索部分为标记的弧，可在各弧算法过程中，通过一些重复被松弛，且距离起点最短的路径指数，构造优先级队列，同时去除算法累积权值中的最小元素。

其二，存储结构。A算法优化后，可将临接表作为算法的主要存储场所，在优先级队列实现后。相关人员能够使用邻接表。针对图中各弧段，可通过表头、表结点分别设计单链表。而第n个单链表中的y表结点，可表示与第n各弧段存在作用关系的y弧。其中链表表头区域内的结点，可将弧段本身的标识号指导升序排列，便于相关任意结合算法需求，实时访问各弧段链表[3]。因此，A算法在最短路径搜索中改进应用时，将邻接表作为存储结构的主要构件，有利于算法实践中，以最快速度查找相应弧段。

2.2 应用分析

相较于传统Dihkstra算法、A算法，优化改进后的A算法是基于算法网络本身在空间中的分布特征，灵活控制搜索空间。在原有的A算法与Dihkstra算法中，由于永久标记点数较多，影响算法实现效率，目标达成效果。而改进后的A算法在具体应用中，其永久标记点数量在可控范围内，可确保数据分析效果。在路网结点数增加时，A、Dihkstra算法，均会导致最短路径搜索时，最优路径的结点数数量较多。本文针对最优数据结点多的问题，在改进A算法时，通过动态化管理数据，调整结点与弧段结构。

相关人员在算法初步实施中，结合算法实现需求，在网络结点、弧段数据的搜索时，适当生成某结点。并非在网络创建时，改变弧段与结点数据的基本结构[4]。之后，可通过删除部分结点，以更新数据结构，节约各永久、临时性结点存储空间。比如在算法过程中，可借助明确起始结点范围，分析该图幅分布范围，从而整理图内数据，在图幅范围内设计邻接表。例如在某地区交通网络数据计算中，改进后的A算法，可在结点逐一标记后，随机选出部分核心区域，计算该区域范围内的结点数量。进而节约最短路径搜索中，标记结点梳理时间。因此，动态化管理数据的过程中，可在算法施行期间，发挥数据存储版块的可利用率，及时将无效数据筛除。基于该数据管理思路的A算法改进，可在路网中结点数量增加时，解决最短路径搜索是，结点过多的问题。

3结束语

综上所述，本文基于传统A、Dihkstra算法在最短路径搜索时，存在的不足之处，对借助运行、存储结构优化，以及数据动态化管理的改进后的A算法应用要点做出分析。为此，相关人员在不同情境中，使用A算法时，可结合A算法实现需求，灵活控制数网内标记结点数量，强化A算法应用效果。

参考文献

[1] 何梦男，付瑜玲，陈诚，等.基于元胞自动机的应急疏散最短路径优化算法[J].中国安全科学学报，2019，（4）：51-57.

[2] 石峰，陈旭，尹飞，等.基于S3变换的TriBA-Net最短路径路由机制[J].中国科学：信息科学，2018，（1）：100-114.

[3] 刘兰芬，杨信丰，刘林忠.基于标号算法搜索过程的K最短路算法设计[J].兰州交通大学学报，2019，（4）：66-69.

[4] 张默.Dijkstra最短路径算法的研究[J].数学学习与研究，2018，（16）： 13-15.