기록

A* 알고리즘

주어진 출발점에서 목표지점까지 가는 최단 경로를 찾아내는 그래프 탐색 알고리즘 중 하나이다.

최단 경로를 찾는다는 공통점을 가지지만, A*는 데이크스트라에 휴리스틱(Heuristic)이라는 개념을 추가하여 효율성을 높인 알고리즘이다. 본래 A 알고리즘이라고 불렸지만 적절한 휴리스틱에 따라서 최적의 알고리즘이 되기 때문에 A* 알고리즘이라 불린다.

데이크스트라와 관계

A*알고리즘은 데이크스트라 알고리즘의 확장 버전이라고 볼 수 있다. 데이크스트라에서 사용하는 시작점으로부터의 실제 거리 g(n)에 목표점까지의 예상 거리 h(n)라는 휴리스틱을 더한 값을 우선순위 기준으로 사용한다.

f(n) = g(n) + h(n)

g(n) : 시작점에서 현재 노드 n까지의 실제 비용

h(n) : 현재 노드 n에서 목표 노드 goal까지의 휴리스틱 비용(예상 비용)

f(n) : 시작점에서 n을 거쳐 goal까지 가는 총 예상 비용

휴리스틱 h(n)이 핵심 역할을 하며, 이 값이 얼마나 목표에 가깝게 추정하느냐에 따라서 A*의 효율성이 결정된다.

휴리스틱

가장 대표적으로 사용되는 두 가지 방법으로 맨해튼 거리(Manhattan Distance)와 유클리드 거리(Euclidean Distance)가 있다.

두 가지 방법 모두 특히 격자 기반의 길 찾기 문제나 2D/3D 공간에서의 최단 경로 탐색에 자주 활용된다.

맨해튼 거리(Manhattan Distance)

격자에서 한 점에서 다른 점까지 가로 또는 세로로만 이동할 수 있을 때의 최단 거리를 의미한다. 마치 도시의 블록을 따라 이동하는 것과 같다고 하여 맨해튼 거리 또는 택시 거리라고 불린다.

계산은 두 점 (x1, y1) , (x2, y2)가 있을 때 두 점 사이의 맨해튼 거리는 |x1 - x2| + |y1 - y2|이다.

이동이 수직(상하) 또는 수평(좌우)으로만 가능한 경우와 각 이동에 대한 비용이 모두 동일할 때 적합하다. (미로, 체스, 격자 등)

유클리드 거리(Euclidean Distance)

가장 일반적인 직선거리 개념으로 두 점을 잇는 가장 짧은 선의 길이이다.

두 점 (x1, y1) , (x2, y2) 사이의 유클리드 거리는 피타고라스의 정리를 사용하여 계산된다.

√ (x1 - x2)^2 + (y1 - y2)^2

대각선 이동이 가능한 경우, 이동 비용이 거리에 비례하는 경우에 사용하기 적합하다.

허용성

A* 알고리즘에서 휴리스틱 함수가 가져야 할 중요한 속성으로, 최단 경로를 정확하게 찾을 수 있는 여부를 보장하는 기준, 즉 A* 알고리즘의 정확성을 보장하는 핵심 조건이다.

허용 가능한 휴리스틱 함수는 어떤 노드에서 목표 노드까지의 예상비용이 실제 최단 거리보다 절대로 크지 않아야 한다.

h(n) ≤ 실제 최단 거리

h(n) : 현재 노드 n에서 목표 노드까지의 휴리스틱 비용

실제 최단 거리 : 현재 노드 n에서 목표 노드까지의 실제 최단 거리

A* 알고리즘이 최단 경로를 항상 찾을 수 있도록 보장하기 때문에 허용 가능한 휴리스틱을 사용하는 것이 중요하다.

최단 경로 보장

만약 휴리스틱이 실제 거리보다 과대평가한다면, 때때로 실제 최단 경로가 아닌 다른 경로를 최단 경로로 착각하여 탐색을 조기에 종료할 수 있다. 하지만 허용 가능한 휴리스틱은 항상 실제보다 같거나 작은 값을 예측하므로 항상 실제 최단 경로를 놓치지 않고 탐색하기 된다.

효율성과 균형

허용성은 정확성을 보장하지만, 너무 보수적인 휴리스틱은 A*가 데이크스트라처럼 넓은 영역을 탐색하게 만들어 효율성이 떨어질 수 있다. 따라서 이성적인 휴리스틱은 허용 가능하면서도 실제 최단 거리에 최대한 가까운 값을 예측하여, 최단 경로를 보장하면서도 탐색 효율성을 극대화하는 것이다.

예) 격자에서 가로/세로 이동만 가능하다고 가정할 때, 맨해튼 거리는 두 점 사이의 실제 최단 거리와 동일하거나 더 짧다. 장애물이 없는 최단 경로는 항상 맨해튼 거리보다 길거나 같을 수 없기 때문에 허용 가능한 휴리스틱이다.

