最短路徑演算法的研究在計算機科學中已有相當長歷史，也常應用於智慧型運輸系統(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.

1.緒論 1
1.1 研究背景與動機 1
1.2 論文架構 2
2.文獻探討 4
2.1 戴式演算法（Dijkstra） 4
2.2 直線距離A* 5
2.3 雙向路徑搜尋演算法 6
2.4 有向地標A* 7
2.5 邊可到達節點之標記（Arc-flag） 8
2.6 節點到達度（Node-reach） 9
2.7 邊到達度（Arc-reach） 10
2.8 其他前處理方法 10
2.9 各種前處理方法之組合 11
3.方法介紹 12
3.1 區域間的最短距離 12
3.2 無向地標A* 13
4.實驗結果 15
4.1 實驗環境與設計 15
4.2 以距離為成本之地圖資料： 17
4.2.1 有無剩餘距離估算及單雙向搜尋方式 17
4.2.2 各前處理的比較 20
4.2.3 容錯下不同參數之設定 23
4.2.4 無向地標A*與各前處理之組合 33
4.3 以時間為成本之地圖資料： 34
4.3.1 時間成本下各前處理的組合比較 34
5.結論與未來展望 41
參考文獻 45

圖目錄
圖 1 Google Earth、Papago與TOBE系統 1
圖 2 Dijkstra演算法與搜尋空間示意圖 5
圖 3 A*演算法搜尋空間示意圖	 6
圖 4 有向地標A*示意圖 7
圖 5 Arc-flag示意圖 8
圖 6 reach-value說明示意圖 9
圖 7 最短路徑演算法示意圖 12
圖 8 區域間最短距離示意圖 13
圖 9 以中位數KD-tree將全台灣地圖切割為512區塊 16
圖 10 以距離為成本路徑搜尋平均時間 18
圖 11 以距離為成本路徑搜尋平均效率 18
圖 12 文獻[4] 以距離為成本各地圖路徑搜尋平均時間 19
圖 13 文獻[4] 以距離為成本各地圖路徑搜尋平均效率 19
圖 14 以距離為成本前處理路徑搜尋平均時間 20
圖 15 以距離為成本前處理路徑搜尋平均效率 21
圖 16 以距離為成本直線距離A*組合前處理搜尋平均時間 22
圖 17 以距離為成本直線距離A*組合前處理搜尋平均效率 22
圖 18 以距離為成本有向地標A*組合前處理搜尋平均時間 23
圖 19 以距離為成本有向地標A*組合前處理搜尋平均效率 23
圖 20 以距離為成本無向地標A*各種組合搜尋錯誤率 25
圖 21 以距離為成本無向地標A*各種組合搜尋平均時間 25
圖 22 以距離為成本無向地標A*各種組合搜尋平均效率 25
圖 23 以距離為成本各種評估公式與真實距離之比例 26
圖 24 以距離為成本在不同β下無向地標A*錯誤率比較 26
圖 25 以距離為成本在不同β下無向地標A*路徑搜尋平均時間 27
圖 26 以距離為成本在不同β下無向地標A*路徑搜尋平均效率 27
圖 27 以距離為成本在不同α下直線距離A*錯誤率比較 28
圖 28 以距離為成本在不同α下直線距離A*路徑搜尋平均時間 29
圖 29 以距離為成本在不同α下直線距離A*路徑搜尋平均效率 29
圖 30 以距離為成本在不同α下有向地標A*錯誤率比較 29
圖 31 以距離為成本在不同α下有向地標A*搜尋平均時間 30
圖 32 以距離為成本在不同α下有向地標A*搜尋平均效率 30
圖 33 以距離為成本有向地標A*與無向地標A*搜尋時間比較 31
圖 34 以距離為成本有向地標A*與無向地標A*搜尋效率比較 31
圖 35 以距離為成本無向地標A*組合前處理搜尋平均時間 33
圖 36 以距離為成本無向地標A*組合前處理搜尋平均效率 34
圖 37 以時間為成本各演算法搜尋平均時間 35
圖 38 以時間為成本各演算法搜尋平均效率 35
圖 39 以時間為成本直線距離A*與各前處理組合平均搜尋時間 36
圖 40 以時間為成本直線距離A*與各前處理組合平均搜尋效率 36
圖 41 以時間為成本有向地標A*與各前處理組合平均搜尋時間 37
圖 42 以時間為成本有向地標A*與各前處理組合平均搜尋效率 37
圖 43 以時間為成本無向地標A*與各前處理組合平均搜尋時間 38
圖 44 以時間為成本無向地標A*與各前處理組合平均搜尋時間 38
圖 45 以時間為成本各種評估公式與真實距離之比例 40
 
表目錄
表 1 實驗環境 15
表 2 文獻[4]測試地圖資料 19
表 3 以距離為成本各種評估公式與真實距離之比例彙總 26
表 4 以距離為成本在不同容錯程度上表現最短之演算法彙總 30
表 5 以距離為成本無向地標A*非最短路徑列表 32
表 6 各級道路速限表 35
表 7 以時間為成本各種評估公式與真實距離之比例彙總 40
表 8 各條件設定下適合之搜尋方法 41
表 9 在以距離/時間為成本有向地標A*與無向地標A*之比較 42
表 10 路徑搜尋所使用各資料檔之資訊 43
表 11 無向地標A*最佳搜尋效率組合檔案列表 43
表 12 全區無向地標A*最佳搜尋時間組合推估 44

[1]交通部運輸研究所, “路網數值圖1.1版,” http://www.iot.gov.tw/mp.asp, November 2004.
[2]研勤科技股份有限公司, “Papago,” www.mactiontech.com
[3]裕隆日產汽車股份有限公司, “Tobe,” http://www.nissan.com.tw/
[4]A.V. Goldberg, and C. Harrelson, “Computing the Shortest Path: A* Search Meets Graph Theory,” 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '05), Vancouver, Canada, 2005.
[5]A.V. Goldberg, H. Kaplan, and R. Werneck, “Reach for A*: Efficient Point-to-Point Shortest Path Algorithms,” Report MSR-TR-2005-132, Microsoft Research, October 2005.
[6]A.V. Goldberg and R. Werneck, “Computing Point-to-Point Shortest Paths from External Memory,” SIAM Workshop on Algorithms Engineering and Experimentation (ALENEX '05), Vancouver, Canada, 2005.
[7]D. Schultes, “Fast and Exact Shortest Path Queries Using Highway Hierarchies,” Master’s thesis, Department of Computer Science, University des Saarlandes, Germany, 2005.
[8]Dorothea Wagner, Thomas Willhalm, and Christos Zaroliagis, “Geometric Containers for Efficient Shortest Path Computation,” DELIS Techical Report, 2004.
[9]E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numerische Mathematik. Volume 1 , 1959, pp. 269–271.
[10]F. Schulz, D. Wagner, and K. Weihe, “Dijkstra's algorithm on-line: An empirical case study from public railroad transport, ” ACM Journal of Experimental Algorithmics, vol. 5, no. 12, 2000.
[11]Google, “Google Earth,” http://earth.google.com/
[12]I Pohl, “Bi-directional Search,” Machine Intelligence, volume 6,Edinburgh Univ. Press, Edinburgh, 1971, pp.124-140.
[13]Martin Holzer, Frank Schulz, and Thomas Willhalm, “Combining Speed-Up Techniques for Shortest-Path Computations,” Proceedings Third International Workshop on Experimental and Efficient Algorithms (WEA), volume 3059 of Lecture Notes in Computer Science, Angra dos Reis, Brazil, 2004, pp.269-284.
[14]M. Thorup, “Integer priority queues with decrease key in constant time and the single cource shortest paths problem,” 35th ACM Symposium on Theory of Computing,  2003, pp.149-158.
[15]P. E. Hart, N. J. Nilsson, B. Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths,” IEEE Transactions on Systems Science and Cybernetics SSC4 (2), 1968, pp. 100-107.
[16]R. Gutman, “Reach-based routing: A new approach to shortest path algorithms optimized for road networks,” Proceedings 6th Workshop on Algorithm Engineering and Experiments (ALENEX), New Orleans, LA, USA, 2004, pp.100-111.
[17]Rolf H. Moehring, Heiko Schilling, Birk Schütz, Dorothea Wagner, and Thomas Willhalm, “Partitioning Graphs to Speed Up Dijkstra's Algorithm,” Proceedings of the 4th International Workshop on Experimental and Efficient Algorithms (WEA'05), Santorini Island, Greece, 2005, pp.189-202.
[18]Takahiro Ikeda, Min-Yao Hsu, and Hiroshi Imai, “A Fast Algorithm for Finding Better Routes by AI Search Techniques,” Proceedings of the IEEE International Conference on Vehicle Navigation & Information Systems (VNIS'94), Yokohama, Japan, 1994, pp.291-296.
[19]Yun-Wu Huang, Ning Jing, and Elke A. Rundensteiner, “Hierarchical Optimization of Optimal Path Finding for Transportation Applications,” ACM 5th Int. Conf on Information and Knowledge Management (CIKM'96), Rockville, Maryland, USA, 1996, pp.261-268.