[CS]A* Algorithm

A* 알고리즘

• 그래프의 최단 경로 문제를 푸는 알고리즘
• 다익스트라에서 발전됨

Dijkstra와의 차이

• Dijkstra:
  • 현재 정점과 다음 정점 사이 가중치(ex.거리)
  • 만을 고려해 최단 경로 결정
• A*:
  • 현재 정점과 다음 정점 사이 가중치와
  • 현재 정점에서 목표 지점까지의 거리(휴리스틱 코스트(heuristic cost)도 고려해
  • 최단 경로 결정
• 결론: 불필요한 경로 탐색 감소

예시

• S는 Start
• G는 Goal

DijkstraDijkstra 예시

• 각 정점 간 코스트 = 1
  

• 파랑색 경로: 탐색한 경로

• 주황색 경로: 최단 경로

• 결론: 3가지 탐색 루트가 나옴

A* 예시

• 시작 지점을 탐색 완료로 설정
  

• 인접 지점의 코스트 계산

• 코스트 = 정점간 거리 + 이동 시, 도착지까지의 거리

  • 오른쪽, 아래는 도착지 방향
  • 위쪽은 도착지 반대 방향이므로 1 증가
    

• 최소 거리인 다음 정점 선택
  

• (반복)...
  

• (반복)...

결과

• Dijkstra보다 효율적인 길찾기
• 휴리스틱 코스트(위 예시에선 목표 지점까지의 직선 거리가 있어야 적용 가능한 길찾기 알고리즘
• 휴리스틱 코스트의 설정에 따라 값이 바뀜
  - 잘못된 휴리스틱 코스트 설정이 탐색 효율을 악화시킬 수도 있음
  

활용

• 2D 게임 프로그래밍에서 길찾기(Path Finding)에 주로 사용
• 계산량이 많아 게임 성능에 악영향을 미칠 수 있음