예) 두 점 사이의 가장 짧은 직선거리는 유클리드 거리이다. 실제 경로가 장애물 때문에 직선으로 갈 수 없다면, 실제 경로는 유클리드 거리보다 길어질 수밖에 없으며 유클리드 걸리도 실제 최단 거리보다 과대평가하지 않으므로 허용 가능한 휴리스틱이다.

데이크스트라(Dijkstra) 알고리즘

데이크스트라 알고리즘은 그래프에서 꼭짓점(노드) 간의 최단 경로를 찾는 알고리즘이다.

기본적으로 단일 출발점(Single-Source)에서 그래프의 다른 모든 꼭짓점까지의 최단 경로를 찾는 데 활용되며, 음의 가중치(negative weights)가 없는 그래프에서만 정확하게 동작한다.

데이크스트라 기본 형태 (선형 탐색 방식)

데이크스트라 알고리즘의 초기 형태는 우선순위 큐를 사용하지 않고, 일반적인 배열 또는 리스트를 사용하여 구현되었다. 이 방식은 매 단계마다 방문하지 않은 노드 중에서 시작점으로부터의 거리가 가장 짧은 노드를 선형 탐색하여 찾아낸다.

시간 복잡도

- 그래프에 V개의 노드가 있을 때, 매번 가장 짧은 노드를 찾기 위해 O(V) 시간이 소요된다.

- 가장 짧은 노드 선택과정을 총 V번 반복하기 때문에, 전체 시간 복잡도는 O(V * V) = O(V^2)이 된다.

플로우(일반 배열/리스트 사용)

기본 형태에서는 일반 배열/리스트를 사용하여 구현했는데 이 경우 그래프의 모든 노드를 방문하면서 각 노드를 방문할 때마다 짧은 거리를 찾는 과정이 필요한데 이때 V개의 노드가 있다면 모든 노드를 순회하는 작업이 O(V)의 시간이 걸리고 여기서 매 반복마다 O(V)의 시간이 소요되는 '가장 짧은 거리 노드 선택' 과정이 총 V번 반복되기 때문에 전체 시간 복잡도는 O(V^2)이 된다.

플로우

dist[] : 각 노드까지의 최단 거리를 저장, infinity 초기화
visited[] : 각 노드를 방문했는지 여부, false 초기화
start_node ( dist = 0 )

그래프의 노드 V개를 모두 방문할 때까지 다음 동작을 반복한다.

min_dist = infinity
closest_node = -1;
visited == false 인 노드(index i) 
- dist[i] < min_dist : min_dist = dist[i], closest_node = i

선택된 노드는 방문 처리를 하고 visited [closest_node] = true, 이 노드의 최단 거리는 확정됨

만약 closest_node == -1이라면 모든 노드가 방문되었거나 연결되지 않은 경우로 반복을 종료한다.

이후 인접 노드 거리를 갱신한다.

closest_node와 연결된 모든 인접 노드에 대해서

visited == false && 
dist[closest_node] + edge_weight(closest_node, neighbor) < dist[neighbor]
(인접 노드를 거치는 것이 현재 저장된 최단 거리보다 더 짧다면 최단 거리를 갱신)

모든 반복이 끝나면 최종적으로 dist [] 배열에는 시작 노드로부터 각 노드까지의 최단 거리가 저장된다.

우선순위 큐를 활용한 개선된 데이크스트라

데이크스트라 알고리즘의 효율성을 높이기 위해 가장 짧은 거리 노드 선택 과정을 개선한 방식으로 우선순위 큐(Priority Queue)를 사용한다.

우선순위 큐는 선입선출 방식인 일반적인 큐와 달리 데이터들이 우선순위를 가지고 있어, 가장 높은(또는 낮은) 우선순위를 가진 데이터가 먼저 나가는 자료구조이다.

시간복잡도

- 우선순위 큐는 가장 작은 값 추출(extract_min) 및 값 삽입(insert) 연산을 각각 O(log N) (N은 큐에 있는 원소의 개수)의 시간 복잡도로 수행한다.

- 간선의 개수를 E라고 할 때, 각 간선이 한 번씩 큐에 삽입될 수 있으므로, 전체 시간 복잡도는 O((V+E)logV) 또는 O(ElogV)로 개선된다.

플로우

dist[] : 최단 거리 저장 배열, 무한대 초기화
pq(priority_queue) : 우선순위 큐, (거리, 노드) 튜플로 저장, 가장 거리가 짧은 튜플이 항상 최상단에 정렬
시작 노드 : pq <- (0, start_node) 삽입

pq에서 거리 값이 가장 작은 튜플을 추출, 짧은 경로가 발견되어 처리되었다면 확정된 노드를 불필요하게 재처리하는 것을 방지하기 위해서 무시하고 다음 반복으로 넘긴다.

