# 臺灣博碩士論文加值系統

(44.201.72.250) 您好！臺灣時間：2023/10/02 11:42

:::

### 詳目顯示

:

• 被引用:4
• 點閱:553
• 評分:
• 下載:0
• 書目收藏:1
 摘要 路徑長度和轉彎次數是運輸和航海交通工具的主要成本因素。路徑越長則所需時間越久，而每次轉彎必須減速因而也會增加時間成本。Lee所提出的路徑連接演算法一直被廣泛應用在地理資訊系統(geographical information system, GIS)，或印刷電路板佈線與積體電路元件配置的研究問題上，用以尋求最短路徑。然而，一條最佳的路徑不應只考慮距離長短，轉彎次數也是一項不可忽略的因素。但是在搜尋時同時考慮兩個以上參數的路徑搜尋演算法，眾所週知是一個NP-complete的問題，因此我們使用線性組合的方式將兩個參數結合為一個參數。 本論文應用類似Lee演算法的觀念，提出最少轉彎路徑演算法，用以在網格圖上尋找最少轉彎路徑，另一方面，我們結合了Kirby所提出的虛擬網路以及Ahuja等人所改進的Dijkstra演算法發展而成的最小成本演算法，可在網格圖及網狀架構上，尋找最小成本路徑，兩者的時間複雜度皆為O(N)，而N為網格總數或節點總數。 關鍵詞：最短路徑、網格圖、Lee演算法、Dijkstra演算法、 NP-complete problem
 Abstract A path with minimum turns is important for transportation planning, as turns usually incur extra cost, be it time or fuel. In this thesis, we first propose a minimum-turn path-finding algorithm capable of finding a path with minimum turns in rectangular grids. However, a path with minimum turns may not always be desirable, since decreasing the number of turns usually means increasing the path length. Also, an algorithm for finding a minimum-cost path considering simultaneously two or more factors is, by nature, an NP-complete problem. We solve the minimum-cost path-finding problem with a two-stage approach. First, we use Kirby’s pseudo-network to reconstruct a mesh. This transforms the mesh into a directed graph. Then, we adopt a modified, thus, more efficient, Dijkstra’s algorithm to find the minimum-cost path. Both path-finding algorithms developed in this thesis achieve O(N) time complexity and are optimal as well. Keywords: Shortest path, mesh, Lee’s shortest path connection algorithm, Dijkstra’s algorithm, minimum-cost path algorithm, minimum-turn path algorithm.
 目錄 圖目錄………………………………………………………….… vi 演算法目錄……………………………………………………….v 第一章 緒論………………………………………………………1 1-1簡介……………………………………………………..1 1-2研究背景與目的……..……………….………………...2 1-3主要貢獻……..…………………………………………2 1-4論文編排方式…………………………………………..3 第二章 空間資料結構與Lee演算法…………………………4 2-1網格圖…………………….…………………………….4 2-2向量圖…….…………………………………………….5 2-3網格圖與向量圖的優缺點比較……………………….5 2-4 Lee最短路徑演算法……………………………………7 第三章 最少轉彎路徑演算法…………………….………….11 3-1資料結構……………………………………………….11 3-2最少轉彎路徑演算法………………………………….12 3-3最少轉彎路徑演算法的正確性及時間複雜度………16 3-3-1最少轉彎路徑演算法的正確性……………….16 3-3-2最少轉彎路徑演算法的時間複雜度………….17 第四章 最小成本路徑演算法…………………….………….19 4-1資料結構………………………………………………19 4-2 Dijkstra最短路徑演算法……………………………..22 4-3最小成本路徑演算法…………………………………23 4-3最小成本路徑演算法的正確性及時間複雜度………16 4-3-1最小成本路徑演算法的正確性……………….24 4-3-2最小成本路徑演算法的時間複雜度………….25 4-4最小成本路徑演算法之參數調整…………………....26 4-5最小成本路徑演算法於運輸網路之實例應用……....29 第五章 結論與未來發展………………………..……….……30 參考文獻……………………………....……………….…………31 圖目錄 圖2-1 網格圖的組成方式………………….………………....4 圖2-2 網格圖之相鄰關係…………………………………….5 圖2-3 網格圖與mesh的對應圖……………………………...7 圖2-4 路徑規劃的範例……….………………………..10 圖3-1 最少轉彎路徑演算法的 網格資料結構示意圖…………………………..…….12 圖3-2 計算最少轉彎數的方法……………………………...13 圖3-3 最少轉彎路徑………………………………………...24 圖4-1 最小成本路徑演算法的節點資料結構示意圖………20 圖4-2 共享後的節點資料結構示意圖…………..…………21 圖4-3 轉彎一次所需耗費的成本為前進一格的6倍之最小成本路徑……………………………………..…40 圖4-4 搜尋最少轉彎路徑的範例…………………………. 27 圖4-5 搜尋最短路徑的範例…..……………………………28 圖4-6 最小成本路徑演算法的應用實例………….……….29 演算法目錄 Algorithm:Lee Shortest Path Connection Algorithm ………8 Function:Counting_Turns(Ci,j, neighbor)…………………………….14 Function:Update(Ci,j, neighbor)………………………………………14 Algorithm:最少轉彎路徑演算法………………………………15 Algorithm:Dijkstra(G,w,s)……………………………………………22 Algorithm:最小成本路徑演算法……………………………………24
 參考文獻[1] R. K. Ahuja, K. Mehlhorn, J. B. Orlin, and Robert E.Tarjan, “Faster algorithms for the shortest path problem,” Journal of ACM, vol. 37, pp. 213-223, 1990.[2] R. Bellmanl, “On a routing problem,” Quarterly of Applied Mathematics, 16(1), pp. 87-90, 1958.[3] T. Caldwell, “On finding minimum routes in a network with turn penalties,” Comm. of ACM, 4, pp. 107-108, 1961.[4] D. Z. Chen and K. S. Klenk, “Rectilinear Short Path Queries Among Rectangular Obstacles,” Information Processing Letters 57, pp. 313-319, 1996.[5] L. Chen, “Optimal Computation of Shortest Paths on Doubly Convex Bipartite Graphs,” in Proc. International Conference on Parallel and Distributed Systems, pp. 618-623, 1997.[6] C. H. Chung and G. N. Saridis, “Path Planning for an Intelligent Robot by the Extended VGraph Algorithm,” in Proc. IEEE International Symposium on Intelligent Control, pp. 544-549, 1989.[7] E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numerische Mathematik, vol. 1, pp. 508-517, 1993.[8] L. R. Ford, Jr. and D. R. Fulkerson, Flows in Networks, Princeton University Press, 1962.[9] M. R. Garey and D. S. Johnson, Computer and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979.[10] J. Hershberger and S. Suri, “Efficient Computation of Euclidean Shortest Paths in the Plane,” in Proc. IEEE 34th Annual Symposium on Foundations of Computer Science, pp. 508-517, 1993.[11] K. Jiang, L. S. Seneviratne, and S. W. E. Earles, “Finding the 3D Shortest Path with Visibility Graph and Minimum Potential Energy,” in Proc. IEE/RSJ International Conference on Intelligent Robots and Systems, vol. 1, pp.679-684, 1993.[12] K. Jiang, L. S. Seneviratne, and S. W. E. Earles, “3D Shortest Path Planning in the Presence of Polyhedral Obstacles,” in Proc. IEEE International Conference on Systems, Man and Cybernetics, vol. 5, pp. 206-211, 1993.[13] S. Jun and K. G. Shin, “Shortest Path Planning with Dominance Relation,” in Proc. IEEE International Conference on Robotics and Automation, vol. 1, pp. 138-143, 1990.[14] E. Jungert and P. D. Holmes, “A Knowledge-based Approach to the Shortest Path Problem in a Digitized Map,” in Proc. IEEE Workshop on Visual Languages, pp. 248-255, 1988.[15] R. F. Kirby and R. B. Potts, “The Minimum Route Problem for Networks with Turn Penalties and Prohibitions,” Transportation Research, vol.3, pp.397-408, 1969.[16] C. Y. Lee, “An Algorithm for Path Connections and Its Applications,” IRE Trans. Electron. Computer, vol. EC-10, pp. 346- 365, Sept. 1961.[17] B. V. Martin, F. W. Memmott, and A. J. Bone, “Principles and techniques of predicting future demand for urban area transportation,” M.I.T. Rep. No.3, 1961.[18] F. Rubin, “The Lee path connection algorithm,” IEEE Trans. Computers, vol. 9, pp. 907-914, Sept. 1974.[19] Y. Saab and M. VanPutte, “Shortest Path Planning on Topographical Maps,” IEEE Trans. System, Man. and Cybernetics, vol. 29, No. 1, pp.139-150, Jan. 1999.[20] G. Tan, G. Li, D. Chen, and X. Cui, “Detection of Collision and Interference Between 3D Objects Using Normal Vector,” Conference of Vehicle Electronics, vol. 1, pp. 286-289, 1999.[21] K. R. Varadarajan and P. K. Agarwal, “Approximating Shortest Paths on a Nonconvex Polyhedron,” 38th Annual Symposium on Foundations of Computer Science, pp. 182-191, 1997.[22] Y. Xia, “Skeletonization Via the Realization of the Fire Front’s Propagation and Extinction in Digital Binary Shapes,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 11, No. 10, pp. 1076-1086, Oct. 1989.[23] S. Q. Zheng, J. S. Lim, and S. S. Iyengar, “Finding Obstacle -avoiding Shortest Paths Using Implicit Connection Graphs,” IEEE Trans. Computer-aided Design of Integrated Circuits and Systems, vol. 15, No. 1, pp.103-110, Jan. 1996.
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 1 船舶避障航路規劃之自動化模組研發 2 地理資訊系統於電子海圖避障航路規劃之模式開發 3 三維彎管自動化佈置之研究 4 電子海圖上最短路徑搜尋及其應用

 無相關期刊

 1 網狀網路上可容錯之直線式史坦納樹試誤型演算法 2 四元樹和金字塔的陣列嵌入、佈局與傳繞 3 三度空間與二次曲面之最短路徑規劃及動態追截 4 四元樹之凸包新解 5 快速預估方位演算法於三維空間寬頻訊號追蹤之應用 6 DS/CDMA編碼之分析與接收機之改善 7 電腦視覺與直流無刷馬達控制整合之桿上球系統研究 8 噴墨印表機列印系統之模式建立與參數判別 9 微波單石積體電路中平面式電感器與場效電晶體之製作 10 一般化彼得森圖形之探討與新圖形Y 11 2048位元RSA加解密系統實作 12 快速雙菱形位移估測演算法應用於即時動態影像編碼系統 13 以DSP模組實現全數位鎖相迴路應用於水下QPSK系統之載波回復 14 使用分碼多工、編碼、和分集技術以改善衛星接收機之效能 15 使用時域有限差分法模擬數位電路電磁干擾問題

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室