본 논문은 실시간 GPS 항법시스템에서 최단경로 탐색에 일반적으로 적용되고 있는 Dijkstra 알고리즘의 수행 복잡도 $O(n^2)$을 선형인 O(n)으로 단축시킬 수 있는 알고리즘을 제안하였다. Dijkstra 알고리즘은 출발 노드부터 시작하여 모든 노드를 방문하여 최소 경로 길이를 계산한다. 따라서 "노드 수 -1"회를 수행하야 하기 때문에 복잡한 도로로 구성된 도시에서 실시간으로 최단경로 정보를 제공할 수 없는 경우도 발생한다. 제안된 알고리즘은 먼저, 그래프를 트리로, 출발 노드를 근 노드로 치환하여 트리의 각 레벨에 해당하는 외부근방 (Out-Neighbourhood) 노드 집합을 구성하고, 외부근방간과 외부근방 내부의 최소 경로 길이를 계산하는 방법을 적용하였다. 제안된 알고리즘을 양방향과 일방통행로로 구성된 복잡한 2개 그래프에 대해 알고리즘을 적용한 결과 Dijkstra 알고리즘과 동일하게 모든 노드의 최소 경로 길이를 얻는데 성공하였다. 또한, 알고리즘 수행속도를 "노드 수 -1"회에서 "레벨 수 -1"회로 약 4배 정도 단축시키는 효과를 얻었다. 제안된 알고리즘을 GPS실시간 시스템에 적용하여 러시아워나 차량 사고로 인한 병목현상이 발생하였을 때, 최단 경로 우회 도로 정보를 실시간으로 제공할 수 있다면 운전자의 만족도를 크기 향상시킬 수 있을 것이다.
본 논문은 실시간 GPS 항법시스템에서 최단경로 탐색에 일반적으로 적용되고 있는 Dijkstra 알고리즘의 수행 복잡도 $O(n^2)$을 선형인 O(n)으로 단축시킬 수 있는 알고리즘을 제안하였다. Dijkstra 알고리즘은 출발 노드부터 시작하여 모든 노드를 방문하여 최소 경로 길이를 계산한다. 따라서 "노드 수 -1"회를 수행하야 하기 때문에 복잡한 도로로 구성된 도시에서 실시간으로 최단경로 정보를 제공할 수 없는 경우도 발생한다. 제안된 알고리즘은 먼저, 그래프를 트리로, 출발 노드를 근 노드로 치환하여 트리의 각 레벨에 해당하는 외부근방 (Out-Neighbourhood) 노드 집합을 구성하고, 외부근방간과 외부근방 내부의 최소 경로 길이를 계산하는 방법을 적용하였다. 제안된 알고리즘을 양방향과 일방통행로로 구성된 복잡한 2개 그래프에 대해 알고리즘을 적용한 결과 Dijkstra 알고리즘과 동일하게 모든 노드의 최소 경로 길이를 얻는데 성공하였다. 또한, 알고리즘 수행속도를 "노드 수 -1"회에서 "레벨 수 -1"회로 약 4배 정도 단축시키는 효과를 얻었다. 제안된 알고리즘을 GPS 실시간 시스템에 적용하여 러시아워나 차량 사고로 인한 병목현상이 발생하였을 때, 최단 경로 우회 도로 정보를 실시간으로 제공할 수 있다면 운전자의 만족도를 크기 향상시킬 수 있을 것이다.
This paper suggests an algorithm that can shorten the complexity $O(n^2)$ of Dijkstra algorithm that is applied to the shortest path searching in real-time GPS Navigation System into an up-to-date O(n). Dijkstra algorithm manipulates the distance of the minimum length path by visiting all...
This paper suggests an algorithm that can shorten the complexity $O(n^2)$ of Dijkstra algorithm that is applied to the shortest path searching in real-time GPS Navigation System into an up-to-date O(n). Dijkstra algorithm manipulates the distance of the minimum length path by visiting all the nodes from the starting node. Hence, it has one disadvantage of not being able to provide the information on the shortest path every second, in a city that consists of sophisticated roads, since it has to execute number of node minus 1. The suggested algorithm, firstly, runs by means of organizing the set of out-neighbourhood nodes at each level of the tree, and root node for departure node. It also uses a method of manipulating the distance of the minimum path of all out-neighborhoods and interior of the out-neighborhoods. On applying the suggested algorithm to two sophisticated graphs consisted of bi-direction and uni-direction, we have succeeded to obtain the distance of the minimum length path, just as same as Dijkstra algorithm. In addition, it has an effect of shortening the time taken 4 times from number of node minus1 to number of level minus 1. The satisfaction of the drivers can be increased by providing the information on shortest path of detour, every second, when occurs any rush hour or any traffic congestion due to car accident, by applying this suggested algorithm to the real-time GPS system.
This paper suggests an algorithm that can shorten the complexity $O(n^2)$ of Dijkstra algorithm that is applied to the shortest path searching in real-time GPS Navigation System into an up-to-date O(n). Dijkstra algorithm manipulates the distance of the minimum length path by visiting all the nodes from the starting node. Hence, it has one disadvantage of not being able to provide the information on the shortest path every second, in a city that consists of sophisticated roads, since it has to execute number of node minus 1. The suggested algorithm, firstly, runs by means of organizing the set of out-neighbourhood nodes at each level of the tree, and root node for departure node. It also uses a method of manipulating the distance of the minimum path of all out-neighborhoods and interior of the out-neighborhoods. On applying the suggested algorithm to two sophisticated graphs consisted of bi-direction and uni-direction, we have succeeded to obtain the distance of the minimum length path, just as same as Dijkstra algorithm. In addition, it has an effect of shortening the time taken 4 times from number of node minus1 to number of level minus 1. The satisfaction of the drivers can be increased by providing the information on shortest path of detour, every second, when occurs any rush hour or any traffic congestion due to car accident, by applying this suggested algorithm to the real-time GPS system.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
노드 “1”에서 출발하여 노드 “20”에 도착하는 최단경로를 찾고자 한다.
본 논문에서는 실시간 GPS 항법 시스템에 일반적으로 적용되고 있는 Dijkstra 알고리즘의 문제점을 고찰해 보고 새로운 최단경로 탐색 알고리즘을 제안하였다. Dijkstra 알고리즘은 방향 그래프에 대해 출발 노드에서 다른 모든 노드로의 최단경로를 찾는데 성공할 수 있으나 알고리즘이 복잡하고 수행속도가 느린 것이 단점으로 지적되고 있다.
본 논문은 수행 복잡도를 선형에 가까운 최단 경로를 탐색하는 알고리즘을 제안한다. 제안된 알고리즘은 그래프를 트리로, 출발 노드를 근 노드로 하여, 인접한 외부근방 (Out-Neighbourhood) 노드 집합을 레벨로 구성하고 레벨과 레벨간 (Inter-level) 노드의 최소 경로 길이와 동일 레벨에 존재하는 노드들 간 (Intra-level)의 최소 경로 길이를 계산하는 방식으로 알고리즘 수행 복잡도는 O(l×n)으로 단축시킬 수 있었다.
지금까지는 최단 경로 탐색 복잡도를 선형으로 할 수 있는 알고리즘 개발이 미해결 과제로 남아 있다. 본 논문은 이 문제를 해결하는 알고리즘을 제안하였다.
제안 방법
두 번째로 pth 외부근방 집합에 대해 레벨 간 (Inter-Level N+(p)(s)→N+(p+1)) 최소 경로 길이를 계산한 후, 레벨 내부 (Intra-Level, N+(p+1)→N+(p+1))에 대한 최소 경로 길이를 계산하여 경로 길이를 갱신한다.
제안된 알고리즘은 먼저 방향그래프의 모든 노드에 대해 외부근방 집합을 탐색하고 이들 레벨 집합간 (Inter-level) 인접 호와 집합 내부 (Intra-level)의 인접 호들에 대해 최소 경로 길이를 계산하는 방식을 택하여 알고리즘 복잡도를 선형에 가깝도록 단축시킬 수 있었다. 제안된 알고리즘을 2개 그래프에 적용한 결과 Dijkstra 알고리즘과 동일하게 출발 노드에서 모든 노드로의 최소 경로 길이와 호들을 선택할 수 있었으며, 수행 횟수를 약 4배 정도 단축시킬 수 있었다.
성능/효과
그래프에 레벨 단위 최단경로 알고리즘을 적용한 과정은 각각 표 3과 표 4에 제시되어 있다. 2개 그래프 모두에서 레벨 단위 최단경로 알고리즘은 Dijkstra 알고리즘과 동일하게 모든 노드의 최소 경로 길이와 PSP를 얻는데 성공하였다. 그러나 알고리즘 수행 복잡도는 O(n2)에서 O(l × n)으로 단축시킬 수 있었으며, 수행속도는 Dijkstra 알고리즘은 G1과 G2에서 각각 “노드 수 -1 (n - 1)회”인 23회와 29회를 수행하는데 반해, 레벨 단위 최단경로 알고리즘은 각각 “레벨 수 -1 (l - 1)회”인 6회와 8회로 단축시킬 수 있었다.
결국 제안된 알고리즘의 복잡도는 O(n) + O(n) = O(n)으로 선형이 됨을 알 수 있다.
이와 같은 결과가 나타난 이유는 Dijkstra 알고리즘은 목적지까지 도달하기 위해 중간 과정에서 경유하는 모든 노드에 대한 최단경로길이를 찾는 방법인데 반해, 제안된 방법은 레벨 단위로 해당 레벨에서의 최단경로 한 지점만에 연결된 다음 레벨의 노드들만을 탐색하여 중간 목적지로 결정하기 때문이다. 결국, 실시간으로 정보를 제공해야 하는 GPS 항법 시스템일 경우 목적지까지의 최단경로를 찾는 시간은 제안된 알고리즘이 Dijkstra 알고리즘에 비해 엄청나게 빠른 결과를 나타내 사용자의 만족도를 크게 향상시킬 수 있을 것이다.
그러나 알고리즘 수행 복잡도는 O(n2)에서 O(l × n)으로 단축시킬 수 있었으며, 수행속도는 Dijkstra 알고리즘은 G1과 G2에서 각각 “노드 수 -1 (n - 1)회”인 23회와 29회를 수행하는데 반해, 레벨 단위 최단경로 알고리즘은 각각 “레벨 수 -1 (l - 1)회”인 6회와 8회로 단축시킬 수 있었다.
제안된 알고리즘은 그래프를 트리로, 출발 노드를 근 노드로 하여, 인접한 외부근방 (Out-Neighbourhood) 노드 집합을 레벨로 구성하고 레벨과 레벨간 (Inter-level) 노드의 최소 경로 길이와 동일 레벨에 존재하는 노드들 간 (Intra-level)의 최소 경로 길이를 계산하는 방식으로 알고리즘 수행 복잡도는 O(l×n)으로 단축시킬 수 있었다.
제안된 알고리즘은 먼저 방향그래프의 모든 노드에 대해 외부근방 집합을 탐색하고 이들 레벨 집합간 (Inter-level) 인접 호와 집합 내부 (Intra-level)의 인접 호들에 대해 최소 경로 길이를 계산하는 방식을 택하여 알고리즘 복잡도를 선형에 가깝도록 단축시킬 수 있었다. 제안된 알고리즘을 2개 그래프에 적용한 결과 Dijkstra 알고리즘과 동일하게 출발 노드에서 모든 노드로의 최소 경로 길이와 호들을 선택할 수 있었으며, 수행 횟수를 약 4배 정도 단축시킬 수 있었다.
후속연구
본 논문에서는 2개의 실제 그래프에 대한 최단경로 탐색을 이론적으로 고찰하였으며, 실제 GPS 항법 시스템에 적용하여 실시간으로 탐색 정보를 제공할 수 있는 실용성을 검증하지는 못하였다. 따라서 추후 실제 GPS 시스템에 적용하여 얼마나 빨리 최단경로를 탐색하여 고객 만족도를 향상시킬 수 있는지 검증하고자 한다.
본 논문에서는 2개의 실제 그래프에 대한 최단경로 탐색을 이론적으로 고찰하였으며, 실제 GPS 항법 시스템에 적용하여 실시간으로 탐색 정보를 제공할 수 있는 실용성을 검증하지는 못하였다. 따라서 추후 실제 GPS 시스템에 적용하여 얼마나 빨리 최단경로를 탐색하여 고객 만족도를 향상시킬 수 있는지 검증하고자 한다.
질의응답
핵심어
질문
논문에서 추출한 답변
실시간 GPS 항법 시스템 어떤 시스템인가?
최근 실시간 GPS 항법 시스템 (Real Time GPS Navigation System)에 방향 그래프 (Digraph)의 최단경로 (SP, Shortest Path)를 구하는 Dijkstra 알고리즘이 일반적으로 적용되고 있다.[1] 실시간 GPS 항법 시스템은 운전자에게 자신의 현재 위치를 화면상에 지정하고, 목적지를 결정하면 최단경로 (시간 또는 경로)를 결정하여 화면상에 표시해주고 운전자가 길을 따라가도록 유도하는 시스템이다. 최단경로를 찾는 알고리즘은 Dijkstra, Bellman Ford, Topological Ordering과 A-Star(A*) 등이 있다.
실시간 GPS 항법 시스템에 사용되는 알고리즘은 무엇인가?
최근 실시간 GPS 항법 시스템 (Real Time GPS Navigation System)에 방향 그래프 (Digraph)의 최단경로 (SP, Shortest Path)를 구하는 Dijkstra 알고리즘이 일반적으로 적용되고 있다.[1] 실시간 GPS 항법 시스템은 운전자에게 자신의 현재 위치를 화면상에 지정하고, 목적지를 결정하면 최단경로 (시간 또는 경로)를 결정하여 화면상에 표시해주고 운전자가 길을 따라가도록 유도하는 시스템이다.
Dijkstra 알고리즘은 무슨 이유 때문에 n-1번의 수행을 하게 되는가?
Dijkstra 알고리즘은 “특정 노드로부터 시작하여 인접 노드의 최소 경로 길이를 계산하고 최소 경로 길이를 갖는 노드를 한번에 하나씩 선택하는 방식”으로, 특정 노드에 인접한 노드들과 이전에 계산된 노드들의 경로의 합이 최소가 되는 노드를 찾는다. 이 과정을 출발 노드로부터 시작하여 모든 노드들을 방문하는 최단경로를 찾기 때문에 n-1번 수행된다. 이는 Prim의 최소신장트리 (MST, Minimum Spanning Tree)를 찾는 알고리즘[11]과 유사한 방법이다.
참고문헌 (12)
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.
J. Bang-Jensen and G. Gutin, "Digraphs: Theory, Algorithms and Applications," Springer-Verlag, London, 2006.
Wikipedia, "Glossary of Graph Theory," http://en.wikipedia.org/wiki/Glossary_of_grapg_theory, Wikimedia Foundation Inc., 2007.
WWL. Chen, "Discrete Mathematics," Department of Mathematics, Division of ICS, Macquarie University, Australia, http://www.maths.mq.edu.au/-wchen/lndmfolder/lndm.html, 2003.
R. C. Prim, "Shortest Connection Networks and Some Generalisations," Bell System Technical Journal, Vol. 36, pp. 1389-1401, 1957.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.