|
|||||
|
|
| A*算法改进及其在动态最短路径问题中的应用 | |
| 引用本文： | 邹亮,徐建闽,朱玲湘. A*算法改进及其在动态最短路径问题中的应用[J]. 深圳大学学报(理工版), 2007, 24(1): 32-36 |
| 作者姓名： | 邹亮 徐建闽 朱玲湘 |
| 作者单位： | 1. 深圳大学土木工程学院,深圳,518060 2. 华南理工大学交通学院,广州,510640 3. 华南农业大学理学院,广州,510642 |
| 基金项目： | 国家自然科学基金;华南农业大学校科研和教改项目 |
| 摘 要： | 动态最短路径搜索算法是智能交通系统技术应用的关键问题之一．为了解决这一问题,提出以一致性原则动态形式为基础的动态A*算法(dynamic A* algorithm,DA* algorithm)并证明了在两节点间动态下界满足一致性原则动态形式前提下,该算法能够求解满足先进先出原则的动态网络中两节点间最短路径问题．在以广州市交通路网为基础的动态网络上对DA*算法进行试验．试验结果表明,Dijkstra算法的和A*算法的平均计算时间分别是DA*算法的6．55和1．43倍． |
| 关 键 词： | 智能交通系统 动态路径诱导 最短路径 A*算法 先进先出原则 一致性原则 广州市电子地图 |
| 文章编号： | 1000-2618(2007)01-0032-05 |
| 修稿时间： | 2006-09-12 |
Improvement of A* algorithm and its application in shortest path problem in dynamic networks |
|
| ZOU Liang,XU Jian-min,ZHU Ling-xiang. Improvement of A* algorithm and its application in shortest path problem in dynamic networks[J]. Journal of Shenzhen University(Science &engineering), 2007, 24(1): 32-36 | |
| Authors: | ZOU Liang XU Jian-min ZHU Ling-xiang |
| Affiliation: | College of Civil Engineering Shenzhen University Shenzhen 518060 P. R. China; College of Transportation and Communication, South China University of Technology, Guangzhou 510640 P. R. China; College of Science South China Agricultural University, Guangzhou 510642 P. R. China |
| Abstract: | Efficient dynamic shortest path algorithm in static networks plays an important role in intelligent transpor-taitro syslem (ITS). To solve this problem, this paper brings forward dynamic A * algorithm based on the dynamic form of consistency assumption. It is proved that dynamic A * algorithm can solve one origin node to one destination node shortest paths problem in dynamic networks that satisfy first-in-first-out principle, if the dynamic lower boundary of the dynamic A * algorithm satisfies the dynamic form of consistency assumption, principle Finally the developed algorithms are implemented with a random dynamic network based on Guangzhou transportation network and their computational performance is analyzed through experiments. The test results showed that A* algorithm and Dijkstra algorithm's average computation time in solving the one-to-one shortest path problem in dynamic networks are 1. 43 and 6. 55 times than dynamic A * algorithm's. |
| Keywords: | intelligent transportation system dynamic route guidance shortest path A * algorithm first in first out consistency assumption electronic map of Guangzhou |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ | |