A* 탐색 알고리즘
원문: Claire Lee, A* Search Algorithm
A* 탐색 알고리즘은 가중 그래프의 시작 노드(출발지)와 목표 노드(목적지) 사이의 단일 쌍 최단 경로를 찾는 경로 탐색 알고리즘입니다. 이 알고리즘은 시작 노드에서 현재 노드(g)까지의 실제 비용을 고려할 뿐만 아니라 휴리스틱(h)을 사용하여 현재 노드에서 목표 노드까지 소요되는 비용도 추정합니다. 그런 다음 목표 노드에 도달할 때까지 이동할 다음 노드로 가장 낮은 f값(f=g+h)을 가진 노드를 선택합니다. 다익스트라(Dijkstra's) 알고리즘은 모든 노드에서 휴리스틱이 0인 A* 알고리즘의 또 다른 예시입니다.
A* 알고리즘은 어떻게 작동하나요?
A* 알고리즘은 g(n)과 h(n)라는 두 가지 함수를 고려합니다. 현재 노드 n에 있다고 생각해 봅시다. g(n)은 시작 노드에서 현재 노드까지 실제 소요된 비용을 알려줍니다. h(n)은 현재 노드에서 목표 노드에 도달하는 데 소요될 비용을 추정하는 휴리스틱 함수입니다. 따라서 h(n)은 학습된 추측이며 A* 알고리즘의 성능을 결정하는 데 매우 중요합니다. g(n)과 h(n)의 합인 f(n)을 기반으로 시작 노드에서 끝 노드까지의 총 비용을 추정할 수 있습니다.
f(n) = g(n) + h(n)
f(n): 시작 노드에서 목표 노드까지의 추정된 총 비용g(n): 시작 노드에서 노드 n까지 실제 소요된 비용h(n): 노드 n에서 목표 노드까지 소요될 추정된 비용
이 알고리즘은 최소 f(n)값을 갖는 노드를 다음 탐색할 현재 노드로 선택하고 발견한 노드에서 더 나은 경로가 발견되면 g(n) 및 h(n)을 지속적으로 업데이트합니다. 이 과정은 알고리즘이 목표 노드에 도달할 때까지 계속됩니다.
A* 알고리즘 vs 다익스트라(Dijkstra's) 알고리즘
A* 알고리즘은 시작 노드와 목표 노드 사이의 최단 경로만 찾는 반면, Dijkstra 알고리즘은 그래프의 모든 노드가 목표 노드기 때문에 시작 노드에서 다른 모든 노드까지의 최단 경로를 찾습니다.
A* 알고리즘은 휴리스틱을 사용하여 목표 노드로 향하는 올바른 방향으로 안내하기 때문에 Dijkstra 알고리즘보다 빠르게 실행됩니다. 그러나 Dijkstra 알고리즘은 목표 노드에 대한 사전 지식이 없기 때문에 사용 가능한 모든 방향으로 고르게 확장되며 항상 이미 소요된 비용이나 거리를 기준으로 시작 노드에 가장 가까운 노드를 계산합니다.
그래프 설명
휴리스틱은 A* 알고리즘의 성능에 매우 중요합니다. 여기서는 데모 목적으로만 휴리스틱 기능을 사용합니다.
- 1단계
a: 시작 노드까지의 거리를 0으로 설정하고 다른 모든 노드까지의 거리를 무한대로 설정합니다.
b: 시작 노드의 f 값을 계산하고 이전 노드를 none/nil/null로 설정합니다.
c: 처음에는 비어 있는 열린 목록과 닫힌 목록을 초기화합니다.
2단계: 시작 노드를 열린 목록에 넣습니다.
3단계
a: 열린 목록에서 최소 f(n)값을 갖는 노드를 찾아 목록에서 제거합니다. 이 노드를 현재 노드로 표시합니다.
b: 현재 노드가 대상 노드인지 아닌지 확인합니다.
c: 현재 노드의 모든 이웃 노드를 채우고 각 이웃 노드에 대해 다음을 확인합니다.
1. 이웃 노드가 닫힌 목록에 있나요?
- 네. 이 노드를 건너뜁니다.
- 아니요. 2로 이동합니다.
2. 이웃 노드의 g 값을 계산하고 더 나은 경로가 있는지 확인합니다. 더 나은 경로(더 낮은 g 값)를 찾았나요?
- 아니요. 이 노드를 건너뜁니다.
- 네. 3으로 이동합니다.
3. 이웃 노드의 g, h, f 값을 계산하고 현재 노드를 이전 노드로 설정합니다.
4. 이웃 노드가 열린 목록에 있는지 확인합니다.
- 네. 열린 목록에서 이웃 노드의 g, h, f 값을 업데이트합니다.
- 아니요. 이 이웃 노드를 열린 목록에 삽입합니다.
- d: 현재 노드를 다음 노드로 확장했으므로 현재 노드를 닫힌 목록에 배치합니다.
- 4단계: 대상 노드에 도달할 때까지 3단계를 반복합니다.
데모 반복 1회 차
데모 반복 2회 차
데모 반복 3회 차
데모 반복 4회 차
데모 반복 5회 차
최종 결과
결국 이전 노드를 기록했으니 이를 통해 최단 경로를 역추적할 수 있습니다. 이 데모에서는 A* 알고리즘을 사용하여 그래프를 모두 탐색하지 않고 최단 경로를 탐색합니다. (아직 노드 4를 검사하지 않았으므로 노드 4가 열린 목록에 있는 것을 볼 수 있습니다). 이건 그래프의 모든 노드를 확장해야 하는 Dijkstra 알고리즘과 다릅니다.
Dijkstra 알고리즘에 대한 자세한 내용은 여기에서 확인할 수 있습니다.
코드 구현
자료 구조
우선순위 큐를 통해 각 실행에 대해 가장 낮은 f값 노드를 가져옵니다. 이 데모에서는 최소 힙 자료 구조를 사용하여 코드를 구현합니다.
복잡도
시간 복잡도: O(nlog(n)), 공간 복잡도: O(n)n: 그래프 내에서 노드 개수
의사코드
# 시작 노드를 포함하는 최소 힙을 초기화
minHeap = MinHeap([start])
While minHeap is not empty:
# 최소 힙에서 최소 f값을 가지는 노드를 가져온 후 현재 노드로 표시
current = minHeap.pop()
# 현재 노드가 목표 노드인지 확인
if current == target:
break
# 현재 노드의 모든 이웃을 채우기
for neighbor in current.neighbors:
compute neighbor's g, h, f value
if neighbor in minHeap:
if neighbor.g < neighbor.g in minHeap:
update minHeap
else:
insert neighbor into minHeap
Golang
힙 자료 구조를 사용하여 시작 노드까지 거리가 가장 짧은 노드를 선택하면 닫힌 목록이 중복됩니다. 확장 노드에 도달하기 위한 최단 거리를 이미 찾았기 때문에 최소 힙에 다시 추가할 필요는 없습니다. (노드를 향한 더 짧은 경로를 찾으면 최소 힙에 추가합니다).
따라서 코드에서 닫힌 목록을 제거할 수 있습니다. (코드에서 닫힌 목록과 관련된 코드는 주석 처리했습니다).
- 메인 코드
- 최소 힙
Python
- 메인 코드
- 최소 힙
전체 코드는 여기에서 보실 수 있습니다.
아래에서 다른 최단 경로 알고리즘들도 확인하실 수 있습니다.
