论文标题
使用新的启发式估计，改进了道路网络的A*搜索算法
An Improved A* Search Algorithm for Road Networks Using New Heuristic Estimation
论文作者
论文摘要
在图中找到两个点之间的最短路径是一个基本问题，在过去的几十年中一直经过深入研究。最短的路径算法通常应用于现代导航系统，因此我们的研究旨在提高大型欧几里得网络上现有算法的效率。当前的文献缺乏对某些算法在这些类型网络上的性能的深入了解。因此，我们将一种称为$ k $步骤的look-aphead的新的启发式功能纳入A*搜索算法中，并进行了计算实验，以评估和比较各种大小的道路网络上的结果。我们的主要发现是，与标准A*相比，这种新的启发式方法可以显着提高运行时，尤其是对于较大的网络，并且需要较高的$ K $值以随着网络尺寸的增加而实现最佳效率。未来的研究可以通过实施一个程序来自动选择输入网络的最佳$ k $值来基于这项工作。这项研究的结果可以应用于GPS路由技术或其他导航设备，以加快找到从起源到目的地的最短路径所需的时间，这是日常生活中的基本目标。
Finding the shortest path between two points in a graph is a fundamental problem that has been well-studied over the past several decades. Shortest path algorithms are commonly applied to modern navigation systems, so our study aims to improve the efficiency of an existing algorithm on large-scale Euclidean networks. The current literature lacks a deep understanding of certain algorithms' performance on these types of networks. Therefore, we incorporate a new heuristic function, called the $k$-step look-ahead, into the A* search algorithm and conduct a computational experiment to evaluate and compare the results on road networks of varying sizes. Our main findings are that this new heuristic yields a significant improvement in runtime, particularly for larger networks when compared to standard A*, as well as that a higher value of $k$ is needed to achieve optimal efficiency as network size increases. Future research can build upon this work by implementing a program that automatically chooses an optimal $k$ value given an input network. The results of this study can be applied to GPS routing technologies or other navigation devices to speed up the time needed to find the shortest path from an origin to a destination, an essential objective in daily life.
