A* 알고리즘

A* 알고리즘의 핵심은 휴리스틱 함수를 사용하여 탐색 방향을 지능적으로 결정하는 데 있다. 휴리스틱 함수는 특정 노드에서 목표 노드까지의 예상 비용을 추정하는 함수이다. 이 추정값은 알고리즘이 현재 위치에서 목표까지 얼마나 가까워졌는지를 평가하는 지표로 작용하며, 불필요한 경로 탐색을 줄이고 효율성을 극대화하는 역할을 한다.

가장 일반적으로 사용되는 휴리스틱 함수는 유클리드 거리와 맨해튼 거리이다. 격자 기반의 맵에서는 맨해튼 거리가, 자유 공간에서의 연속적인 이동에는 유클리드 거리가 적합하다. 이 외에도 문제의 특성에 맞춰 다양한 휴리스틱 함수를 설계할 수 있다. 휴리스틱 함수의 설계는 알고리즘의 성능에 직접적인 영향을 미치며, 추정값이 실제 최단 경로 비용을 정확히 반영할수록 탐색 속도가 빨라진다.

휴리스틱 함수는 적절성과 일관성이라는 두 가지 중요한 성질을 가질 수 있다. 적절성은 휴리스틱 값이 실제 비용을 절대 과대평가하지 않음을 의미하며, 이 조건이 충족될 때 A* 알고리즘은 최적의 경로를 보장받는다. 일관성은 인접한 노드 사이의 휴리스틱 추정치가 특정 조건을 만족함을 뜻하며, 이는 탐색 과정의 효율성을 더욱 높여준다.

A* 알고리즘은 각 노드 n에 대해 평가 함수 f(n)을 계산하여 탐색 방향을 결정한다. 이 평가 함수 f(n)은 두 가지 비용의 합으로 정의된다. 하나는 출발 노드에서 현재 노드 n까지의 실제 비용을 나타내는 g(n)이며, 다른 하나는 현재 노드 n에서 목표 노드까지의 예상 비용을 추정하는 휴리스틱 함수 h(n)이다. 즉, f(n) = g(n) + h(n)이라는 관계가 성립한다.

여기서 g(n)은 출발점부터 노드 n까지 이미 탐색된 경로의 누적 비용으로, 다익스트라 알고리즘과 같이 실제 이동한 거리나 비용을 정확히 기록한다. 반면 h(n)은 노드 n에서 목표 지점까지 남은 예상 비용으로, 맨해튼 거리나 유클리드 거리와 같은 휴리스틱을 사용해 추정한다. 이 휴리스틱 함수 h(n)이 실제 남은 비용을 과대평가하지 않는다는 조건(허용 가능 휴리스틱)을 만족할 때, A* 알고리즘은 최적의 경로를 보장한다.

이 세 요소의 관계는 알고리즘의 동작을 이해하는 핵심이다. 알고리즘은 열린 목록에서 가장 낮은 f(n) 값을 가진 노드를 선택해 확장한다. 이는 이미 소모한 비용(g(n))과 앞으로 예상되는 비용(h(n))을 모두 고려하여, 전체 예상 비용이 가장 낮은 경로를 우선적으로 탐색하도록 유도한다. 결과적으로 A* 알고리즘은 불필요한 탐색을 줄이면서도 최단 경로를 효율적으로 찾아낼 수 있다.

A* 알고리즘의 구체적인 실행 과정은 오픈 리스트와 클로즈드 리스트라는 두 개의 자료 구조를 사용하여 진행된다. 알고리즘은 먼저 출발 노드를 오픈 리스트에 추가하는 것으로 시작한다. 이후 오픈 리스트가 빌 때까지, 즉 더 이상 탐색할 후보 노드가 없을 때까지 다음 단계를 반복한다.

