[Graph] A* 알고리즘

다익스트라와 기본은 같다. 다익스트라는 현재 노드의 기준에서 다음 노드를 넣는다.

쓸데없는 평가를 피해야 한다.

다음 노트 선택 시 기준을 하나 더 추가

 - 다익스트라의 기준은 시작점부터 노드까지의 거리

 - A*가 추가하는 기준은 그 노드로부터 목적지까지의 거리

 

문제점 : 목적지까지 탐색을 하기전까지는 확실히 모름

A*가 추가한 기준은 결정적이지 않다. -> 휴리스틱, 근사

이 휴리스틱함수에 따라 A* 의 성능이 달라짐

대부분의 경우는 다익스트라보다 빠르다

 

A* 의 두 가지 노드 선택 기준

g(n): 시작노드부터 노드 n까지의 거리(실제값)

h(n): n부터 목적지 노드까지의 거리(추정치)

f(n): 시작노드부터 목적지 노드까지의 거리(추정치)

f(n) = g(n) + h(n)

다음 노드 선택 시

다익스트라는 g(n)이 최소

A* 는 f(n)이 최소

 

계속 목적지 방향으로 가고 싶다면 목적지 쪽에 있는 노드를 우선적으로 선택하고 싶음, 목적지쪽에있는 노드의 h(n)이 더 작아야함, h(n)은 주로 거리함수를 사용한다(유클리드 거리, 맨해튼 거리)

 

다익스트라와 차이점

OPEN 이란 이름의 노드 집합이 있음

• 방문할 최단 경로 후보 노드들이 있음

OPEN 안에 있는 후보 선택 시 최소 f(n)을 이용

같은 노드를 두 번 이상 방문할 수 있음

 

1. 그래프에 모든 g(n) 과 f(n) 을 무한대로 초기화

2. g(s) = 0, f(s) = h(s)

3. 시작 노드 s 를 OPEN 에 추가

4. OPEN 에서 f(n) 이 가장 작은 노드를 찾아 제거

5. n의 각 이웃 m 에 대해 시작점 -> n -> m 이 더 짧은 경로면 g(m)을 업데이트, m을 OPEN 에 추가

6. 목적지에 도달하거나 OPEN이 빌 때 까지 4~5를 반복

 

h(n) 함수에 대한 이해

h(n) 의 결과와 실제 결과의 관계에 따라 A* 알고리즘의 행동이 바뀜

h(n) = 0이라면 다익스트라와 똑같다

h'(n) : 실제 노드 n부터 목적지까지의 거리

h(n) <= h'(n) 이라면 A*는 최단거리를 찾는다. 이 때 h(n)은 admissible 이라고 한다.

h(n) << h'(n) 이라면 A* 가 굉장히 많은 경로를 탐색, 탐색 범위가 넓어져서 속도가 느려짐

 

A* 가 중복방문을 허용하는 이유

다익스트라는 새로 방문하는 노드의 실제 거리가 최소

 - 실제거리 g(n)만을 사용, 더이상 작아질 수 없다.

A*는 새로 방문하는 노드의 거리가 실제 거리가 아님

 - h(n)으로 추정, 나중에 다른 경로를 방문하면 거리가 작아질 수 있다.

그러나 h(n)이 특정 조건을 만족하면 노드를 한번씩만 방문함

 - consistent / monotone (일관적/단조로운) 휴리스틱

 - 특정조건 : h(n) <= dist(n, m) + h(m)

 

시간복잡도 : h(n) 이 O(1)고 OPEN 이 피보나치 힙이라면 다익스트라와 같은 시간복잡도를 갖는다.