摘要
动态网络中两节点间最短路径问题是目前尚未解决的一个难题.文中提出利用A*算法来求解电子地图中的这一问题,并利用电子地图中的地理信息来得到网络中两节点间最短距离的下界,运用这些下界来设计有效的A*算法.以广州市电子地图为基础,随机产生了一个满足先进先出原则的动态网络,利用这个网络对提出的算法进行了试验及性能分析.试验结果证明了该方法的有效性.
Shortest path problem from one origin node to one destination node in dynamic networks is an unsol, ved hard problem. An approach based on A＊ algorithm is adopted to solve the problem in electronic maps. The approach uses geographical information on electronic maps to get lower bounds on minimum travel time in networks. These lower bounds are exploited in designing efficient adaptations of the A＊ algorithm. Based on Guangzhou City＇s electronic map, a dynamic network containing 2 0000 nodes, 4 0000 links and 144 time intervals is randomly generated, which satisfies the First In First Out property （FIFO）. The approach is implemented with this dynamic network and its computational performance is analyzed experimentally. The experimental results show the effectiveness of the approach.
出处
《武汉理工大学学报（交通科学与工程版）》
2006年第5期885-888,共4页
Journal of Wuhan University of Technology（Transportation Science & Engineering）
基金
广东省自然科学基金项目(批准号:020945)
国家自然科学基金项目资助(批准号:50578064)
关键词
A＊算法
动态路径诱导
电子地图
最短路径问题
A＊ algorithm
dynamic path guidance
electronic map
shortest path problems
