A* 탐색
다익스트라 알고리즘은 목표까지의 최단 경로를 찾지만, 목표에서 멀어지는 방향까지 모든 방향을 한꺼번에 탐색합니다. A* 탐색은 목표가 아직 얼마나 먼지에 대한 추정치라는 지식 하나를 더할 뿐인데, 탐색이 단번에 목표를 향해 곧장 나아갑니다.
기본 아이디어
지도에서 길을 찾을 때, 목적지에서 멀어지는 길을 목적지로 향하는 길만큼 꼼꼼히 살피지는 않습니다. A* 탐색도 마찬가지입니다. 모든 노드는 점수를 받습니다. 시작에서 지금까지의 거리 g에 남은 거리의 추정치 h를 더한 값입니다. 탐색은 항상 점수가 가장 낮은 노드에서 이어지므로, 목표 쪽에 있는 노드가 먼저 나옵니다.
단계별 과정
시작 노드의 거리를 0으로 두고 점수 h(start)로 큐에 넣습니다. 다음을 반복합니다. 점수가 가장 낮은 노드를 꺼내고 그 거리를 확정합니다. 그 노드가 목표라면 멈춥니다. 기억해 둔 노드를 거꾸로 따라가면 경로가 됩니다. 아니라면 확정되지 않은 각 이웃 노드에 대해 이 노드를 거친 거리를 계산합니다. 그 값이 지금까지의 거리보다 짧으면 거리를 낮추고, 이 노드를 거쳐 가는 길로 기억한 뒤, 새 거리에 추정치를 더한 값을 이웃 노드의 점수로 줍니다. 두 점수가 같을 때는 추정치가 더 작은 노드를 먼저 꺼내면 대개 목표에 더 빨리 도달합니다.
예시
시작 A와 목표 D가 있다고 합시다. A–B의 길이는 2, B–D는 2이고, A–C는 1, C–D는 5입니다. D까지의 직선 추정치는 A에서 3, B에서 2, C에서 3입니다. A는 점수 0 + 3 = 3으로 시작합니다. A를 꺼내면 B의 점수는 2 + 2 = 4, C의 점수는 1 + 3 = 4가 됩니다. 동점이므로 A*는 추정치가 더 작은 B를 꺼내고, B는 D에 점수 4 + 0 = 4를 줍니다. 이제 D는 점수가 가장 낮고 추정치도 가장 작으므로 꺼내집니다. 최단 경로는 길이 4인 A → B → D이고, 엉뚱한 방향으로 가는 C는 한 번도 확정되지 않습니다. 다익스트라 알고리즘이었다면 A에서 가장 가까운 노드인 C를 먼저 확정했을 것입니다.
좋은 추정치
추정치는 목표까지의 실제 거리보다 길어서는 안 됩니다. 이런 추정치를 허용 가능하다고 하며, 이를 쓰면 A*는 항상 최단 경로를 찾습니다. 직선은 허용 가능합니다. 어떤 경로도 직선보다 짧지 않기 때문입니다. 또한 한 노드에서 다음 노드로 갈 때 추정치가 간선 길이보다 더 많이 줄지 않는다면 일관된 추정치이며, 확정된 노드를 다시 볼 필요가 전혀 없습니다. 추정치가 실제에 가까울수록 A*에 필요한 노드는 줄어듭니다. 추정치 0은 허용 가능하지만 쓸모가 없습니다. 그러면 A*는 다익스트라 알고리즘이 됩니다. 너무 큰 추정치는 A*를 빠르게 하지만 최단 경로를 놓칠 수 있습니다.
역사와 활용
스탠퍼드 연구소의 피터 하트, 닐스 닐슨, 버트럼 라파엘은 최초의 이동 로봇 중 하나인 셰이키를 연구하던 중 1968년에 A*를 발표했습니다. 그 이전 버전은 A1과 A2라고 불렸고, 별표는 최적임을 증명한 버전을 표시한 것입니다. 오늘날 A*는 비디오 게임에서 캐릭터가 장애물을 피해 움직이게 하고, 경로와 로봇의 움직임을 계획하며, 15 퍼즐 같은 퍼즐을 풉니다. 15 퍼즐에서는 추정치가 각 타일이 제자리에서 얼마나 떨어져 있는지를 더합니다.
직접 살펴보기
앱을 열고 단계를 누르세요. 간선의 숫자는 그 길이이며, 여기서는 그려진 길이와 일치합니다. 점선은 목표까지의 직선 추정치를 보여 줍니다. 그래프 아래의 큐는 노드를 점수가 낮은 순서로 나열합니다. 목표가 확정되면 상태 줄에서 A*가 확정한 노드 수와 다익스트라 알고리즘이었다면 필요했을 노드 수를 비교합니다. 큰 그래프의 먼 구석에 목표를 두면 차이가 가장 크게 나타납니다.
자주 묻는 질문
A*의 별표는 무슨 뜻인가요?
하트, 닐슨, 라파엘은 처음에 A1과 A2라는 알고리즘을 설명했습니다. A*('A 스타')는 추정치가 일관될 때, 같은 추정치를 쓰는 비슷한 알고리즘 가운데 가장 적은 노드를 확장하여 최단 경로를 찾는다고 그들이 증명한 버전입니다.
A*의 시간 복잡도는 얼마인가요?
최악의 경우, 즉 추정치가 쓸모없으면 A*는 다익스트라 알고리즘과 같은 일을 합니다. 이진 힙을 쓰면 O((V + E) log V)입니다. 좋은 추정치가 있으면 노드의 일부만 확정하므로 실제로는 빠릅니다.
A*에 좋은 휴리스틱은 무엇인가요?
계산이 빠르고, 실제 거리를 과대평가하지 않으며, 실제 거리에 최대한 가까워야 합니다. 상하좌우로만 움직일 수 있는 격자에서는 맨해튼 거리를, 지도에서는 직선거리를 흔히 씁니다.
휴리스틱이 과대평가하면 어떻게 되나요?
그러면 A*가 최단이 아닌 경로를 돌려줄 수 있습니다. 더 나은 경로를 살펴보기 전에 끝날 수 있기 때문입니다. 일부 프로그램은 일부러 이렇게 하여(가중 A*) 경로의 질을 조금 희생하고 속도를 크게 얻습니다.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
A* 탐색 해 보기