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

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

作　　者：陈易[1] 王晶[1] 

机构地区：[1]北京化工大学信息科学与技术学院,北京100029

出　　处：《北京化工大学学报（自然科学版）》2009年第5期107-111,共5页Journal of Beijing University of Chemical Technology(Natural Science Edition)

基　　金：国家自然科学基金(60704011);北京市教育委员会共建项目建设计划(XK100100435)

摘　　要：当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.

关 键 词：A＊算法 启发式搜索 道路通行限制 数据库 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]