A* 알고리즘

A*알고리즘

시작 지점에서 목표 지점까지 이동하는 경로를 찾는 탐색 알고리즘
게임 캐릭터 이동, 로봇의 경로 탐색, 네비게이션 등에서 활용

A* 는 지금까지 실제로 이동한 비용과 목표까지 남았다고 예상하는 비용을 함께 사용하여,
이를 통한 불필요한 방향의 탐색을 줄이는 탐색

A* 속도적인 측면에서도 좋고,, 최단경로를 빨리 구할 수 있도록 하는 알고리즘이 많이 등장함

A*에서 사용하는 비용

• g(n) : 시작 노드에서 현재 노드까지 실제로 이동한 누적 비용
• h(n) : 현재 노드에서 목표 노드까지 남았다고 추정한 비용
• f(n) : 해당 노드를 거쳐 목표까지 이동할 것으로 예상되는 전체 비용
• f(n) = g(n) + h(n)

Open 목록, Closed 목록

A* 에서는 탐색할 노드를 관리하기 위해 2개의 목록을 사용
Open 목록 : 앞으로 확인할 후보 노드 저장

• fCost가 가장 작은 노드를 다음 탐색 대상으로 선택
• 같은 노드로 가는 더 저렴한 경로 발견시, 해당 노드의 비용과 이전 노드 정보 갱신
  Closed 목록 : 확인을 마친 노드를 저장

A*알고리즘 동작 과정

1. 시작 노드 Open 목록에 추가
2. Open 목록에서 fCost가 가장 작은 노드 선택
3. 선택한 노드가 목표 노드면 탐색 종료하고 경로 복원
4. 현재 노드와 인접한 노드들의 gCost, hCost, fCost 계산
5. 처음 발견한 노드이거나, 더 저렴한 경로를 발견한 경우 이전 노드 정보 갱신 후 Open 목록에 추가
6. 현재 노드를 Closed 목록으로 옮기고 목표에 도달할 때까지 과정 반복

휴리스틱

h(n) 처럼 목표까지의 남은 비용을 추정하는 방법

가로 세로(상하좌우) 값 구해서 그 길이값을 비용으로 사용하는거 : 맨해튼 거리
적절한 휴리스틱을 사용하는게 중요 (그럼 다익스트라 탐색보다 범위 줄일 수 있음)