一种改进的双向A*算法在城市GIS中的实现

摘要：

针对传统最短路径算法存在的一个不足,即算法的时间复杂度与顶点数目的平方成正比,当顶点数目增加时,其运算速度会显著降低,该文提出了一种改进的双向A*算法,其主要思想为利用中间列表双向搜索目标,在搜索的方向上将之前算法中的“目标点”变为“目标面”.实验数据表明,相比较传统的A*和Dijkstra算法,该文提出的双向A*算法在搜索速度上更快,特别是当顶点数目较多时,该算法仍旧能保持较快的计算速度.

关键词：城市地理信息系统、网络分析系统、最短路径、服务质量、搜索速度

所属期刊栏目：45

分类号：P208.2(一般性问题)

资助基金：国家自然科学基金青年基金项目51709125

在线出版日期：2020-05-18（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：145-149