A* 알고리즘 쉬운 개념 설명

개요

그래프/트리 탐색 알고리즘. 

게임에서 많이 사용되는 최단거리 길찾기 알고리즘이다.

다익스트라 확장판. BFS의 가지치기 알고리즘이라 생각하면 된다. 

핵심 개념 

1. 최소가 되는 지점을 우선 탐색 (우선 순위 큐)

2. 휴리스틱 추정값 사용

3. Open List / Closed List를 이용하여 노드 관리

다른 알고리즘과 차이점

BFS (Breadth First Search) : 완전 탐색 알고리즘. 우선순위없이 모든 노드를 탐색한다. 

다익스트라 : 일반적인 최단거리 알고리즘. 한 노드를 기준으로 모든 노드의 최단 경로를 찾기 때문에 시간 비용이 많이 든다.

플로이드 : 모든 노드의 최단 경로를 찾는 알고리즘. 일반적인 시간 복잡도 O(N^3).

개념 설명

1. 휴리스틱 추정값

  f(x) = h(x) + g(x)

  - h(x) : 출발 노드 n으로부터 도착 노드 n까지의 경로 가중치 (새로운 사각형까지의 거리)

      

   이 포스팅에서는 수평, 수직으로 가는 경로는 10, 대각선으로 가는 경로는 14의 가중치를 갖는다. 

  - g(x) : 노드 n 으로부터 목표 노드까지의 추정 경로 가중치 (도착 노드까지의 예상 이동비용)

      맨해튼 거리 측정법 사용 (x1-x2) + (y2-y1)  //장애물을 무시한 거리

2. Open List, Closed List

 - Open List : 검색 가능성이 있는 노드의 집합

 - Closed List : 이미 검색이 끝난 지점들의 집합

3. 탐색 우선 순위

 - Open List 내의 f(x) 가중치 값이 가장 작은 노드부터 탐색

동작 원리(Pseudo Code)

while pq_size
    node = pq.pop;
    if node == goal
        break;
    for next_node in (next_node_begin...next_node_end)
        pq.push(next_node, g(node) + cost + h(next_node));

print node

출처 : https://namu.wiki/w/A*%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 (나무위키)

슈도코드 풀이

1.출발 노드의 주변 노드 8개를 open list에 추가

    1.1 if(주변노드 in closed list || 못가는 지역) continue;

    1.2 if(주변노드 not in open list || 주변노드 < 기존 탐색 노드) 갱신

2. current = open list내의 노드중 f(x)값이 가장 작은 노드

    2.1 if(Open list.empty()) 최단 경로 없음

3. 선택된 노드는 open list에서 제거 및 closed list에 추가

4. if(current == 도착 노드) break; //길 찾기 완료

    else 반복 // 1.로 이동

그림 설명

2차원 배열로 단순화 시켜 설명하겠습니다.

- 초록색 : 출발 노드

- 파란색 : 장애물 (이동 불가)

 - 빨간색 : 도착 노드

1. 출발 노드를 Priority Queue에 Push()

1. Priority Queue에서 pop() (현재 Priority Queue에는 출발 노드만 존재)

2. 출발 노드는 Closed List에 추가하게 됩니다.

3. 출발 노드를 기준으로 주변 노드 8개 (사각형)을 탐색해 갈 수 있는 노드의 F(=G+H) 가중치 값과 부모 노드 (여기선 출발노드)를 구한다.

 // G : 직선 : 10, 대각선 14

 // H : 장애물을 무시한 도착 노드까지의 맨해튼 거리 (출발 노드의 오른쪽 상단 노드의 H값은 도착 노드까지 x+3, y+1 의 거리값을 갖는다)

4. 계산된 주변 노드를 Open List에 추가합니다. 

1. Priority Queue는 F값으로 정렬되어 있으므로 F값이 가장 낮은 40 노드를 pop()

2. 주변 탐색 가능한 노드를 찾는다. 

  2.1 출발 노드는 closed list에 존재하므로 continue; 장애물 3개도 continue;

  2.2 F=54인 바로 위, 아래 노드는 open list에 있으므로(↗) 40을 거쳐가는 (→↑) 경로와 비교한다.

  2.3 →↑ 경로는 G가중치가 20( →(G = 10) +↑(G = 10)) 이고 ↗ 경로는 14를 가지므로 ↗ 경로가 더 가깝다. 그러므로 open list에 push()하지 않음

      나머지 경로 또한 위와 같은 계산으로 갱신하거나 새로 추가한다.

3. 40 노드는 closed list에 push()된다.

1. 다시 Priority Queue를 pop()해서 다음 노드를 꺼낸다. (54 노드 두개 중 하나가 나오겠죠?)

2. 54 노드의 주위노드를 탐색합니다. 

  2.1 ← 노드는 open list에 있기 때문에 F값을 계산하여 비교해보지만 원래 가지고 있는 F값이 더 작기때문에 갱신되지 않습니다.

  2.2 좌상, 상 노드는 closed list에 있기 때문에 탐색하지 않습니다. 우상, 우 노드는 장애물이기 때문에 탐색하지 않습니다. 

  2.3 우하 노드는 장애물에 걸리기 때문에 탐색하지 않습니다. (원한다면 넣어도 됨)

  2.4 좌하, 우 노드는 open list에 없기 때문에 F 가중치 값 계산 후 open list에 push()

1. 한 가지 확인해야할 것은 위위사진과 위 사진을 비교했을 때 초록색 사각형 아래아래에 있는 F=80인 노드의 값이 변경된 것을 확인할 수 있습니다. 기존의 F=84인 노드보다 새로운 경로의 F=80이 더 낮은 가중치를 갖기 때문에 갱신된 것 입니다.

2. 위와 같은 로직을 반복하면서 도착 노드가 나올 때까지 계속 반복합니다.

1. 도착 노드가 나왔으면 도착 노드가 가지고 있던 부모 노드를 추적하여 나오는 경로가 출발노드에서 도착노드로 가는 최단 경로가 됩니다.

2. 도착 노드가 나오지 않는다면 경로 탐색이 불가능.

정리

A* 알고리즘은 개량하여 상대적으로 더 최적화된 결과를 얻을 수 있다.

 - 주변노드 탐색(현재는 사각형) 범위를 바꾸거나 맨해튼 거리가 아닌 유클리디안 거리 측정법을 이용하거나.