- 현재
- 큐에 있음
- 확정
- 경로
- 직선 추정치
A* 탐색
A* 탐색은 다익스트라 알고리즘처럼 시작에서 목표까지의 최단 경로를 찾지만, 목표가 대략 어디 있는지 압니다. 모든 노드는 남은 거리의 추정치, 즉 목표까지의 직선거리를 받고, 탐색은 항상 지금까지의 거리에 추정치를 더한 값이 가장 작은 노드에서 이어집니다. 노드를 클릭해 시작으로 정하고, 목표를 고른 뒤 단계별로 진행하면 탐색이 목표를 향해 나아가며 그래프의 구석 전체를 건드리지 않는 모습을 볼 수 있습니다. 재생을 눌러 탐색을 보거나, 단계와 뒤로로 한 단계씩 진행하세요. 단계 슬라이더를 끌면 원하는 곳으로 이동합니다. 노드를 클릭하면 시작 노드가 됩니다. 클릭을 목표로 바꾸고 다른 노드를 클릭하면 그 노드가 목표가 됩니다. 각 간선의 숫자는 그 길이이고, 각 노드의 숫자는 지금까지의 거리이며, 점선은 남은 거리의 직선 추정치입니다. 그래프 아래의 줄은 점수가 낮은 순서로 놓인 큐이며, 각 점수(지금까지의 거리 + 추정치)가 함께 표시됩니다. 새 그래프는 다른 그래프를 만듭니다. 노드와 간선 수를 고를 수 있습니다. 보드를 선택한 상태에서 화살표 키는 단계 이동, 스페이스 바는 재생과 일시 정지, Home과 End는 처음과 끝으로 이동합니다.
작동 원리
- 노드를 클릭해 시작 노드로 정합니다. 클릭을 목표로 바꾸고 다른 노드를 클릭해 목표로 정합니다.
- 재생을 누르거나, 단계와 뒤로로 한 단계씩 이동하세요. 단계 슬라이더를 끌면 탐색의 원하는 곳으로 이동합니다.
- 큐의 점수와 점선으로 된 직선 추정치를 지켜보세요. 마지막에 A*가 필요로 한 노드 수를 다익스트라 알고리즘과 비교하세요.
A* 탐색의 원리
시작 노드의 거리를 0으로 두고 큐에 넣습니다. 큐의 각 노드에는 점수가 있습니다. 지금까지의 거리에 남은 거리의 추정치를 더한 값입니다. 다음을 반복합니다. 점수가 가장 낮은 노드를 꺼내고 그 거리를 확정합니다. 그 노드가 목표라면 멈춥니다. 아니라면 확정되지 않은 각 이웃 노드에 대해 간선 길이를 노드의 거리에 더합니다. 그 값이 이웃 노드의 지금까지 거리보다 짧으면 거리를 낮추고, 그 노드를 거쳐 가는 길로 기억한 뒤, 이웃 노드를 새 점수와 함께 큐에 넣습니다.
추정치가 너무 길면 안 되는 이유
추정치가 목표를 실제보다 멀다고 하지 않는 한, A*는 최단 경로를 찾습니다. 이런 추정치를 허용 가능하다고 합니다. 직선이 그 예입니다. 두 곳 사이의 어떤 길도 직선보다 짧지 않기 때문입니다. 너무 긴 추정치는 A*가 가장 좋은 경로를 건너뛰게 할 수 있습니다. 모든 곳에서 추정치가 0이면 A*는 다익스트라 알고리즘이 되는데, 안전하지만 모든 방향을 살핍니다. 추정치가 좋을수록 A*에 필요한 노드는 줄어듭니다. 이 앱에서는 모든 간선의 길이가 그려진 길이를 올림한 값이므로, 직선은 안전한 추정치입니다.
자주 묻는 질문
A* 탐색이란 무엇인가요?
시작에서 목표까지의 최단 경로를 찾는 경로 탐색 알고리즘입니다. 다익스트라 알고리즘처럼 동작하지만, 큐를 지금까지의 거리에 남은 거리의 추정치를 더한 값으로 정렬하므로, 모든 방향으로 퍼지지 않고 목표를 향해 나아갑니다.
허용 가능한 휴리스틱이란 무엇인가요?
목표까지의 거리에 대한 추정치로, 실제 최단 거리보다 결코 길지 않은 것입니다. 허용 가능한 추정치를 쓰면 A*는 항상 최단 경로를 찾습니다. 지도에서의 직선거리가 대표적인 예입니다.
A*가 다익스트라 알고리즘보다 빠른가요?
목표 하나까지의 길이 필요하고 좋은 추정치가 있다면 대개 그렇습니다. 목표에서 먼 노드는 점수가 높아지므로 A*가 확정하는 노드가 더 적습니다. 추정치가 0이면 다익스트라 알고리즘과 똑같이 동작합니다. 모든 노드까지의 거리가 필요하다면 다익스트라 알고리즘이 더 낫습니다.
A*는 어디에 쓰이나요?
비디오 게임에서 캐릭터가 장애물을 피해 움직이게 할 때, 길 찾기 서비스, 로봇 동작 계획, 그리고 15 퍼즐 같은 퍼즐 풀이 프로그램에 쓰입니다. 15 퍼즐에서는 추정치가 타일이 제자리에서 얼마나 떨어져 있는지를 셉니다.
내 그래프가 어딘가로 전송되나요?
아니요. 그래프는 브라우저 안에서 만들어지고 탐색되며, 마지막 설정은 이 브라우저의 로컬 저장소에 남습니다.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
편집기로 이동