A* 알고리즘

A*(에이 스타)는 휴리스틱 기반의 최적 우선 탐색 알고리즘이다. A* 는 휴리스틱 함수를 사용해 노드 확장을 최소화함으로써 탐색 시간을 줄인다. 휴리스틱 함수는 두 정점 사이의 거리를 추정한다. 예를 들어, 도시 내 두 지점 간 경로를 탐색할 때, 직선 거리를 통해 실제 도로 거리를 추정할 수 있다.

A* 는 휴리스틱 함수에 따라 가장 유망한 노드를 먼저 확장한다. 도시 예시에서 A* 는 목표 지점 방향으로 가는 도로를 먼저 선택하고, 그 도로가 막다른 길일 경우에만 되돌아가 다른 도로를 시도한다. 이 방식은 대부분의 상황에서 탐색 속도를 높인다.

A* 는 휴리스틱 함수가 허용 가능한 경우 최적의 경로를 찾는다. 휴리스틱 함수가 허용 가능하다는 것은 목표에 도달하는 데 필요한 비용을 절대 과대평가하지 않는다는 의미다. 휴리스틱 함수가 항상 0을 반환하는 극단적인 경우, A* 는 다익스트라 알고리즘과 동일하게 동작한다. 휴리스틱 함수가 실제 거리에 가까울수록 탐색 속도가 빨라진다.

예제

이 간단한 방향성 그래프를 통해 예제를 살펴보자. 모든 간선의 비용은 1로 가정하고, 휴리스틱 함수는 목표 노드에서 시작해 뒤로 거슬러 올라가는 컬럼 값을 사용한다.

첫 번째 단계에서 왼쪽의 루트 노드(파란색)를 확장한다. 비용 g를 0으로 설정하고 모든 이웃 노드를 오픈 리스트(회색)에 추가한다.

첫 번째 노드를 클로즈드 리스트(연한 파란색)에 추가해 그래프에 루프가 있을 경우 다시 확장하지 않도록 한다. 다음으로 오픈 리스트에서 g + h 값이 가장 작은 노드를 선택한다. 여기서 g는 현재 비용(0)에 간선 비용(1)을 더한 값이다. 오픈 리스트의 모든 노드가 동일한 값을 가지므로 가장 위에 있는 노드를 선택한다.

이 과정을 반복해 오픈 리스트에서 다음 노드를 선택한다. 이 경우 오픈 리스트에 추가할 새로운 노드가 없다.

다음 노드를 확장한다. 오픈 리스트에 하나의 노드가 추가되지만 아직 특별한 변화는 없다.

위쪽과 아래쪽 노드가 동일한 값을 가지므로 위쪽 노드를 선택한다. 이 선택이 최선은 아니지만, 더 나은 휴리스틱 함수가 있었다면 더 좋은 선택을 할 수 있었을 것이다.

이제 아래쪽 노드를 확장한다. 이 노드의 값이 중간 노드보다 작기 때문이다(2 + 1 < 3 + 1).

드디어 목표 노드에 도달했다! 중간 노드는 전혀 확장하지 않았다. 그 노드의 값이 4로, 우리가 찾은 해결책의 총 길이와 동일하기 때문에 최적 경로에 포함되지 않을 것이 보장되었기 때문이다.

마지막 단계는 목표 노드에서 역추적해 최적 경로를 구성하는 것이다.