A* 알고리즘 설명
해당 설명에 사용된 프로그램 포함 글

A* 알고리즘을 Flow Chart로 발표하라는 과제가 주어졌다. JAVA GUI로 미로탐색 시스템(길찾기 프로그램)을 구현해야한다. 저번 비트 1차 과제로 N 퍼즐을 구현했을때 A*를 사용했었는데, 개념을 정확히 잡지 못하고 넘어간 부분이라 이번에 제대로 한번 알아보게 되었다.

A* 알고리즘

• BFS 알고리즘의 한 예로, 휴리스틱(h) 값을 이용해 최단 경로를 추정해 나가는 방식 BFS의 특성과 함께 Dijkstra의 알고리즘을 확장시킨 개념

• 최단 경로 탐색에 제일 많이 쓰이는 알고리즘이다.

• 한 지점을 노드라고 표현하고, 초기 노드에서 목표 노드로 가는 경로 중 가장 최단 경로를 찾기 위해 사용한다.

• 공식 F = G + H

  • G : 시작점 A로부터 현재 사각형까지의 경로를 따라 이동하는데 소요되는 비용
  • H : 현재 사각형에서 목적지 B까지의 예상 이동 비용 (사이에 벽, 물 등으로 인해 실제 거리는 알지 못하지만 그들을 무시하고 예상 거리를 산출한다.)
  • F : 현재까지 이동하는데 걸린 비용과 예상 비용을 합친 총 비용

• H 추정

  다양한 방식으로 추정 할 수 있으나, 해당 글은 맨하탄 방식으로 사용한다.

  • 맨하탄 방식이란? 목적지까지 남은 거리를 셀 때 오로지 상,하,좌,우 방향에 존재하는 노드만 세는 방식 값을 구하는 공식은 각 노드들의 |x좌표의 차| + |y 좌표의 차|가 된다.

    

    예시) 여행자의 위치에서 맥주까지의 거리는 x좌표로 3, y좌표로 3 떨어져 있으므로 총 남은 거리는 6이된다.