| dc.contributor.advisor | 連耀南 | zh_TW |
| dc.contributor.advisor | Lien, Yao Nan | en_US |
| dc.contributor.author (Authors) | 林啟榮 | zh_TW |
| dc.contributor.author (Authors) | Lin, Chi Jung | en_US |
| dc.creator (作者) | 林啟榮 | zh_TW |
| dc.creator (作者) | Lin, Chi Jung | en_US |
| dc.date (日期) | 2008 | en_US |
| dc.date.accessioned | 11-Sep-2009 16:03:53 (UTC+8) | - |
| dc.date.available | 11-Sep-2009 16:03:53 (UTC+8) | - |
| dc.date.issued (上傳時間) | 11-Sep-2009 16:03:53 (UTC+8) | - |
| dc.identifier (Other Identifiers) | G0094971011 | en_US |
| dc.identifier.uri (URI) | https://nccur.lib.nccu.edu.tw/handle/140.119/29688 | - |
| dc.description (描述) | 碩士 | zh_TW |
| dc.description (描述) | 國立政治大學 | zh_TW |
| dc.description (描述) | 資訊科學學系 | zh_TW |
| dc.description (描述) | 94971011 | zh_TW |
| dc.description (描述) | 97 | zh_TW |
| dc.description.abstract (摘要) | A*(A-Star)演算法透過啟發函式，以減少路徑搜尋過程中所需要計算的網路數量，SMA*(Simplified Memory Bounded A-Star)為A*之變形，目前最廣泛被應用於GPS導航系統之路徑規劃的演算法。尋找路徑的計算過程中，A*與SMA*演算法利用中間節點與目的地的方向(直線距離)作為啟發函式，以預估中間節點到目的地之路徑長度挑選優先搜尋的路段，而SMA*則因記憶體的限制會排除預估長度較長的路段，以減少搜尋的路段數量與記憶體之使用量。當起點與終點中存在障礙地形時或路段較崎嶇時，以方向導引路徑搜尋之準確度便大幅降低，導致A*與SMA*之搜尋數量增加，SMA*甚至會得到較差的路徑。主幹導引式最短路徑搜尋演算法(Backbone Orientation)以骨幹路徑導引路徑之搜尋，在障礙地形或道路崎嶇的情況下，可有效避免SMA*之缺點，效能較佳。主幹導引式最短路徑搜尋演算法分為二階段，先由原始路網中提取骨幹路網，並計算出最佳骨幹路徑，再利用骨幹路徑引導路徑的搜尋，在骨幹路徑的一定範圍內搜尋最短路徑。本研究以台灣地區2007年之平面路網圖進行實驗，以三種不同的實驗方式進行實驗，以驗證主幹導引式最短路徑搜尋演算法之效能，證明在SMA*演算法之啟發函式效能低落時，使用主幹導引式最短路徑搜尋演算法可以有效的改善SMA*在障礙地形之效能不彰的問題。 | zh_TW |
| dc.description.tableofcontents | 第一章 簡介 11.1. 簡介 11.1.1. 最短路徑問題(shortest path problem) 11.1.2. 導航系統 31.1.3. 導航系統中之路徑規劃 41.2. 研究動機與目的 61.3. 最短路徑問題(SHORTEST PATH PROBLEM) 61.3.1. 問題類型 7(a) 固定起點 (Single source shortest path problem) 7(b) 固定終點(Single destination shortest path problem) 7(c) 固定起點到固定終點(Single pair shortest path problem) 7(d) 任意起點到任意終點(All pair shortest path problem) 71.3.2. 最短路徑演算法之類型 71.4. 主幹導引式最短路徑搜尋法 (骨幹路線導引法) 81.5. 論文架構 8第二章 背景與相關研究 92.1. 最短路徑問題與現有解法 92.2. 最短路徑搜尋法(SHORTEST PATH ALGORITHMS) 92.2.1. 最佳解演算法 102.2.1.1. Dijkstra 演算法 112.2.1.2. Bellman-Ford 演算法 112.2.1.3. A*(A-Star)演算法 122.2.2. 次佳解演算法 132.2.2.1. 啟發式演算法(algorithmic heuristic) 142.2.2.2. 搜尋式演算法(Search based algorithm) 162.3. 現有演算法問題分析 172.4. 小結 18第三章 主幹導引式最短路徑搜尋演算法(骨幹路線導引法) 203.1. 設計理念 203.2. 細部設計 213.2.1.1. 骨幹路網提取(Backbone graph extraction) 213.2.1.2. 骨幹路網之最短路徑計算(Shortest path in Backbone graph) 243.2.1.3. 初始路徑 (Initial solution) 253.2.1.4. 建立候選路網(Canonical graph extraction) 263.2.1.5. 最終路徑搜尋(Final solution) 283.3. 演算法虛擬碼 29第四章 實驗與效能評估 304.1. 實驗評估指標 304.2. 實驗環境 304.2.1. 實驗工具 314.2.1.1. 案例產生 344.2.1.2. 案例測試器 344.3. 實驗一 (手動設定起/終點 一般地形) 344.3.1. 實驗目標 344.3.2. 實驗結果與分析 344.3.3. 小結 384.4. 實驗二 (手動設定起/終點 障礙地形) 384.4.1. 實驗目標 384.4.2. 實驗結果與分析 394.4.3. 小結 434.5. 實驗三 (大量隨機測試) 444.5.1. 實驗目標 444.5.2. 實驗結果分析 444.5.3. 小結 474.6. 實驗總結 47第五章 結論 495.1. 總結 495.2. 後續研究 50參考文獻 52 | zh_TW |
| dc.language.iso | en_US | - |
| dc.source.uri (資料來源) | http://thesis.lib.nccu.edu.tw/record/#G0094971011 | en_US |
| dc.subject (關鍵詞) | 主幹導引 | zh_TW |
| dc.subject (關鍵詞) | 路徑規劃 | zh_TW |
| dc.subject (關鍵詞) | 最短路徑演算法 | zh_TW |
| dc.subject (關鍵詞) | 導航系統 | zh_TW |
| dc.subject (關鍵詞) | backbone orientation | en_US |
| dc.subject (關鍵詞) | route planning | en_US |
| dc.subject (關鍵詞) | shortest path algorithm | en_US |
| dc.subject (關鍵詞) | Navigation system | en_US |
| dc.title (題名) | 主幹導引式最短路徑搜尋演算法 | zh_TW |
| dc.title (題名) | A Heuristics shortest path algorithm by backbone orientation | en_US |
| dc.type (資料類型) | thesis | en |
| dc.relation.reference (參考文獻) | [1] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi, “Complexity and Approximation”, Springer, ISBN-13 978-3540654315, 2003. | zh_TW |
| dc.relation.reference (參考文獻) | [2] Richard Bellman, “On a Routing Problem”, Quarterly of Applied Mathematics, 16(1), 1958, p.p. 87-90. | zh_TW |
| dc.relation.reference (參考文獻) | [3] Thomas H. Cormen, Charle E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms (Second Edition), ISBN 0-262-03293-7, 2001, p.p. 525-681. | zh_TW |
| dc.relation.reference (參考文獻) | [4] Thomas H. Cormen, Charle E. Leiserson, Ronald L. Rivest and Clifford Stein, “Chapter 16: Greedy Algorithms”, Introduction to Algorithms (Second Edition), 2001, p.p. 525-681, ISBN 0-262-03293-7. | zh_TW |
| dc.relation.reference (參考文獻) | [5] Rina Dechter and Judea Pearl, “Generalized best-first search strategies and the optimality of A*”, Journal of the ACM (JACM), Volume 32, Issue 3, July-1985, p.p. 505–536. | zh_TW |
| dc.relation.reference (參考文獻) | [6] E.W. Dijkstra, “A Note on Two Problems in Connexion with Graphs”, Numerische Mathematlk l, 1959, p.p. 269 – 271. | zh_TW |
| dc.relation.reference (參考文獻) | [7] Robert W. Floyd, “Algorithm 97: Shortest Path”, Communications of the ACM 5 (6), 1997, p.p. 345. | zh_TW |
| dc.relation.reference (參考文獻) | [8] L. R. Ford and F.-Delbert Ray, “Flows in Networks”, Princeton University Press, 1962. | zh_TW |
| dc.relation.reference (參考文獻) | [9] Fred Glover, “Tabu search: A Tutorial”, Center for Applied Artifical Intelligence University of Colorado Boulder, 1990. | zh_TW |
| dc.relation.reference (參考文獻) | [10] Donald B. Johnson, “Efficient algorithms for shortest paths in sparse networks”, Journal of the ACM 24 (1), 1977, p.p. 1–13. | zh_TW |
| dc.relation.reference (參考文獻) | [11] K. Mohajer, Mutapcic A., and Emami M., “Estimation-pruning (EP) algorithm for point-to-point travel cost minimization in a non-FIFO dynamic network”, Intelligent Transportation Systems, 2003. Proceedings. 2003 IEEE, Volume 2, Issue , 12-15, 2003, p.p. 1257 – 1262. | zh_TW |
| dc.relation.reference (參考文獻) | [12] Judea Pearl, Heuristics, Addison-Wesley Pub. ISBN 0-20-105594-5, April-1984. | zh_TW |
| dc.relation.reference (參考文獻) | [13] Stuart Russell and Peter Norvig,” Upper Saddle River, NJ: Prentice Hall”, Artificial Intelligence:A Modern Approach (2nd ed.) , ISBN 0-13-790395-2, 2003, p.p. 111-114. | zh_TW |
| dc.relation.reference (參考文獻) | [14] Sartaj Sahni, “Shortest Paths and Transitive Closure”, Fundamentals of Data Structures in C, p.p. 6-42, ISBN957-22-1713-5, 1994. | zh_TW |
| dc.relation.reference (參考文獻) | [15] Anthony Stentz, “Optimal and Efficient Path Planning for Partially-Known Environments”, Proceedings of the IEEE International Conference on Robotics and Automation (ICRA `94), May-1994, p.p. 3310-3317. | zh_TW |
| dc.relation.reference (參考文獻) | [16] Anthony Stentz, “The Focussed D* Algorithm for Real-Time Replanning”, In Proceedings of the International Joint Conference on Artificial Intelligence, 1995. | zh_TW |
| dc.relation.reference (參考文獻) | [17] Anthony Stentz, “Optimal and efficient path planning for partially-known environments”, In Proceedings of IEEE International Conference on Robotics and Automation, May-1994, ISBN 0-8186-5330-2, 8-13-May-1994, p.p. 3310-3317 vol.4. | zh_TW |
| dc.relation.reference (參考文獻) | [18] Steven R. Strom, “Charting a Course Toward Global Navigation”, http://www.aerospace.org/publications/crosslink/summer2002/01.html, Retrive at 12-28-2008. | zh_TW |
| dc.relation.reference (參考文獻) | [19] Nathan Sturtevant and Michael Buro, “Partial Pathfinding Using Map Abstraction and Refinement”, In Proceedings of AAAI, 2005, p.p. 47–52. | zh_TW |
| dc.relation.reference (參考文獻) | [20] George Taylor, “Line Simplification Algorithm”, http://www.comp.glam.ac.uk/pages/staff/getaylor/papers/lcwin.PDF, 1995. Retrive at 01-21-2009. | zh_TW |
| dc.relation.reference (參考文獻) | [21] Stephen Warshall, “A theorem on Boolean matrices”, Journal of the ACM 9 (1), January-1962, p.p. 11–12. | zh_TW |
| dc.relation.reference (參考文獻) | [22] F. Benjamin Zhan and Charle E. Noon, “Shortest Path Algorithms: An Evaluation Using Real Road Networks”, Transportation Science, 1996, Vol.32, p.p 65-73. | zh_TW |
| dc.relation.reference (參考文獻) | [23] 付梦印, 李杰, 邓志紅, “限制搜索区域的距离最短路径规划算法”, 北京理工大學學報, Vol.24 No.10, October-2004. | zh_TW |
| dc.relation.reference (參考文獻) | [24] 吳泰熙, 張欽智, “以禁忌搜尋法則求解推銷員旅行問題”, Journal of Da-Yeh University, Vol.6, No.1, 1997, p.p. 87-99. | zh_TW |
| dc.relation.reference (參考文獻) | [25] 張文贏, 蕭飛賓, 許棟龍, “多目標巡視之飛行路徑規劃研究”, 國立成功大學航太系-96年度博士畢業論文, 2007. | zh_TW |
| dc.relation.reference (參考文獻) | [26] 賴建銘, 尹邦嚴, 徐熊健, “以禁制搜尋演算法建構最大概率條件演化樹”, 國立暨南大學資管所, 2003. | zh_TW |
| dc.relation.reference (參考文獻) | [27] “Bellman-Ford algorithm”, http://en.wikipedia.org/wiki/Bellman-Ford_algorithm, Retrieved at 12-25-2008. | zh_TW |
| dc.relation.reference (參考文獻) | [28] “Breadth-first search”, http://en.wikipedia.org/wiki/Breadth-first_search, Retrieved at 12-25-2008. | zh_TW |
| dc.relation.reference (參考文獻) | [29] “Depth-first search”, http://en.wikipedia.org/wiki/Depth-first_search, Retrieved at 12-25-2008. | zh_TW |
| dc.relation.reference (參考文獻) | [30] “Dijkstra`s algorithm”, http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm, Retrieved at 12-25-2008. | zh_TW |
| dc.relation.reference (參考文獻) | [31] “Simulated annealing”, http://en.wikipedia.org/wiki/Simulated_annealing, Retrieved at 12-25-2008. | zh_TW |
