A*

지난 글 : [알고리즘] - 다익스트라 알고리즘

 

A*(에이 스타)는 그래프의 최단 경로를 찾는 알고리즘으로 다익스트라 알고리즘을 발전시킨 것이다. 다익스트라 알고리즘에서는 시작점에서 각 정점까지의 최단 경로를 순서대로 결정해 가며, 시작점에 가까운 정점부터 순서대로 결정한다. 따라서 시작점에서 멀리 떨어진 정점의 최단 경로도 결정한다. 허나 이것은 결국 사용하지 않아 의미가 없게 된다. A*는 미리 추정 가중치를 설정해 불필요한 탐색을 방지하도록 개선한 기법이다.

 

1

칸으로 이루어진 미로 속에서 시작점과 목표 정점을 정한다. 미로는 각 칸을 정점으로 간주하고 각 정점 사이의 가중치가 1인 그래프라고 해석한다.

 

2

다익스트라 알고리즘으로 최단 경로를 구하면 필요 없는 경로도 모두 구한다. 하지만 A*에서는 시작점부터의 가중치뿐만 아니라 현시점에서 목표까지의 추정 가중치도 함께 고려해 탐색한다. 이 추정치는 자유롭게 설정할 수 있다.

 

3

A*를 사용하면 먼저 시작 지점을 탐색 완료했다고 표시한 후 시작점으로부터 갈 수 있는 칸의 가중치를 각각 계산한다. 가중치는 '거기에 도달할 때까지의 가중치'와 '발견적 가중치'의 합계로 계산한다. 여기서 발견적 가중치란, 사람의 손으로 미리 설정하는 추정 가중치다. 사전 정보를 갖고 최적의 추정 가중치를 설정하고 그것을 힌트로 사용하므로 더 효울적인 탐색이 가능해진다.

 

4

가중치가 가장 낮은 칸을 하나 선택한다. 선택한 칸을 따로 표시하고 탐색 완료 상태로 표시한다. 

 

5

탐색을 완료한 칸에서 갈 수 있는 칸의 가중치를 계산한다.

 

6

가중치가 가장 낮은 칸을 하나 선택한다.

 

7

선택한 점을 탐색 완료 상태로 표시한다. 같은 작업을 목표에 도착할 때가지 반복한다.

 

8

탐색을 완료했다. 다익스트라라면 목표로부터 멀어지는 방향의 칸도 탐색했겠지만, A*를 사용해 보다 효율적으로 미로를 탐색할 수 있었다.

 

참고 서적 :