带通行限制的加权A*算法及其数据库实现

An improved weighted A* algorithm for a road network with traffic restrictions and its implementation based on a database

当A*算法应用于带有通行限制的路网时,算法得到的最优解中含有不可通行的路段,而人们期望的搜索结果是可通行路段的集合。为找到符合限制条件的最优解,本文通过建立合适的数据库表结构,对A*算法进行改进,实现了带通行限制的A*算法,并对启发函数进行加权,使算法能够根据存储在数据库中的限制条件扩展节点,减少算法遍历的节点数目,降低执行时间,达到搜索出符合条件的最短路径的目的。

When an A ＊ algorithm is used in tains unanticipated paths. In this paper, we a road network with traffic restrictions, the optimal solution condescribe an improved A ＊ algorithm to deal with the restrictions which has been derived by creating a proper database structure and weighting the heuristic function to improve the search efficiency. The new algorithm can quickly find the optimal solution according to the traffic restrictions, reduce the numbers of nodes and save more time than a general A ＊ algorithm.