A star 알고리즘 (python) 설명

A star 알고리즘은 시작 노드부터 목표 노드까지 최단거리를 효율적으로 탐색 할 수 있는 알고리즘이다.

 

A Star 알고리즘의 작동은 아래 그림과 같다.

시작점 (0,0) 에서 도착점 (n-1, m-1) 까지 최단거리를 탐색을 하는데 BFS 와는 다르게 모든 노드를 탐색하지 않고 거리가 가까운 노드를 중심으로 탐색을 한다.

A star 알고리즘

 

반면 BFS 는 모든 노드를 탐색하면서 최단거리를 알아낸다.

BFS

 

 

A star 알고리즘을 활용해 아래 그림과 같이 출발점이 0 인 노드에서 도착점이 6 인 노드까지의 최단거리를 구해보자.

A star 알고리즘을 사용하기 위해서 휴리스틱 추정값을 사용해야 한다. 

휴리스틱 추정값이란, 간단히 말해서 현재 위치의 노드에서 도착점 까지의 대강의 거리를 말한다.

 

위 그림을 보면 O 와 C 배열이 있는데 O 라는 배열은 현재 위치인 0 과 연결된 1, 3 노드의 정보를 담고 있는 배열이다. 

F score = G score + H score 이며, H score 는 위에서 설명한 휴리스틱 추정값이고 G score 는 간선의 가중치이다.

예를들어 0번 노드에서 1번 노드까지의 거리는 5.6 이며, 1 번 노드에서 6 번 노드까지의 휴리스틱 추정값은 12 이므로,

F score 는 5.6 + 12 = 17.6 이다.

C 배열에는 현재 선택된 노드들이 들어있으며 ParentNode 는 해당 노드에 도달하기 전 가장 최근에 거쳐간 노드이다.

O 배열에 있는 값중 F score 가 가장 작은 값을 pop 해서 C 노드에 append 한다.

 

3번 노드가 C 에 들어왔으니, 3번노드와 연결된 2, 5 번 노드가 O 에 들어가야 한다.

3번 노드부터 2 번노드까지의 거리는 5.6 이며, 0 번노드부터 3번 노드까지의 거리는 6.8 이므로 2번노드까지의 간선 가중치는 5.6 + 6.8 = 12.4 이다. 

마찬가지로 5 번 노드도 값을 계산하여 O 배열에 넣어준다.

그 다음 O 에서 F scroe 가 가장 작은 1 을 pop 하여 C 배열에 append 한다.

1번 노드와 연결되어있는 노드는 2번과 4번이다. 하지만 2번은 이미 O 배열안에 존재한다. 이때 0 - 1 - 2 경로를 탔을때 간선의 가중치는 9.9 이며, 이는 기존에 존재하는 0 - 3 - 2 를 탔을때의 간선의 가중치인 12.4 보다 작은 값이다. 즉, 새로운 G score 의 값이 기존에 존재하는 G score 의 값보다 작다면 더 작은 값으로 갱신해준다.

모든 과정이 끝나고 O 배열안에 있는 값중 F score 가 가장작은 값은 2 이므로, C 에 2 를 append 해준다.

2 와 연결된 간선은 1,3,5,6 이며 C 배열에 존재하지 않는 5,6 노드에 대해서 다시 값을 계산해주어 O 배열에 넣어준다.

O 배열의 값 중 F score 가 최소인 노드는 6번 노드이므로 6번 노드를 C 에 append 해준다.

 

6번 노드가 C 에 들어왔다. 6 번은 도착지점의 노드이므로 이때 탐색을 끝낸다.

 

A star 알고리즘은 최단 경로 근처의 지점들만 탐색해서 BFS 와는 다르게 모든 경로를 탐색할 필요가 없다.

하지만, F score, G score, H score 등 여분의 데이터를 저장하기 위한 메모리가 BFS 에 비해 더 많이 필요하며, 만약 도착지점까지 도착할 수 없는 경우 BFS 와 똑같이 모든 노드를 탐색하게된다.

 

즉 A star 알고리즘은 도착할 수없는 경우 BFS 와 시간은 똑같지만 메모리를 더 쓰게 되는 것이다.

 

따라서 출발 지점부터 도착점까지 도착 방법이 확실히 존재하는 경우 사용해야 예상가능한 효율을 낼 수 있다.