| 带通行限制的加权A*算法及其数据库实现 |
| |
| 引用本文： | 陈易,王晶.带通行限制的加权A*算法及其数据库实现[J].北京化工大学学报(自然科学版),2009,36(5):107-111. |
| |
| 作者姓名： | 陈易 王晶 |
| |
| 作者单位： | 北京化工大学 信息科学与技术学院， 北京 100029 |
| |
| 基金项目： | 国家自然科学基金，北京市教育委员会共建项目建设计划 |
| |
| 摘 要： | 当A*算法应用于带有通行限制的路网时，算法得到的最优解中含有不可通行的路段，而人们期望的搜索结果是可通行路段的集合。为找到符合限制条件的最优解，本文通过建立合适的数据库表结构，对 A*算法进行改进，实现了带通行限制的A*算法，并对启发函数进行加权，使算法能够根据存储在数据库中的限制条件扩展节点，减少算法遍历的节点数目，降低执行时间，达到搜索出符合条件的最短路径的目的。
|
| 关 键 词： | A*算法 启发式搜索 道路通行限制 数据库 A*算法 启发式搜索 道路通行限制 数据库 |
| 收稿时间： | 2009-01-12 |
An improved weighted A* algorithm for a road network with traffic restrictions and its implementation based on a database |
| |
| CHEN Yi,WANG Jing.An improved weighted A* algorithm for a road network with traffic restrictions and its implementation based on a database[J].Journal of Beijing University of Chemical Technology,2009,36(5):107-111. |
| |
| Authors: | CHEN Yi WANG Jing |
| |
| Institution: | College of Information Science and Technology, Beijing University of Chemical Technology, Beijing 100029, China |
| |
| Abstract: | When an A* algorithm is used in a road network with traffic restrictions, the op timal solution contains unanticipated paths. In this paper, we describe an impro ved A* algorithm to deal with the restrictions which has been derived by creatin g a proper database structure and weighting the heuristic function to improve th e search efficiency. The new algorithm can quickly find the optimal solution acc ording to the traffic restrictions, reduce the numbers of nodes and save more ti me than a general A* algorithm. |
| |
| Keywords: | A*algorithm heuristic search road restrictions database |
| 本文献已被 万方数据 等数据库收录！ |
| 点击此处可从《北京化工大学学报(自然科学版)》浏览原始摘要信息 |
| 点击此处可从《北京化工大学学报(自然科学版)》下载免费的PDF全文 |
