臺灣博碩士論文加值系統

摘要
路徑長度和轉彎次數是運輸和航海交通工具的主要成本因素。路徑越長則所需時間越久，而每次轉彎必須減速因而也會增加時間成本。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.