개념
A star 알고리즘은 현재까지 온 비용과 목표까지 남은 비용 추정치를 함께 고려하는 휴리스틱 탐색 알고리즘이다.
평가 함수
A star는 다음 평가 함수를 사용한다.
- g(n): 시작 상태에서 현재 노드 n까지 온 실제 비용
- h(n): 현재 노드 n에서 목표까지 남은 비용의 추정치
- f(n): 전체 경로 비용의 추정치
왜 중요한가
최상 우선 탐색은 h(n)만 보고 목표에 가까워 보이는 노드를 고른다. 하지만 실제로 돌아온 비용이 너무 크면 좋은 경로가 아닐 수 있다. A star는 이미 지나온 비용 g(n)을 함께 보므로 더 균형 잡힌 선택을 한다.
예시
8-Puzzle에서는 h(n)으로 목표 위치와 다른 타일 수나 맨해튼 거리를 사용할 수 있다.
로봇 경로 계획
로봇 경로 계획은 현재 위치에서 목표 위치까지 장애물을 피하는 경로를 계산하는 문제이다. 격자 지도에서 각 칸을 상태로 보고 상하좌우 이동을 연산자로 두면, A star로 목적지까지의 경로를 찾을 수 있다. 장애물 칸은 지나갈 수 없는 상태로 처리한다.
전체 지도에서 큰 경로를 정하는 전역 경로 계획과 실제 이동 중 가까운 장애물이나 동적 상황에 대응하는 지역 경로 계획을 구분할 수 있다.