摘要
当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.
出处
《北京化工大学学报(自然科学版)》
CAS
CSCD
北大核心
2009年第5期107-111,共5页
Journal of Beijing University of Chemical Technology(Natural Science Edition)
基金
国家自然科学基金(60704011)
北京市教育委员会共建项目建设计划(XK100100435)