이번에 더 배울 것
A*는 하트·닐슨·라파엘(Hart, Nilsson & Raphael, 1968)이 발표한 최단 경로 탐색입니다. 다익스트라가 출발점에서 지금까지의 비용 g(n)이 가장 작은 노드를 먼저 확정한다면, A*는 여기에 n에서 도착점까지 남은 비용의 어림값 h(n)을 더한 f(n) = g(n) + h(n)이 가장 작은 노드를 먼저 꺼냅니다. 지도에서는 두 지점 사이의 직선거리를 h로 흔히 씁니다.
h가 실제 남은 비용을 절대 넘지 않으면 허용 가능한(admissible) 휴리스틱이라 하고, 이때 A*는 최단 경로를 찾습니다. 직선거리는 어떤 도로보다 길 수 없으므로 허용 가능합니다. h=0이면 A*는 다익스트라와 똑같이 움직이고, h가 실제 남은 비용에 가까울수록 도착점 방향의 노드만 꺼내 탐색이 줄어듭니다.
h가 실제보다 크게 어림하면(과대 추정) 탐색은 더 빨리 끝날 수 있지만 최단이 아닌 경로를 답으로 낼 수 있습니다. 또 좋은 h를 만들려면 노드의 좌표처럼 그래프 밖의 정보가 필요하므로, 그런 정보가 없는 소셜 네트워크나 지식 그래프에서는 쓰기 어렵습니다.
작은 예제로 따라가기
좌표는 S(0,0), 서쪽 W1(−2,0)·W2(−4,0), 동쪽 E1(2,0)·E2(4,0)·T(6,0), 북쪽 N1(3,4)입니다. 엣지는 S–W1 2, W1–W2 2, S–E1 2, E1–E2 2, E2–T 2, S–N1 5, N1–T 5이고, h는 T까지의 직선거리입니다.
다익스트라는 거리 순으로 S(0), W1·E1(2), W2·E2(4), N1(5), T(6)까지 7개 노드를 모두 확정한 뒤에야 끝납니다. 목적지 반대편인 W1·W2까지 꺼냅니다.
A*는 S 다음에 E1(f=2+4=6), E2(f=4+2=6), T(f=6+0=6) 순으로 꺼내 4개만 확정하고 같은 최단 비용 6을 찾습니다. W1은 f=2+8=10, N1은 f=5+5=10이라 끝까지 꺼내지 않습니다.
휴리스틱 바꾸기
h를 0, 직선거리, 과대 추정으로 바꿀 때 꺼내는 노드 수와 답이 어떻게 될지 먼저 예상하세요.
어림 정보가 없으면 f = g가 되어, 지금까지의 거리만 보고 사방으로 넓혀 갑니다.
학습을 시작하면 새 문제를 직접 풀고 확인 퀴즈를 마친 뒤 선택한 본과정 회차로 돌아갑니다.