A* 길찾기 휴리스틱 개선: 삼각 부등식으로 탐색 공간 줄이기
Improving Heuristics for A* Pathfinding
A* 길찾기 최적화는 보통 우선순위 큐나 맵 표현에 집중하지만, 휴리스틱 함수 개선도 큰 효과를 낼 수 있습니다. Red Blob Games의 이 글은 랜드마크를 활용해 휴리스틱을 개선하는 방법을 설명합니다. 미리 계산한 랜드마크까지의 최단 거리와 삼각 부등식을 이용하면, A*가 탐색하는 노드 수를 크게 줄일 수 있습니다. 여러 랜드마크를 배치하고 max()를 취하면 더 좋은 하한을 얻을 수 있습니다. 랜드마크 배치는 프로젝트 특성에 따라 달라지며, 자동 배치 알고리즘도 소개합니다. 구현은 Dijkstra 알고리즘으로 거리 테이블을 만들고 휴리스틱 함수만 수정하면 되므로 A* 코드는 변경할 필요가 없습니다.
A*가 올바른 방향으로 안내할 때는 빠르게 실행되지만, 잘못된 방향으로 안내할 때는 시간을 낭비합니다. 그런데 왜 잘못된 방향일까요? 일반적인 거리 기반 휴리스틱은 벽을 알지 못하기 때문입니다.
- simonw
> 2007년에 이 기법을 배웠고, 2015년에 글로 정리하려고 시도했습니다. 설명할 수 있을 만큼 충분히 이해하지 못했다는 것을 깨달았습니다. 2016년, 2018년, 2019년, 2022년, 2024년, 2026년에 틈틈이 공부했습니다. 이 페이지를 여러 번 포기하고 다시 시작했습니다. 그리고 2026년에 이제 이 페이지를 쓸 만큼 충분히 이해했다고 생각합니다.
훌륭합니다.
- lokar
df를 예로 사용하지만, (다른 예들과 달리) 두 지점 사이의 유효한 경로 집합이 끊임없이 변할 수 있다는 문제가 있습니다.
- LPisGood
보통 오타를 지적하지는 않지만, 이 오타는 잠재적 개선의 규모를 파악하기 어렵게 만듭니다:
> A*가 탐색해야 하는 노드 수가 12693에서 12693으로 감소합니다.