A*算法在矢量地图最优路径搜索中的应用

A* Algorithm for Finding the Optimal Path on Vector Maps

在交通地理信息系统应用中,如何既快速又准确地找到最优路径是一个关键的问题。将人工智能领域的A*算法引入到矢量地图的最优路径搜索中来,论述了应用于矢量地图最优路径搜索的A*算法是一种完备的算法。同时,针对交通矢量地图的特点,提出了一种将矢量地图本身节点的数据结构和A*算法需搜索的节点数据结构在索引时相互联系,在计算时又相互分离的策略,提高了A*算法的执行效率。实验表明这种改进数据结构的A*算法在准确性和快速性方面都取得了令人满意的效果。

The key problem is how to find a optimal path accurately and quickly in the application of GIS -T, This thesis introduces A ＊ algorithm used in AI into the searching on vector maps, and states that the A ＊ algorithm applied in vector maps is a complete algorithm, At the same time, this article also raises a strategy which links the designs of vertexes of A ＊ and vector maps together when the indexing occurs, and separates them when computing occurs to improve the performance of A ＊ searching. The experiment shows the satisfactory results of the enhanced A ~ searching both in accuracy and quickness,