다른 블로그들에 A*(에이스타, A Star)와 관련된 글들이 굉장히 많았다.
사실 보면서 잘 이해가 안갔는데, 그냥 내 나름대로 이해한 글들을 정리했다.
모든 내용을 정리하기보단 그냥 이해가 안됐던 부분들 위주로...
휴리스틱이라는게 대체 왜 나오는거냐?
모든 에이스타 알고리즘 설명에는 꼭 휴리스틱이라는 말이 끼워져서 나온다. 왜일까?
휴리스틱을 정말 간단하게 요약한 글귀 중에 와닿았던 부분은 '해보니까 대충 이거던데?'였다.
백프로 맞아야 하는 규칙도 아니고, 그렇다고 완전 근거가 없는 것도 아닌 그런 부분인 것 같다.
그래서 휴리스틱이 나오는 이유는, 길찾기란 근본적으로 출발지에서 목적지까지 얼마나 걸릴지 예측해야 하는데,
이 예측에 '대충 이만큼 걸리지 않을까?'를 활용하기 때문이다.
매번 나오는 공식
$$ cost(n) = g(n) + h(n) $$
위 공식은 정말 징하게 많이 나온다. n이라는건 왜 있는걸까?
n은 '목적지를 나타내는 어떤 값'으로 생각해보자.
g(n)은 '출발지'에서 '현재 내 지점'까지 얼마나 걸렸는지를 기록하는 함수이다.
h(n)은 휴리스틱으로, '현재 내 지점'에서 '목적지'까지 얼마나 걸릴지를 예측하는 함수이다.
이 두개를 합치면 자연스럽게 '출발지에서, 지금 내가 서있는 지점을 거쳐서, 목적지까지 얼마나 걸릴까?'를 예측하는 무언가가 나온다.
계산 방식
기본적으로 갈 수 있는(하지만 안가본) 모든 방향을 다 계산하는 것 같다.
약간 BFS와 느낌이 유사하기도 한데,
일단 출발지에서 갈 수 있는 방향으로 모두 가보고, 각각의 cost(n) (즉 예상 소요 시간)을 다 계산한다.
그런 다음에 cost(n)이 최소인 쪽으로 계속 가보는 것이다.
주의점이 있는데, 뭔가 최소일 것 같은 곳으로 갔는데 길이 막혔다든지 해서 cost(n)이 급증할 수도 있다.
만약 이러면, 여태까지 중 cost(n)이 최소였던 지점으로 다시 되돌아가서 계산을 하게 된다.
그리디, BFS와의 차이
BFS와의 차이를 생각해보면, BFS는 출발지와 가까운 곳에서부터 마치 물결이 퍼지듯 모든 점을 다 가보고 기록한다.
그러나 A*는 앞에 벽이 나온다든지 하여 예상 도착 시간이 증가하면, 일단 다른 곳을 먼저 가본다.
그리디와의 차이를 생각해보면, A*는 휴리스틱인 만큼 "예측"이 들어가게 되며, cost(n)은 실제 계산값이 아닌 예측값이다.
그리디는, 매 순간순간마다는 계산했을때 진짜로 최적이라는 점에서 차이가 있다.