[알고리즘] A*(AStar) 알고리즘

A*(AStar) 알고리즘이란?

 A*(AStar) 알고리즘은 최단 경로 탐색 알고리즘 중 하나로, 시작 노드와 목적지 노드를 분명하게 지정하여 두 노드 간의 최단 경로를 파악하는 알고리즘이다. 출발지에서 목적지까지 가는 최단 경로를 찾아내기 위해 고안되었으며 다익스트라 알고리즘을 확장하여 만든 알고리즘이다. 다익스트라 알고리즘은 목적지 노드를 설정하지 않고 출발 노드로부터 다른 모든 노드까지의 최단 경로를 찾지만, A* 알고리즘은 목표 노드를 선택하고 시작한다. 경로 탐색의 우선순위를 두고 유망한 해부터 우선적으로 탐색한다. 가장 가까운 정점부터 탐색하는 것이 아니라 휴리스틱(h)이라는 함수를 통해 탐색하게 된다. 

 

 유망한 해부터 우선적으로 탐색한다고 했는데, 유망한 해를 어떻게 선정할까? 노드들에 점수를 매겨서 선정하는데, 점수를 매기는 데 필요한 것은 f, g, h가 있다.

g = 지금까지 온 거리(걸린 거리. 실제로 왔던 거리)

h = 예상 거리(앞으로 갈 예상거리. 휴리스틱이라고 함)

f = g + h (총점수. f가 가장 낮은 값부터 탐색. 경로에 따라 달라짐)

 

h(휴리스틱)을 어떻게 설정하느냐에 따라 효율성이 달라진다(대각선으로 이동할수록 효율성이 좋아짐: 유클리드 거리).

대각선의 효율을 이용할 땐, 삼각형의 비율이 1:1:루트2 인데 루트 2가 대략 1.414.... 이다. 근데 소수점으로 계산하면 힘드니까 한 칸 자체를 1이 아닌 10으로 잡는다. 그래서 한 칸 이동은 10으로 계산, 대각선은 14로 계산한다. 

f, g, h 모두 작을수록 좋은 거다.

 

 A* 알고리즘은,

1. f값이 가장 작은 정점부터 탐색을 해서

2. 탐색한 정점의 f값을 구해온다.

 

 

 

 

다익스트라와 A* 알고리즘의 차이점

• 다익스트라는 목적지 노드를 선정하지 않는다. 출발 노드로부터 다른 모든 노드까지의 최단 경로를 찾지만 A* 알고리즘은 목표 노드를 선택하고 시작한다.
• A* 알고리즘은 완전한 최단 경로를 찾지 않고 최단 경로의 근사값을 찾아내는 것을 목표로 한다. 가장 가까운 노드부터 순차적으로 모두 방문하는 것이 아닌, 휴리스틱 함수를 통해 추정하여 매긴 점수를 토대로 탐색한다.
• 다익스트라는 가중치없이 전방향으로 전체적으로 탐색하지만 A*는 아니다.