current_dist > dist[current_node] continue

인접 노드 거리 갱신, 현재 방문 중인 노드와 인접한 노드들에 대해서 해당 간선의 가중치에 대해 반복

dist[current_node] + edge_weight < dist[neighbor]
dist[neighbor] = dist[current_node] + edge_weight
pq <- (dist[neighbor], neighbor) insert

current_node를 경유할 때 인접한 노드까지의 거리가 현재 저장된 값보다 더 짧다면 해당 값으로 갱신하고 거리와 노드를 우선순위 큐에 저장한다.

pq가 완전히 비워지게 되면 dist [] 배열에는 시작 노드에서 다른 모든 노드까지의 최단거리가 저장된다.

BFS

Breath-First Search, 너비 우선 탐색

트리 자료구조의 순회 방법으로 같은 계층의 모든 노드를 먼저 탐색하고 다음 계층을 탐색하는 방식으로 순차적으로 진행하는 방식이다. 

아직 탐색하지 않은 자식 노드를 추적하고 모든 노드를 탐색하기 위해서 일반적으로 FIFO 방식인 큐를 사용한다.

탐색을 시작할 때 먼저 루트 노드를 큐에 넣는다. 큐에서 가장 앞에 있는 노드를 먼저 탐색하고 그 자식 노드를 모두 큐에 넣는다. 그리고 큐에서 제거를 하면 가장 먼저 넣었던 노드가 빠지게 된다. 그리고 다시 큐의 가장 앞에 있는 노드를 탐색하고 자식을 큐에 넣고 가장 앞의 노드를 제거하는 과정을 큐가 빌 때까지 반복하면 최종적으로 모든 노드를 방문할 수 있게 된다.

이 방법을 확장하면 사이클 유무, 방향성, 가중치 유무 등에 상관없이 모든 형태를 포함할 수 있는 자유로운 구조로 노드와 간선으로 구성된 구조인 일반 그래프에도 적용할 수 있게 된다. 이때는 부모-자식 관계가 확실한 트리에서와는 달리 중복해서 탐색하는 것을 방지하는 작업이 추가로 필요하다.

시각적으로 확인하기 쉬운 이차원 그리드에서 이를 응용하면 특정 셀을 루트 노드로 간주하고 그 인접한 각 셀들을 자식 노드로 치환할 수 있다. 이때 셀들은 중복해서 인접하기 때문에 이를 체크하여 순차적으로 탐색을 이어가면 모든 셀을 중복 없이 탐색할 수 있다.

여기서 시작 셀 이외에 또 다른 셀을 도착 지점으로 지정하고 이 셀을 만날 때까지 탐색을 진행하고 각 셀들이 어떤 셀로부터 이어져 온 것인지에 대한 정보를 저장한다면 도착한 셀에서 이전 셀을 타고 올라가면 시작 셀에서부터 도착 셀까지 이어지는 경로를 알 수 있게 된다. 이 과정이 BFS를 응용한 길 찾기 알고리즘이다.

DFS

Depth-First Search, 깊이 우선 탐색

트리 자료구조의 순회 방법으로 한 방향으로 최대한 깊이 탐색한 후, 더 이상 갈 곳이 없으면 이전 노드로 돌아가서 다른 방향을 탐색하는 방식으로 진행한다.

아직 탐색하지 않은 경로를 추적하고 모든 노드를 탐색하기 위해서 일반적으로 LIFO 방식인 스택을 사용하거나 재귀 함수를 활용한다. 탐색을 시작하면 루트 노드부터 시작해서 자식이 없는 리프 노드가 나올 때까지 스택에 노드를 저장하면서 탐색을 진행한다. 리프노드에 도착하면 스택에서 제거하면서 다시 역으로 거슬러 올라가는 백트래킹 과정을 진행한다. 해당 노드에 아직 탐색하지 않은 다른 자식이 있는지 확인 후 있으면 다시 깊이 탐색을 진행하고 리프에서 다시 역으로 올라가는 작업을 스택이 빌 때까지 반복한다.

BFS나 DFS는 트리 구조에 따라서 다르겠지만 BFS는 같은 계층의 모든 노드를 저장하기 때문에 깊이난 얕지만 계층이 넓은 경우 메모리상 불리하고 DFS는 계층이 얇지만 트리가 깊다면 또 불리하기 때문에 구조에 따라 방법을 선택해야 한다.

DFS 또한 길 찾기에 적용시킬 수 있는데 BFS는 가장 인접한 노드를 탐색하기 때문에 자연스럽게 최단 경로를 찾게 되는 것과 달리 DFS의 경우에는 최단 경로는 보장하지 않지만 경로 존재 여부나 모든 경로 탐색 등의 경우에 유리하다.