1. NCCU Academic Hub
  2. 學術產出
  3. College of Informatics
  4. Theses
  5. Item

學術產出-Theses

Article View/Open

Publication Export

Google ScholarTM

政大圖書館

Citation Infomation

  • No doi shows Citation Infomation
題名 主幹導引式最短路徑搜尋演算法
A Heuristics shortest path algorithm by backbone orientation
作者 林啟榮
Lin, Chi Jung
貢獻者 連耀南
Lien, Yao Nan
林啟榮
Lin, Chi Jung
關鍵詞 主幹導引
路徑規劃
最短路徑演算法
導航系統
backbone orientation
route planning
shortest path algorithm
Navigation system
日期 2008
上傳時間 11-Sep-2009 16:03:53 (UTC+8)
摘要 A*(A-Star)演算法透過啟發函式，以減少路徑搜尋過程中所需要計算的網路數量，SMA*(Simplified Memory Bounded A-Star)為A*之變形，目前最廣泛被應用於GPS導航系統之路徑規劃的演算法。尋找路徑的計算過程中，A*與SMA*演算法利用中間節點與目的地的方向(直線距離)作為啟發函式，以預估中間節點到目的地之路徑長度挑選優先搜尋的路段，而SMA*則因記憶體的限制會排除預估長度較長的路段，以減少搜尋的路段數量與記憶體之使用量。當起點與終點中存在障礙地形時或路段較崎嶇時，以方向導引路徑搜尋之準確度便大幅降低，導致A*與SMA*之搜尋數量增加，SMA*甚至會得到較差的路徑。

主幹導引式最短路徑搜尋演算法(Backbone Orientation)以骨幹路徑導引路徑之搜尋，在障礙地形或道路崎嶇的情況下，可有效避免SMA*之缺點，效能較佳。主幹導引式最短路徑搜尋演算法分為二階段，先由原始路網中提取骨幹路網，並計算出最佳骨幹路徑，再利用骨幹路徑引導路徑的搜尋，在骨幹路徑的一定範圍內搜尋最短路徑。

本研究以台灣地區2007年之平面路網圖進行實驗，以三種不同的實驗方式進行實驗，以驗證主幹導引式最短路徑搜尋演算法之效能，證明在SMA*演算法之啟發函式效能低落時，使用主幹導引式最短路徑搜尋演算法可以有效的改善SMA*在障礙地形之效能不彰的問題。
參考文獻 [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.
描述 碩士
國立政治大學
資訊科學學系
94971011
97
資料來源 http://thesis.lib.nccu.edu.tw/record/#G0094971011
資料類型 thesis
dc.contributor.advisor 連耀南zh_TW
dc.contributor.advisor Lien, Yao Nanen_US
dc.contributor.author (Authors) 林啟榮zh_TW
dc.contributor.author (Authors) Lin, Chi Jungen_US
dc.creator (作者) 林啟榮zh_TW
dc.creator (作者) Lin, Chi Jungen_US
dc.date (日期) 2008en_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) G0094971011en_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 (描述) 94971011zh_TW
dc.description (描述) 97zh_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 第一章 簡介 1
1.1. 簡介 1
1.1.1. 最短路徑問題(shortest path problem) 1
1.1.2. 導航系統 3
1.1.3. 導航系統中之路徑規劃 4
1.2. 研究動機與目的 6
1.3. 最短路徑問題(SHORTEST PATH PROBLEM) 6
1.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) 7
1.3.2. 最短路徑演算法之類型 7
1.4. 主幹導引式最短路徑搜尋法 (骨幹路線導引法) 8
1.5. 論文架構 8
第二章 背景與相關研究 9
2.1. 最短路徑問題與現有解法 9
2.2. 最短路徑搜尋法(SHORTEST PATH ALGORITHMS) 9
2.2.1. 最佳解演算法 10
2.2.1.1. Dijkstra 演算法 11
2.2.1.2. Bellman-Ford 演算法 11
2.2.1.3. A*(A-Star)演算法 12
2.2.2. 次佳解演算法 13
2.2.2.1. 啟發式演算法(algorithmic heuristic) 14
2.2.2.2. 搜尋式演算法(Search based algorithm) 16
2.3. 現有演算法問題分析 17
2.4. 小結 18
第三章 主幹導引式最短路徑搜尋演算法(骨幹路線導引法) 20
3.1. 設計理念 20
3.2. 細部設計 21
3.2.1.1. 骨幹路網提取(Backbone graph extraction) 21
3.2.1.2. 骨幹路網之最短路徑計算(Shortest path in Backbone graph) 24
3.2.1.3. 初始路徑 (Initial solution) 25
3.2.1.4. 建立候選路網(Canonical graph extraction) 26
3.2.1.5. 最終路徑搜尋(Final solution) 28
3.3. 演算法虛擬碼 29
第四章 實驗與效能評估 30
4.1. 實驗評估指標 30
4.2. 實驗環境 30
4.2.1. 實驗工具 31
4.2.1.1. 案例產生 34
4.2.1.2. 案例測試器 34
4.3. 實驗一 (手動設定起/終點 一般地形) 34
4.3.1. 實驗目標 34
4.3.2. 實驗結果與分析 34
4.3.3. 小結 38
4.4. 實驗二 (手動設定起/終點 障礙地形) 38
4.4.1. 實驗目標 38
4.4.2. 實驗結果與分析 39
4.4.3. 小結 43
4.5. 實驗三 (大量隨機測試) 44
4.5.1. 實驗目標 44
4.5.2. 實驗結果分析 44
4.5.3. 小結 47
4.6. 實驗總結 47
第五章 結論 49
5.1. 總結 49
5.2. 後續研究 50
參考文獻 52		zh_TW
dc.language.iso en_US-
dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0094971011en_US
dc.subject (關鍵詞) 主幹導引zh_TW
dc.subject (關鍵詞) 路徑規劃zh_TW
dc.subject (關鍵詞) 最短路徑演算法zh_TW
dc.subject (關鍵詞) 導航系統zh_TW
dc.subject (關鍵詞) backbone orientationen_US
dc.subject (關鍵詞) route planningen_US
dc.subject (關鍵詞) shortest path algorithmen_US
dc.subject (關鍵詞) Navigation systemen_US
dc.title (題名) 主幹導引式最短路徑搜尋演算法zh_TW
dc.title (題名) A Heuristics shortest path algorithm by backbone orientationen_US
dc.type (資料類型) thesisen
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