政大機構典藏-National Chengchi University Institutional Repository(NCCUR):Item 140.119/29688

政大典藏 > College of Informatics > Department of Computer Science > Theses > Item 140.119/29688

Please use this identifier to cite or link to this item: https://nccur.lib.nccu.edu.tw/handle/140.119/29688

Title:	主幹導引式最短路徑搜尋演算法 A Heuristics shortest path algorithm by backbone orientation
Authors:	林啟榮 Lin, Chi Jung
Contributors:	連耀南 Lien, Yao Nan 林啟榮 Lin, Chi Jung
Keywords:	主幹導引路徑規劃最短路徑演算法導航系統 backbone orientation route planning shortest path algorithm Navigation system
Date:	2008
Issue Date:	2009-09-11 16:03:53 (UTC+8)
Abstract:	A(A-Star)演算法透過啟發函式，以減少路徑搜尋過程中所需要計算的網路數量，SMA(Simplified Memory Bounded A-Star)為A之變形，目前最廣泛被應用於GPS導航系統之路徑規劃的演算法。尋找路徑的計算過程中，A與SMA演算法利用中間節點與目的地的方向(直線距離)作為啟發函式，以預估中間節點到目的地之路徑長度挑選優先搜尋的路段，而SMA則因記憶體的限制會排除預估長度較長的路段，以減少搜尋的路段數量與記憶體之使用量。當起點與終點中存在障礙地形時或路段較崎嶇時，以方向導引路徑搜尋之準確度便大幅降低，導致A與SMA之搜尋數量增加，SMA甚至會得到較差的路徑。主幹導引式最短路徑搜尋演算法(Backbone Orientation)以骨幹路徑導引路徑之搜尋，在障礙地形或道路崎嶇的情況下，可有效避免SMA之缺點，效能較佳。主幹導引式最短路徑搜尋演算法分為二階段，先由原始路網中提取骨幹路網，並計算出最佳骨幹路徑，再利用骨幹路徑引導路徑的搜尋，在骨幹路徑的一定範圍內搜尋最短路徑。本研究以台灣地區2007年之平面路網圖進行實驗，以三種不同的實驗方式進行實驗，以驗證主幹導引式最短路徑搜尋演算法之效能，證明在SMA演算法之啟發函式效能低落時，使用主幹導引式最短路徑搜尋演算法可以有效的改善SMA在障礙地形之效能不彰的問題。
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. [2] Richard Bellman, “On a Routing Problem”, Quarterly of Applied Mathematics, 16(1), 1958, p.p. 87-90. [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. [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. [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. [6] E.W. Dijkstra, “A Note on Two Problems in Connexion with Graphs”, Numerische Mathematlk l, 1959, p.p. 269 – 271. [7] Robert W. Floyd, “Algorithm 97: Shortest Path”, Communications of the ACM 5 (6), 1997, p.p. 345. [8] L. R. Ford and F.-Delbert Ray, “Flows in Networks”, Princeton University Press, 1962. [9] Fred Glover, “Tabu search: A Tutorial”, Center for Applied Artifical Intelligence University of Colorado Boulder, 1990. [10] Donald B. Johnson, “Efficient algorithms for shortest paths in sparse networks”, Journal of the ACM 24 (1), 1977, p.p. 1–13. [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. [12] Judea Pearl, Heuristics, Addison-Wesley Pub. ISBN 0-20-105594-5, April-1984. [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. [14] Sartaj Sahni, “Shortest Paths and Transitive Closure”, Fundamentals of Data Structures in C, p.p. 6-42, ISBN957-22-1713-5, 1994. [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. [16] Anthony Stentz, “The Focussed D Algorithm for Real-Time Replanning”, In Proceedings of the International Joint Conference on Artificial Intelligence, 1995. [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. [18] Steven R. Strom, “Charting a Course Toward Global Navigation”, http://www.aerospace.org/publications/crosslink/summer2002/01.html, Retrive at 12-28-2008. [19] Nathan Sturtevant and Michael Buro, “Partial Pathfinding Using Map Abstraction and Refinement”, In Proceedings of AAAI, 2005, p.p. 47–52. [20] George Taylor, “Line Simplification Algorithm”, http://www.comp.glam.ac.uk/pages/staff/getaylor/papers/lcwin.PDF, 1995. Retrive at 01-21-2009. [21] Stephen Warshall, “A theorem on Boolean matrices”, Journal of the ACM 9 (1), January-1962, p.p. 11–12. [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. [23] 付梦印, 李杰, 邓志紅, “限制搜索区域的距离最短路径规划算法”, 北京理工大學學報, Vol.24 No.10, October-2004. [24] 吳泰熙, 張欽智, “以禁忌搜尋法則求解推銷員旅行問題”, Journal of Da-Yeh University, Vol.6, No.1, 1997, p.p. 87-99. [25] 張文贏, 蕭飛賓, 許棟龍, “多目標巡視之飛行路徑規劃研究”, 國立成功大學航太系-96年度博士畢業論文, 2007. [26] 賴建銘, 尹邦嚴, 徐熊健, “以禁制搜尋演算法建構最大概率條件演化樹”, 國立暨南大學資管所, 2003. [27] “Bellman-Ford algorithm”, http://en.wikipedia.org/wiki/Bellman-Ford_algorithm, Retrieved at 12-25-2008. [28] “Breadth-first search”, http://en.wikipedia.org/wiki/Breadth-first_search, Retrieved at 12-25-2008. [29] “Depth-first search”, http://en.wikipedia.org/wiki/Depth-first_search, Retrieved at 12-25-2008. [30] “Dijkstra`s algorithm”, http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm, Retrieved at 12-25-2008. [31] “Simulated annealing”, http://en.wikipedia.org/wiki/Simulated_annealing, Retrieved at 12-25-2008.
Description:	碩士國立政治大學資訊科學學系 94971011 97
Source URI:	http://thesis.lib.nccu.edu.tw/record/#G0094971011
Data Type:	thesis
Appears in Collections:	[Department of Computer Science ] Theses

Files in This Item:

There are no files associated with this item.

社群 sharing

Loading...