|其它题名: ||Research on the shortest path algorithm with pre-processing|
|作者: ||謝逢鳴;Hsieh, Feng-ming|
|关键词: ||Dijkstra演算法;直線距離A*;地標A*;Dijkstra algorithm;Euclidean A*;landmark-based A*|
|上传时间: ||2010-01-11 04:58:54 (UTC+8)|
The research on the shortest path algorithm has quite a long history in computer science. It has also seen many applications in different fields such as intelligent transportation system (ITS), geographical information system (GIS) and robotics. Recently with the progress in technology, people began to use the electronic map in hand for path finding. To find the shortest path, precision, efficiency, and time are the three factors of concern. Under the premise of no pre-processing, traditional works focus on reduction of the search time by improving the heap data structure of the algorithm. But this kind of improvement soon faces a bottleneck. By allowing pre-processing to guide the search, recent works show that much gain in efficiency and time can be obtained. The pre-processing of the original map serves to provide two kinds of information. One relates to arcs that need not be expanded, e.g. the arc-flag method. The other relates to estimation of the remaining distance, e.g. the landmark-based distance estimation in A*. This paper intends to evaluate their effectiveness. To have a good base for stacking the different pre-processing methods, the Dijkstra algorithm, the Euclidean A* and their bidirectional counterparts are compared. Only the Euclidean A* survived. Both bidirectional versions are dropped out due to poor time performance. Then based on the Euclidean A* and the directional landmark-based A*, various combinations of pre-processing are tested which include the zone distance, the arc-flag, the arc-reach, and the node-reach methods. To further improve the gain in performance, an error-tolerant undirectional landmark-based A* is proposed where a little tradeoff in precision is considered. The results show that under the same error rate, the undirectional landmark-based A* is better than the Euclidean A* and the directional landmark-based A* in terms of both time and efficiency. Finally based on the undirectional landmark-based A*, various combinations of pre-processing are also tested. For all the results, the experiments are carried out based on an electronic map of the Taiwan or a smaller part of it, the Taipei City and the Taipei County.