[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 이 피보나치 힙이라면 다익스트라와 같은 시간복잡도를 갖는다.