Loading...
|
Please use this identifier to cite or link to this item:
https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/34155
|
| Title: | 有前處理下最短路徑演算法之研究 |
| Other Titles: | Research on the shortest path algorithm with pre-processing |
| Authors: | 謝逢鳴;Hsieh, Feng-ming |
| Contributors: | 淡江大學資訊管理學系碩士班
魏世杰;Wei, Shih-chieh |
| Keywords: | Dijkstra演算法;直線距離A*;地標A*;Dijkstra algorithm;Euclidean A*;landmark-based A* |
| Date: | 2006 |
| Issue Date: | 2010-01-11 04:58:54 (UTC+8) |
| Abstract: | 最短路徑演算法的研究在計算機科學中已有相當長歷史，也常應用於智慧型運輸系統(ITS）、地理資訊系統(GIS）及機器人學等領域。近來，隨著科技進步，許多人都使用電子地圖來搜尋路徑。在路徑搜尋過程，除計算最短路徑的結果需正確外，如何讓電腦快速有效的完成搜尋也相當重要。在原始地圖資料中如不引入輔助資訊下，通常是透過改進搜尋演算法的資料結構來降低搜尋時間。但這種方法將面臨瓶頸，如要再改善搜尋時間則要有效提升搜尋效率。提升搜尋效率的方法可在搜尋過程中引入輔助資訊輔助搜尋。輔助資訊可分為兩種，一種是在搜尋過程中輔助刪除不必要展開邊的資訊，如Arc-flag、Arc-reach及Node-reach等，另一種則是輔助估計剩餘距離的資訊，如直線距離A*及有向地標A*等。本文所謂的前處理即是對原始地圖資訊作處理以得到輔助資訊。為了提升搜尋效率表現，本文首先提出區域間最短距離以輔助估計剩餘距離資訊。接著進一步在估計剩餘距離資訊上提出容錯之無向地標A*。經實驗發現，無論在以距離為成本或以時間為成本之地圖資料中，在相同錯誤率下，無向地標A*相較於直線距離A*及有向地標A*，皆能有效改善路徑搜尋時間與效率，且其誤差尚在可容忍範圍內。最後本文也試著在無向地標A*基礎上，找出與各種輔助資訊之最佳組合。以上實驗均以台灣地圖或台北縣市地圖為準。
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. |
| Appears in Collections: | [資訊管理學系暨研究所] 學位論文
|
All items in 機構典藏 are protected by copyright, with all rights reserved.
|
