【摘要】 动态网络中两节点间最短路径问题是目前尚未解决的一个难题.文中提出利用A*算法来求解电子地图中的这一问题,并利用电子地图中的地理信息来得到网络中两节点间最短距离的下界,运用这些下界来设计有效的A*算法.以广州市电子地图为基础,随机产生了一个满足先进先出原则的动态网络,利用这个网络对提出的算法进行了试验及性能分析.试验结果证明了该方法的有效性.更多还原

【Abstract】 Shortest path problem from one origin node to one destination node in dynamic networks is an unsolved 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.更多还原