본 논문은 실시간 GPS 항법시스템에서 최단 경로를 탐색하는데 일반적으로 적용되고 있는 Dijkstra 알고리즘의 문제점을 개선한 알고리즘을 제안하였다. Dijkstra 알고리즘은 출발 노드부터 시작하여 그래프의 모든 노드에 대한 최단 경로를 결정하기 때문에 일반적으로 노드의 수 - 1회를 수행해야 하며, 알고리즘 수행에 많은 메모리가 요구된다. 따라서 Dijkstra 알고리즘은 복잡한 도시의 도로에서 목적지 까지 최단 경로를 탐색하여 실시간으로 정보를 제공하지 못할 수도 있다. 이러한 문제점을 해결하고자, 본 논문에서는 먼저 출발과 목적지 노드를 제외한 경로 노드들의 최단 경로 (유입과 유출 최소 가중치 호 선택)를 결정하고, 출발 노드부터 시작하여 노드 유출 호들에 대해 경로 노드의 최단 경로와 일치하는 호들을 모두 선택하는 방식으로 한번에 다수의 노드들을 탐색하는 방법을 택하였다. 14개의 다양한 방향 그래프에 제안된 알고리즘을 적용한 결과 모두 최단 경로를 탐색하는데 성공하였다. 또한, 수행 속도 측면에서 Dijkstra 알고리즘보다 2배에서 3배 정도 빠른 결과를 얻었으며, 알고리즘 수행에 필요한 메모리도 적게 요구되었다.
본 논문은 실시간 GPS 항법시스템에서 최단 경로를 탐색하는데 일반적으로 적용되고 있는 Dijkstra 알고리즘의 문제점을 개선한 알고리즘을 제안하였다. Dijkstra 알고리즘은 출발 노드부터 시작하여 그래프의 모든 노드에 대한 최단 경로를 결정하기 때문에 일반적으로 노드의 수 - 1회를 수행해야 하며, 알고리즘 수행에 많은 메모리가 요구된다. 따라서 Dijkstra 알고리즘은 복잡한 도시의 도로에서 목적지 까지 최단 경로를 탐색하여 실시간으로 정보를 제공하지 못할 수도 있다. 이러한 문제점을 해결하고자, 본 논문에서는 먼저 출발과 목적지 노드를 제외한 경로 노드들의 최단 경로 (유입과 유출 최소 가중치 호 선택)를 결정하고, 출발 노드부터 시작하여 노드 유출 호들에 대해 경로 노드의 최단 경로와 일치하는 호들을 모두 선택하는 방식으로 한번에 다수의 노드들을 탐색하는 방법을 택하였다. 14개의 다양한 방향 그래프에 제안된 알고리즘을 적용한 결과 모두 최단 경로를 탐색하는데 성공하였다. 또한, 수행 속도 측면에서 Dijkstra 알고리즘보다 2배에서 3배 정도 빠른 결과를 얻었으며, 알고리즘 수행에 필요한 메모리도 적게 요구되었다.
This paper suggests an algorithm that improves the disadvantages of the Dijkstra algorithm that is commonly used in GPS navigation system, searching for the shortest path. Dijkstra algorithm, first of all, requires much memory for the performance of the algorithm. It has to carry out number of node ...
This paper suggests an algorithm that improves the disadvantages of the Dijkstra algorithm that is commonly used in GPS navigation system, searching for the shortest path. Dijkstra algorithm, first of all, requires much memory for the performance of the algorithm. It has to carry out number of node minus 1, since it determines the shortest path from all the nodes in the graph, starting from the first node. Therefore, Dijkstra algorithm might not be able to provide the information on every second, searching for the shortest path between the roads of the congested city and the destination. In order to solve these problems, this paper chooses a method of searching a number of nodes at once by means of choosing the shortest path of all the path nodes (select of minimum weight arc in-degree and out-degree), excluding the departure and destination nodes, and of choosing all the arcs that coincide with the shortest path of the path nodes, from all the node outgoing arcs starting from the departure node. On applying the suggested algorithm to 14 various digraphs, we succeeded to search the shortest path. In addition, the result was obtained at the speed of 2 to 3 times faster than that of Dijkstra algorithm, and the memory required was less than that of Dijkstra algorithm.
This paper suggests an algorithm that improves the disadvantages of the Dijkstra algorithm that is commonly used in GPS navigation system, searching for the shortest path. Dijkstra algorithm, first of all, requires much memory for the performance of the algorithm. It has to carry out number of node minus 1, since it determines the shortest path from all the nodes in the graph, starting from the first node. Therefore, Dijkstra algorithm might not be able to provide the information on every second, searching for the shortest path between the roads of the congested city and the destination. In order to solve these problems, this paper chooses a method of searching a number of nodes at once by means of choosing the shortest path of all the path nodes (select of minimum weight arc in-degree and out-degree), excluding the departure and destination nodes, and of choosing all the arcs that coincide with the shortest path of the path nodes, from all the node outgoing arcs starting from the departure node. On applying the suggested algorithm to 14 various digraphs, we succeeded to search the shortest path. In addition, the result was obtained at the speed of 2 to 3 times faster than that of Dijkstra algorithm, and the memory required was less than that of Dijkstra algorithm.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 논문에서는 방향 그래프의 최단 경로 탐색 알고리즘을 고찰하였다. 그러나 실제 도시의 도로는 모두 양방향 통행이 가능할 수도 있다.
본 논문에서는 실시간 GPS 항법 시스템에 일반적으로 적용되고 있는 Dijkstra SP 알고리즘의 문제점을 고찰해보고 새로운 최단 경로 탐색 알고리즘을 제안하였다. Dijkstra SP 알고리즘은 출발 노드부터 시작하여 모든 노드들을 한 번에 하나씩 방문하는 방법으로 알고리즘 수행속도가 느린 단점이 있다.
본 논문은 그래프의 크기가 클 경우라도 적은 메모리 용량을 필요로 하면서도 간단한 수행 횟수로 최단 경로를 찾는 알고리즘을 제안한다. 2장에서는 Dijkstra SP 알고리즘의 최단 경로를 찾는 과정을 고찰해 보고 문제점을 살펴본다.
본 절에서는 그림 &과 같이 12개 그래프를 대상으로 Sulee SP 알고리즘의 적용성을 평가해 본다. 와 G, 그래프는 Chen[12], G3, 65, 伝 와 Gl:i 그래프는 Ikeda[13], G4 그래프는 Wenger[14], G6 그래프는 Dewellyn[9], G8 그래프는 BoydE15], G10 그래프는 Orlin[16], Gn 그래프는 Coleman[17], G12 그래프는 Walker[18]에서 인용되었다.
제안 방법
본 절에서는 그림 19의 G14 그래프를 대상으로 Sulee SP 알고리즘의 적용성을 평가해 본다. Gu그래프는 Lee[19]에서 인용되었으며, 출발 노드 “1”로부터 목적지 노드 “30” 까지 최단경로를 탐색하고자 한다.
이러한 단점을 보완하기 위해, 제안된 알고리즘은 한번에 하나의 노드를 탐색하지 않고 한번에 다수의 노드를 탐색하는 방법을 취하였다. 세부적으로는 출발과 목적지 노드가 설정되었을 때 경로 노드에 대해 유출과 유입되는 최소 가중치 호를 사전에 설정하고, 출발 노드부터 시작하여 연결된 호들에 대해 사전에 결정된 최소 가중치 호와 일치하는 호의 노드들을 모두 방문하는 방법을 택하였다. 14개의 다양한 방향 그래프에 대해 제안된 알고리즘을 적용한 결과 모두 최단경로를 탐색하는데 성공하였으며, Dijkstra SP 알고리즘에 비해 2배에서 3배 정도 알고리즘이 빨리 종료되는 효과를 얻었다.
따라서 복잡한 도시의 경우 실시간으로 최단 경로를 탐색하여 정보를 제공하지 못할 수도 있다. 이러한 단점을 보완하기 위해, 제안된 알고리즘은 한번에 하나의 노드를 탐색하지 않고 한번에 다수의 노드를 탐색하는 방법을 취하였다. 세부적으로는 출발과 목적지 노드가 설정되었을 때 경로 노드에 대해 유출과 유입되는 최소 가중치 호를 사전에 설정하고, 출발 노드부터 시작하여 연결된 호들에 대해 사전에 결정된 최소 가중치 호와 일치하는 호의 노드들을 모두 방문하는 방법을 택하였다.
이론/모형
방향그래프의 점대점 최단거리를 빠르게 찾는 제안된 알고리즘을 "Sulee SP 알고리즘”이라 하자. 먼저, 그래프의 노드들을 그림 3과 같이 S, P, 尸。와。의 4 그룹으로 분류한다.
그림 2의 그래프에 대해 Dijkstra SP 알고리즘[5]을 적용하여 보자. G] 그래프는 Llewellyn[9]에서 인용되었으며, »=10, 〃= 14인 그래프로 출발 노드는 목적지 노드는(D 이다.
노드 최소 가중치 호 선택”은 Boruvka MST 알고리즘 [10, 11]을 간선형한 형태를 적용한다. 이와 같이 하는 이유는 각 경로 노드들의 유입과 유출 최소 가중치 호들로 경로를 설정하여 출발에서 목적지 노드까지 경로 단절 없이 최단 경로를 갖도록 하기 위함이다.
성능/효과
세부적으로는 출발과 목적지 노드가 설정되었을 때 경로 노드에 대해 유출과 유입되는 최소 가중치 호를 사전에 설정하고, 출발 노드부터 시작하여 연결된 호들에 대해 사전에 결정된 최소 가중치 호와 일치하는 호의 노드들을 모두 방문하는 방법을 택하였다. 14개의 다양한 방향 그래프에 대해 제안된 알고리즘을 적용한 결과 모두 최단경로를 탐색하는데 성공하였으며, Dijkstra SP 알고리즘에 비해 2배에서 3배 정도 알고리즘이 빨리 종료되는 효과를 얻었다. 따라서 제안된 알고리즘을 실시간 GPS 항법 시스템의 최단 경로 탐색에 적용하면 고객의 만족도를 향상시킬 수 있을 것이다.
GPS 최단거리 탐색 알고리즘에서, 그래프의 크기에 따라 Bellman Ford 알고리즘은 Dijkstra 알고리즘보다 많은 시간이 소요되지만 좋은 결과를 얻을 수 있다. Topological Ordering 알고리즘은 선형 시간대에 최단 경로를 찾을 수 있지만 최적의 경로를 찾지 못할 수도 있다.
결과는 표 5에 제시하였다. Sulee SP 알고리즘은 Dijkstra SP 알고리즘에 비해 동일한 SP를 얻으면서, 평균적으로 알고리즘 수행 횟수를 약 2배 단축시키는 효과를 얻었다. 또한, 그래프의 노드수가 큰 G”는 약 3배 정도 알고리즘이 빨리 수행됨을 알 수 있다.
결론적으로, Sulee SP 알고리즘은 13개 그래프 모두에서 문제점 없이 SP를 얻는데 모두 성공하였다. 그러나 Dijkstra SP 알고리즘은 과 Gn 그래프에서 알고리즘 적용에 약간의 문제가 발생하였다.
Dijkstra SP 알고리즘과 Sulee SP 알고리즘을 적용한 결과는 그림 20에 제시되어 있다. 알고리즘 적용 결과 동일한 경로를 탐색하였으며, Dijkstra SP 알고리즘은 29회 수행으로, Sulee SP 알고리즘은 단지 10회 수행으로 최단경로를 탐색하는데 성공하였다.
있다. 알고리즘 적용 결과, Sulee SP 알고리즘은 Dijkstra SP 알고리즘[5]과 동일한 SP 경로를 얻는데 성공하였다. 알고리즘 수행 횟수 측면에서 볼 때, Dijkstra SP 알고리즘[5]은 笈- 1=9 회를 수행한데 비해 Sulee SP 알고리즘은 6회로 단축시킬수 있었으며, 메모리 크기 측면에서도 Sulee SP 알고리즘이 월등히 적은 메모리를 사용함을 알 수 있다.
후속연구
14개의 다양한 방향 그래프에 대해 제안된 알고리즘을 적용한 결과 모두 최단경로를 탐색하는데 성공하였으며, Dijkstra SP 알고리즘에 비해 2배에서 3배 정도 알고리즘이 빨리 종료되는 효과를 얻었다. 따라서 제안된 알고리즘을 실시간 GPS 항법 시스템의 최단 경로 탐색에 적용하면 고객의 만족도를 향상시킬 수 있을 것이다.
양방향 통행이 가능한 도로는 무방향 그래프로 생각할 수 있다. 따라서 추후 무방향 그래프의 최단 경로를 탐색하는 알고리즘을 연구할 계획이다.
참고문헌 (19)
M. Abboud, L. Mariya, A. Jaoude, and Z. Kerbage, 'Real Time GPS Navigation System,' 3rd FEA Student Conference, Department of Electrical and Computer Engineering, American University of Beirut, 2004
T. H. Cormen, C. E. Leserson, R. L. Rivest, and C. Stein, 'Introduction to Algorithms,' 2nd Edition, MIT Press and McGraw-Hill, 2001
E. W. Dijkstra, 'A Note on Two Problems in Connection with Graphs,' Numerische Mathematik, Vol. 1, pp. 269-271, 1959
Wikipedia, 'Dijkstra's Algorithm,' http://en.wikipedia.org/wiki/Dijkstra_algorithm, Wikimedia Foundation Inc., 2007
J. Misra, 'A Walk Over the Shortest Path: Dijkstra's Algorithm Viewed as Fixed-Point Computation,' Department of Computer Science, University of Texas at Austin, USA, 2000
Y. T. Lim and H. M. Kim, 'A Shortest Path Algorithm for Real Road Network Based on Path Overlap,' Department of Civil Engineering, Institute of Transportation Studies, University of California, Irvine, USA, http://www.its.uci.edu/hyunmyuk/library/ (2005) 20EAST(k-path).pdf, 2005
F. B. Zhan, 'Three Fatest Shortest Path Algorithms on Real Road Networks: Data Structures and Procedures,' Journal of Geographic Informaton and Decision Analysis, Vol. 1, No.1, pp. 69-82, 1997
R. C. Prim, 'Shortest Connection Networks and Some Generalisations,' Bell System Technical Journal, Vol. 36, pp. 1389-1401, 1957
M. Llewellyn, 'COP 3503: Computer Science II Introduction to Graphs,' http://www.cs.ucf.edu/ courses/cop3503/ summer04, 2004
O. Boruvka, 'O Jistem Problemu Minimalnim,' Prace Mor. Prrodved. Spol. V Brne (Acta Societ. Natur. Moravicae), Vol. III, No.3, pp. 37-58, 1926
J. Nesetril, E. Milkova, and H. Nesetrilova, 'Otakar Boruvka on Minimum Spanning Tree Problem (Translation of the both 1926 Papers, Comments, History),' DMATH: Discrete Mathematics, Vol. 233, 2001
WWL. Chen, 'Discrete Mathematics,' Department of Mathematics, Division of ICS, Macquarie University, Australia, http://www.maths.mq.edu.au/~wchen/lndmfolder/lndm.html, 2003
K. Ikeda, 'Mathematical Programming,' Dept. Information Science and Intelligent Systems, The University of Tokushima, http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/maxflow/MaxflowApp. shtml. 2005
R. Wenger, 'CIS 780: Analysis of Algorithms,' http://www.cse.ohio-state.edu/~wenger/cis780/shortest_path.pdf, 2004
S. Boyd, 'Applications of Combinational Optimization: Optimal Paths and Trees,' http://www.site.uottawa.ca/~sylvia/csi5166web/5166tespg26to61.pdf, School of Information Technology and Engineering (SITE), University of Ottawa, Canada, 2005
J. B. Orlin, 'Network Optimization: Dijkstra's Algorithm for the Shortest Path Problem,' http://www.mit.edu/~jorlin/15.082/Lectures/05Dijkstra.ppt, MIT, 2003
R. Coleman, 'CS 221: Data Structures,' Computer Science, University of Alabama in Huntsville, 2002
D. Walker, 'COS 226: Algorithms and Data Structures,' Department of Computer Science, Princeton University, http://www.cs.princeton.edu/ courses/ archi ve/fall04/ cos226/lectures/ shortest-path.pdf, 2004
K. S. Lee, 'Shortest Path Algorithm' http://www.geocities.com/lekinsengl/
※ AI-Helper는 부적절한 답변을 할 수 있습니다.