Author: Joonhee Lim
Date: 2022/07/25
논문 원문: https://iopscience.iop.org/article/10.1088/1742-6596/1566/1/012061/pdf
참고한 글: https://kangworld.tistory.com/61
0. Abstract
최단 경로 문제를 해결하기 위해 우리는 보통 Dijkstra 또는 A* 알고리즘을 사용한다. 이 두 가지 알고리즘은 라우팅 또는 도로 네트워크에 자주 사용된다. 이 논문의 목표는 이 최단 경로 문제를 해결하기 위한 두 알고리즘을 비교하는 것이다. 본 연구에서는 Dijkstra와 A*가 Town 또는 Regional scale 지도를 푸는 데 사용할 때는 거의 동일한 성능을 보이지만, 대규모 축척 지도를 푸는 데 사용할 때는 A*가 더 낫다는 결과를 보인다.
1. Introdunction
한 지점(시작점)에서 다른 위치(끝점)로 가는 경로를 요청할 때 보통 나오는 결과가 시작점에서 목적지점까지의 '최단 경로'다. 좀 더 공식적으로 표현하면, 꼭짓점이 에지에 의해 결합되고 각 에지가 값 또는 비용을 갖는 그래프에서, 두 꼭짓점 사이에서 가장 낮은 비용 경로를 찾는 문제이다. 본 논문에서는 Dijkstra의 알고리즘과 A* 알고리즘을 비교하여 최단 경로 문제를 해결할 것이다.
2. Method
1) 다익스트라 알고리즘
1. 출발지점을 설정
2. 출발지점에서 이동가능한 노드로의 이동 후 거리 기입
3. 가장 가까운 노드로 이동 후 이동가능한 노드로의 이동 후 최단거리 기입
4. 대충 이런 느낌으로 반복
2) A* 알고리즘
A* 알고리즘은 시작 노드부터 현재 노드까지의 비용을 g(n), 현재 노드에서 목표 노드까지의 예상 비용을 h(n)이라 할 때, 이 두 값을 더한 f(n) = g(n) + h(n)이 가장 최소가 되는 노드를 다음 탐색 노드로 선정한다.
h(n)=0이라고 가정하면 다익스트라 알고리즘과 똑같이 움직인다.
출발지점에서 가장 작은 f(n)을 가진 노드를 찾아가고 다시 주변 노드의 f(n)을 계산하고 찾아가고 계산하는 과정을 반복하면 목표 노드에 도착할 수 있다.
간단 요약
BFS : 가중치 없는 그래프, 시작 노드 기준으로 모든 노드의 최단 경로 구함, 완전 탐색
다익스트라 : 가중치 그래프, 시작 노드 기준으로 모든 노드의 최단 경로 구함, 그리디 알고리즘
A* : 가중치 그래프, 시작 노드에서 목표 노드까지의 최단 경로만을 구하려 함, 그리디 알고리즘
3. Results and Discussions
Dijkstra와 A*가 Town 또는 Regional scale 지도를 푸는 데 사용할 때는 거의 동일한 성능을 보이지만, 대규모 축척 지도를 푸는 데 사용할 때는 A*가 더 낫다는 결과를 보인다. (Loop가 적게 들어 계산 시간 감소)
-> 모든 노드의 최단경로를 구하는 다익스트라보다 목적지까지의 최단 거리만을 구하는 A*가 좀 더 빠른 것 같다.
