기록

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

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

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

BFS

Breath-First Search, 너비 우선 탐색

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

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

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

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

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

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

DFS

Depth-First Search, 깊이 우선 탐색

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

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

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

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

탐색 알고리즘을 시각화하기 위한 웹 페이지

https://bakcoding.github.io/pathfinding-algorithm/index.html