摘要
动态最短路径搜索算法是智能交通系统技术应用的关键问题之一．为了解决这一问题,提出以一致性原则动态形式为基础的动态A*算法(dynamic A* algorithm,DA* algorithm)并证明了在两节点间动态下界满足一致性原则动态形式前提下,该算法能够求解满足先进先出原则的动态网络中两节点间最短路径问题．在以广州市交通路网为基础的动态网络上对DA*算法进行试验．试验结果表明,Dijkstra算法的和A*算法的平均计算时间分别是DA*算法的6．55和1．43倍．
Efficient dynamic shortest path algorithm in static networks plays an important role in intelligent transportaitro 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 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.
出处
《深圳大学学报（理工版）》
EI
CAS
北大核心
2007年第1期32-36,共5页
Journal of Shenzhen University(Science and Engineering)
基金
国家自然科学基金资助项目(50578064)
华南农业大学校长基金资助项目(2006k017)
关键词
智能交通系统
动态路径诱导
最短路径
A^＊算法
先进先出原则
一致性原则
广州市电子地图
intelligent transportation system
dynamic route guidance
shortest path
A^＊ algorithm
first in first out
consistency assumption
electronic map of Guangzhou