반복 과정의 핵심은 오픈 리스트에서 평가 함수 f(n) 값이 가장 작은 노드를 선택하여 현재 노드로 만드는 것이다. 이 노드를 오픈 리스트에서 제거하고 클로즈드 리스트에 넣는다. 만약 이 현재 노드가 목표 노드라면, 경로를 역추적하여 최단 경로를 구성하고 알고리즘을 종료한다. 목표 노드가 아니라면, 현재 노드의 모든 이웃 노드(인접 노드)를 검사한다. 각 이웃 노드에 대해, 클로즈드 리스트에 이미 존재하는지 확인하여 이미 평가가 완료된 노드는 무시한다. 만약 이웃 노드가 오픈 리스트에 없다면, g(n)과 h(n)을 계산하여 f(n) 값을 구한 후 오픈 리스트에 새로 추가한다. 이미 오픈 리스트에 있는 이웃 노드라면, 현재 경로를 통해 계산한 새로운 g(n) 값이 기존 g(n) 값보다 작은지 확인한다. 더 작다면, 해당 노드의 g(n)과 f(n) 값을 새로운 값으로 갱신하고, 부모 노드 정보를 현재 노드로 변경하여 더 나은 경로를 반영한다.

이 과정은 목표 노드에 도달하거나 오픈 리스트가 고갈될 때까지 계속된다. 오픈 리스트가 빈 상태로 종료된다면 출발점에서 목표점까지 도달 가능한 경로가 존재하지 않음을 의미한다. 알고리즘의 효율성은 휴리스틱 함수 h(n)의 정확도에 크게 의존하며, 만족스러운 휴리스틱을 사용할 경우 불필요한 노드 확장을 최소화하면서 최적 경로를 보장받을 수 있다.

A* 알고리즘은 최적성과 완전성이라는 두 가지 중요한 특성을 모두 만족하는 알고리즘이다. 최적성이란 알고리즘이 찾아낸 경로가 실제로 존재하는 가능한 모든 경로 중에서 비용이 가장 낮은, 즉 최단 경로임을 보장한다는 의미이다. 완전성이란 출발점에서 목표점까지 경로가 실제로 존재한다면, 알고리즘이 반드시 그 경로를 찾아낸다는 것을 의미한다. 이 두 가지 특성은 경로 탐색 알고리즘의 핵심 평가 기준으로, A* 알고리즘이 널리 사용되는 근본적인 이유가 된다.

A* 알고리즘이 최적성을 보장받기 위해서는 사용된 휴리스틱 함수 h(n)이 허용 가능해야 한다. 허용 가능 휴리스틱이란 휴리스틱 함수가 목표 노드까지의 실제 잔여 비용을 절대 과대평가하지 않는 성질을 말한다. 즉, h(n)은 항상 목표에 도달하기 위해 필요한 실제 최소 비용보다 작거나 같아야 한다. 또한 그래프에 음의 가중치를 갖는 간선이 존재하지 않아야 한다는 전제 조건이 필요하다. 이러한 조건 하에서 A* 알고리즘은 확장하는 첫 번째 목표 노드가 최적의 경로를 가진 노드임을 보장한다.

완전성에 관해서는, 그래프가 유한하고 각 노드에서 파생되는 가지의 수가 유한하며, 각 간선의 비용이 0보다 큰 값을 가질 때 A* 알고리즘은 완전성을 가진다. 이 조건들은 알고리즘이 무한 루프에 빠지지 않고 탐색 공간을 체계적으로 탐색하여, 존재하는 경로를 반드시 발견할 수 있도록 한다. 따라서 게임의 길찾기나 로봇의 경로 계획과 같은 실제 응용 분야에서 A* 알고리즘은 목표까지의 경로가 존재할 경우 그 해를 항상 찾아낼 수 있는 신뢰할 수 있는 방법으로 자리 잡았다.

휴리스틱 함수의 선택은 A* 알고리즘의 성능과 결과에 결정적인 영향을 미친다. 이 함수는 특정 노드에서 목표 노드까지의 예상 비용을 추정하는 역할을 하며, 알고리즘이 탐색할 노드의 순서와 범위를 조절한다.

휴리스틱 함수가 실제 최소 비용을 과대평가하지 않는다는 조건, 즉 허용 가능한 휴리스틱일 때, A* 알고리즘은 항상 최적의 경로를 보장한다. 반대로 휴리스틱 함수가 실제 비용을 과소평가하면 알고리즘은 여전히 최적 경로를 찾을 수 있지만, 탐색해야 할 노드의 수가 불필요하게 증가하여 효율성이 떨어진다. 만약 휴리스틱 값이 0으로 설정되면, A* 알고리즘은 다익스트라 알고리즘과 동일하게 동작하여 출발점을 중심으로 균일하게 확장하는 탐색을 수행하게 된다.

