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

Implementation of an improved bi-directional A^* algorithm in urban geographic information system

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

Aiming at the shortcoming that in the traditional shortest path algorithm,the time complexity of the algorithm is proportional to the square of the number of vertices,and when the number of vertices increases,its operation speed will be significantly reduced.To deal with this problem,this paper proposed an improved bi-directional A^*algorithm(denoted by bi-directional A^*).The main idea of the Bi-directional A^*is summarized as follows:leverage the intermediate list to bidirectional search the target,and change the"target point"in the previous algorithm into"target surface"in the search direction.Experimental results showed that the bi-directional A^*algorithm proposed in this paper was much faster than the traditional A^*and Dijkstra algorithms,especially when the number of vertices was much higher.