A* 알고리즘의 최단경로 탐색 정확도 향상을 위한 역방향 적용방법에 관한 연구 A Study on A* Algorithm Applying Reversed Direction Method for High Accuracy of the Shortest Path Searching원문보기
Dijkstar 알고리즘에 기초하는 최단경로 탐색 알고리즘의 탐색속도 향상에 관한 많은 연구들이 지속되어 왔다. 그 대표적인 알고리즘이 $A^*$ 알고리즘이다. 빠른 탐색속도는 $A^*$ 알고리즘의 장점이지만, 복잡하고 불규칙한 가로 네트워크에서 실제의 최단경로 탐색이 실패할 확률이 높다. 탐색실패란 목적노드를 탐색하지 못한 경우와 최단경로가 아닌 경로를 구축하는 것을 의미한다. 본 연구는 $A^*$ 알고리즘의 최단경로 탐색 성공확률을 높이기 위한 방법으로 일차적으로 출발노드와 목적노드 간 연결 관계를 정리하고, 목적노드에서 출발노드까지 정리된 경로에 따라 $A^*$ 알고리즘을 역으로 적용한 것이다. 이 방법은 네트워크 및 경로 부하량 특성에 따라 실제의 최단경로가 아닌 경로를 최단경로로 구축하는 경우가 발생할 수는 있으나, 경로구축의 완전한 실패는 발생시키지 않는다. 이 방법을 실제 복잡한 네트워크에 적용하여 유효성을 검증한 결과, 통상적인 $A^*$ 알고리즘의 적용보다 탐색 소요시간은 약간 증가하나, 정확성은 상당히 높아지는 것으로 분석되었다.
Dijkstar 알고리즘에 기초하는 최단경로 탐색 알고리즘의 탐색속도 향상에 관한 많은 연구들이 지속되어 왔다. 그 대표적인 알고리즘이 $A^*$ 알고리즘이다. 빠른 탐색속도는 $A^*$ 알고리즘의 장점이지만, 복잡하고 불규칙한 가로 네트워크에서 실제의 최단경로 탐색이 실패할 확률이 높다. 탐색실패란 목적노드를 탐색하지 못한 경우와 최단경로가 아닌 경로를 구축하는 것을 의미한다. 본 연구는 $A^*$ 알고리즘의 최단경로 탐색 성공확률을 높이기 위한 방법으로 일차적으로 출발노드와 목적노드 간 연결 관계를 정리하고, 목적노드에서 출발노드까지 정리된 경로에 따라 $A^*$ 알고리즘을 역으로 적용한 것이다. 이 방법은 네트워크 및 경로 부하량 특성에 따라 실제의 최단경로가 아닌 경로를 최단경로로 구축하는 경우가 발생할 수는 있으나, 경로구축의 완전한 실패는 발생시키지 않는다. 이 방법을 실제 복잡한 네트워크에 적용하여 유효성을 검증한 결과, 통상적인 $A^*$ 알고리즘의 적용보다 탐색 소요시간은 약간 증가하나, 정확성은 상당히 높아지는 것으로 분석되었다.
The studies on the shortest path algorithms based on Dijkstra algorithm has been done continuously to decrease the time for searching. $A^*$ algorithm is the most represented one. Although fast searching speed is the major point of $A^*$ algorithm, there are high rates of faili...
The studies on the shortest path algorithms based on Dijkstra algorithm has been done continuously to decrease the time for searching. $A^*$ algorithm is the most represented one. Although fast searching speed is the major point of $A^*$ algorithm, there are high rates of failing in search of the shortest path, because of complex and irregular networks. The failure of the search means that it either did not find the target node, or found the shortest path, witch is not true. This study proposed $A^*$ algorithm applying method that can reduce searching failure rates, preferentially organizing the relations between the starting node and the targeting node, and appling it in reverse according to the organized path. This proposed method may not build exactly the shortest path, but the entire failure in search of th path would not occur. Following the developed algorithm tested in a real complex networks, it revealed that this algorithm increases the amount of time than the usual $A^*$ algorithm, but the accuracy rates of the shortest paths built is very high.
The studies on the shortest path algorithms based on Dijkstra algorithm has been done continuously to decrease the time for searching. $A^*$ algorithm is the most represented one. Although fast searching speed is the major point of $A^*$ algorithm, there are high rates of failing in search of the shortest path, because of complex and irregular networks. The failure of the search means that it either did not find the target node, or found the shortest path, witch is not true. This study proposed $A^*$ algorithm applying method that can reduce searching failure rates, preferentially organizing the relations between the starting node and the targeting node, and appling it in reverse according to the organized path. This proposed method may not build exactly the shortest path, but the entire failure in search of th path would not occur. Following the developed algorithm tested in a real complex networks, it revealed that this algorithm increases the amount of time than the usual $A^*$ algorithm, but the accuracy rates of the shortest paths built is very high.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 연구에서는 A* 알고리즘 적용방법을 개선하여 탐색 실패확률을 감소시키고, 탐색 소요시간을 최소화 하는 방법 제시하는 것을 목적으로 한다.
본 연구에서는 이와 같은 A* 알고리즘의 낮은 정확도를 높이기 위하여 A* 알고리즘을 역방향으로 적용하는 방법을 제시하였다.
제안 방법
1. 개발방향
개발하는 방법은 A* 알고리즘의 장점인 짧은 시간의 탐색을 크게 후퇴시키지 않으면서 최단경로 탐색 실패확률을 줄이는 방법이다.
개발한 방법의 효율성 검증은 최단경로 탐색의 정확성에 초점을 두는데, 정확성의 향상이 너무 많은 탐색 시간을 요하게 되면 이 방법의 적용 효과가 반감될 수 있으므로 탐색시간도 검증항목으로 하였다.
효율성 검증을 위한 최단경로 탐색 수는 전체 노드간의 최단경로 15,750(126 × 126 －126)개로 하였다. 그리고 출발노드와 목적노드까지 2㎞의 직선거리 단위로 구분하여 비교하였다.
효율성 검증은 정확성과 소요시간, 두 개의 항목에 대해 기존 알고리즘과의 탐색결과를 비교하는 것으로 하였다. 비교대상 알고리즘은 A* 알고리즘과 최근 100% 정확성을 가지는 것으로 개발된 최소 기대 부하량을 이용한 알고리즘[4]으로 하였다.
효율성 검증은 정확성과 소요시간, 두 개의 항목에 대해 기존 알고리즘과의 탐색결과를 비교하는 것으로 하였다. 비교대상 알고리즘은 A* 알고리즘과 최근 100% 정확성을 가지는 것으로 개발된 최소 기대 부하량을 이용한 알고리즘[4]으로 하였다.
대상 데이터
대상 네트워크는 결과비교를 보다 객관적으로 하기 위하여 최소 기대 부하량을 이용한 알고리즘 개발시 적용한 네트워크와 부하량을 그대로 하였다.
성능/효과
15,750개의 최단경로를 찾는 전체 소요시간을 보면 A* 알고리즘이 2.00E-04 ms, 최소 기대 부하량을 이용한 알고리즘은 6.00E-06 ms로 측정된 반면 본 연구에서 개발한 A* 알고리즘의 역방향 적용 방법은 3.29E-03 ms로 측정되었다.
개발한 방법 또한 통상의 A* 알고리즘의 적용결과와 같이 복수개의 경로 중에서 부하량이 높아도 노드수가 적은 경로를 최단경로로 선택할 확률은 가지고 있다. 차후, 이와 같은 약점을 극복할 수 있는 연구가 계속되어야 할 것이다.
결과적으로 높은 정확도를 비교적 빠른 탐색속도로 탐색하기 위해서는 A* 알고리즘을 그대로 적용하기 보다 본 연구에서 개발한 A* 알고리즘의 역방향 적용 방법을 이용하는 것이 효과적일 것으로 판단한다.
규칙적이지 못하고 복잡한 대구 간선가로 네트워크를 이용하여 효율성을 검증한 결과, 통상의 A* 알고리즘 보다 월등히 높은 정확도를 가지는 것으로 분석되었다.
노드간 직선거리가 길어질수록 탐색소요시간은 길어지는 경향을 나타내는데, A* 알고리즘과 본 연구에서 개발한 방법의 연구결과에서는 직선거리와 소요시간이 비례하지 않은 결과도 나타났다. 이는 소수의 성공 경로를 가진 경우, 그리고 대상 네트워크가 그리드 형태의 규칙적 가로가 아니고 복잡하며, 거리는 가깝지 않으나 부하량이 적은 순환선 등의 영향이 크기 때문이다.
대상 네트워크가 규칙적이지 않으면서 복잡하고, 부하량인 소요시간도 가로 길이에 비례적이지 못한 것 등의 요인으로 인해 A* 알고리즘의 완벽한 성공 확률은 출발노드와 목적노드간의 길이가 멀면 멀수록 저하하는 것으로 나타났다.
본 연구에서 개발한 A* 알고리즘의 역방향 적용 방법은 A* 알고리즘에 비하여 약간의 탐색 소요시간이 증가하나, 높은 정확성을 가지는 것으로 확인되었으므로 효율성을 가지는 것으로 판단된다.
본 연구에서 개발한 A* 알고리즘의 역방향 적용 방법은 A* 알고리즘의 정확성보다 월등히 높은 정확도를 가지는 것으로 분석되었다.
본 연구에서 개발한 방법의 효율성은 기존 A* 알고리즘보다 정확도가 높으면서, 정확도를 목표로 한 최소 기대 부하량을 이용한 알고리즘보다 빠른 탐색이 가능하다면 효율성을 가지는 것으로 판단할 수 있다.
최단경로 탐색소요시간은 통상의 A* 알고리즘 보다 약간 증가하였으나, 100% 정확도를 위해 개발된 알고리즘에 비해서는 상당히 빠른 탐색소요시간을 가지는 것으로 분석되었다.
하나의 경로탐색에 대한 평균 소요시간은 A* 알고리즘이 1.09E-08 ms, 최소 기대 부하량을 이용한 알고리즘이 3.64E-06 ms로 측정되었고, 본 연구에서 개발한 방법은 2.09E-07 ms로 측정되었다.
효율성 평가에서 정확성은 실제 최단경로를 정확히 구축한 경우를 성공으로 하고, 완벽한 최단경로가 아니거나, 아예 경로를 구축하지 못한 경우 모두를 실패로 보았다.
후속연구
알고리즘의 정확도를 높이기 위한 연구들은 수행되었고, 정확도도 높였다[4, 5]. 그러나 정확도가 높을수록 탐색 속도가 감소하는 결과를 초래하므로, 최단경로 정확도의 향상과 함께 탐색 소요시간을 최소화할 수 있는 알고리즘의 연구가 필요하다.
알고리즘의 적용결과와 같이 복수개의 경로 중에서 부하량이 높아도 노드수가 적은 경로를 최단경로로 선택할 확률은 가지고 있다. 차후, 이와 같은 약점을 극복할 수 있는 연구가 계속되어야 할 것이다.
질의응답
핵심어
질문
논문에서 추출한 답변
Dijkstra 알고리즘은 어떠한 알고리즘에 기초로 사용되는가?
하나의 출발지에서 하나의 목적지를 탐색(One to One Search)하는 최단경로 탐색 알고리즘은 Dijkstra 알고리즘[1]에 기초를 두고 있으며, 현재까지도 많이 활용하고 있다.
Dijkstra 알고리즘의 단점 해소하는 세 가지 방법은?
주요 3가지 방법은 출발노드와 목적노드에서 양방향으로 최단경로를 탐색하는 양방향 탐색법(Bidirectional Search), 소요시간 단축을 위하여 정확한 최단경로의 구축이 아니라 적정 수준에서의 최단경로 구축을 목적으로 하는 휴리스틱 탐색법(Heuristic Search), 그리고 출발노드와 목적노드가 멀리 떨어진 경우 주로 사용하는 네트워크 계층구분법(Hierarchical Methods) 등 이다.
탐색실패란 무엇인가?
빠른 탐색속도는 $A^*$ 알고리즘의 장점이지만, 복잡하고 불규칙한 가로 네트워크에서 실제의 최단경로 탐색이 실패할 확률이 높다. 탐색실패란 목적노드를 탐색하지 못한 경우와 최단경로가 아닌 경로를 구축하는 것을 의미한다. 본 연구는 $A^*$ 알고리즘의 최단경로 탐색 성공확률을 높이기 위한 방법으로 일차적으로 출발노드와 목적노드 간 연결 관계를 정리하고, 목적노드에서 출발노드까지 정리된 경로에 따라 $A^*$ 알고리즘을 역으로 적용한 것이다.
참고문헌 (8)
E. W. DIJKSTRA, "A Note on Two Problems in Connexion with Graphs", Numerische Mathematik1, pp.269-271, 1959.
L. Fu and D. Sun and L. R. Rilett, "Heuristic shortest path algorithms for transportation applications: State of the art", Computers & Operations vol. 33, no. 11, pp.3324-3343, 2006.
W. Dorothea and W. Thomas, "Speed-Up Techniques for Shortest-Path Computations", STACS 2007, Lecture Notes in Computer Science, vol. 4393, pp.22-36, 2007.
Y. G. Ryu, "Development of a shortest path searching algorithm using minimum expected weights", The journal of The Korea Institute of Intelligent Transport Systems, vol. 12, no 5, pp.36-45, 2013.
P. E. Hart and N. J. Nilsson and B. Raphael, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths", IEEE Transactions on Systems Science and Cybernetics, vol. 4, no. 2, pp.100-107, 1968.
Y. G. Ryu, "Development of shortest path searching network reduction algorithm", The journal of The Korea Institute of Intelligent Transport Systems, vol. 12, no. 2, pp.12-21, 2013.
Y. G. Ryu, "A Study on the Forecasting of Bus Travel Demand and the Method of Determining Optimal Bus Network", Ph. D. Thesis, Yeong Nam University, pp.131-140, 1996.
AI-Helper
※ AI-Helper는 부적절한 답변을 할 수 있습니다.