따라서 실제 응용 분야에서는 문제의 특성에 맞는 적절한 휴리스틱 함수를 설계하는 것이 중요하다. 예를 들어, 격자 지도에서는 맨해튼 거리나 유클리드 거리가 흔히 사용된다. 좋은 휴리스틱 함수는 가능한 한 정확하게 실제 비용에 근접하면서도 계산 비용이 낮아, 알고리즘이 빠르게 최적 해를 찾을 수 있도록 돕는다.

다익스트라 알고리즘은 A* 알고리즘과 마찬가지로 그래프 상에서 최단 경로를 찾는 대표적인 알고리즘이다. 이 알고리즘은 출발 노드로부터 그래프 내 모든 다른 노드까지의 최단 거리를 계산하는 데 사용된다. A* 알고리즘이 휴리스틱을 활용해 목표 지향적인 탐색을 하는 반면, 다익스트라 알고리즘은 휴리스틱을 사용하지 않고 출발점을 중심으로 거리 비용만을 기준으로 균일하게 탐색 영역을 확장해 나간다는 점이 근본적인 차이이다.

알고리즘의 과정은 다음과 같다. 먼저 출발 노드의 거리를 0으로, 다른 모든 노드의 거리를 무한대로 설정한다. 그 후 아직 방문하지 않은 노드 중 현재까지 계산된 거리가 가장 짧은 노드를 선택해 방문하고, 이 노드를 통해 인접 노드로 가는 새로운 경로의 거리가 기존에 알려진 거리보다 짧다면 거리 정보를 갱신한다. 이 과정을 목표 노드가 방문될 때까지, 혹은 모든 노드를 방문할 때까지 반복한다.

다익스트라 알고리즘은 음의 가중치를 갖는 간선이 존재하지 않는 그래프에서 항상 최단 경로를 보장한다는 최적성을 갖는다. 그러나 휴리스틱 정보를 전혀 사용하지 않기 때문에 목표 노드의 방향성을 고려하지 않고 모든 방향으로 고르게 탐색을 진행한다. 이로 인해 목표 노드가 명확한 상황에서는 A* 알고리즘에 비해 탐색 속도가 느리고 불필요한 노드를 많이 방문할 수 있다.

따라서 다익스트라 알고리즘은 출발점 하나로부터 그래프의 모든 노드까지의 최단 경로를 구해야 하는 경우나, 휴리스틱 함수를 설계하기 어려운 환경에서 널리 사용된다. 반면, 출발점과 목표점이 명확하고 적절한 휴리스틱을 사용할 수 있다면 A* 알고리즘이 일반적으로 더 효율적인 성능을 보인다.

Greedy Best-First Search(탐욕적 최선 우선 탐색)는 A* 알고리즘과 마찬가지로 휴리스틱 함수를 사용하는 그래프 탐색 알고리즘이다. 그러나 이 알고리즘은 목표 노드에 도달하기까지의 실제 비용을 전혀 고려하지 않고, 오직 현재 노드에서 목표 노드까지의 예상 비용, 즉 휴리스틱 값 h(n)만을 기준으로 다음에 탐색할 노드를 선택한다. 이는 항상 휴리스틱 값이 가장 낮은, 즉 목표에 가장 가까워 보이는 노드를 우선적으로 탐색하는 탐욕적인 전략이다.

이러한 방식은 종종 매우 빠르게 목표를 찾을 수 있지만, 최단 경로를 보장하지 않는다는 근본적인 단점이 있다. 알고리즘이 휴리스틱에만 의존하기 때문에 실제 비용이 더 높은 우회로로 빠질 수 있으며, 심지어 잘못된 휴리스틱 함수를 사용할 경우 무한 루프에 빠질 위험도 있다. 반면, A* 알고리즘은 출발점부터 현재 노드까지의 실제 비용 g(n)과 휴리스틱 비용 h(n)을 합친 총 예상 비용 f(n)을 평가하여, 탐색의 효율성과 최적 경로 보장 사이에서 균형을 잡는다.

따라서 Greedy Best-First Search는 정확한 최단 경로가 필요하지 않고, 단순히 어떤 경로로든 목표에 빠르게 도달하는 것이 중요한 상황에서 사용될 수 있다. 하지만 게임 AI의 길찾기나 로봇 공학의 경로 계획과 같이 최적의 경로가 중요한 대부분의 응용 분야에서는 A* 알고리즘이나 다익스트라 알고리즘이 더 선호된다.