A-star 알고리즘

A* 알고리즘이란??

 

- 전산학 분야에 있어서 A* 알고리즘은 주어진 출발지 노드에서부터 목적지 노드까지의

  최단 경로를 찾아내는 그래프/트리 탐색 알고리즘 중 하나이다.

 

 

 

 

 

초록색 : 시작점

검은색 : 장애물

빨간색 : 도착점

 

길찾기 순서

 

1. 시작점에서 검색 된 사격형을 열린목록에 추가한다.

 

2. 시작점 근처에 붙어있고 지나갈 수 있는 모든 사각형들을 본다.  그리고 그 지나갈 수 있는 사각형들을 열린목록에 추가한다. 추가된 각각의 사각형들에게 지점A를 부모사각형이라고 저장함

(부모사각형은 나중에 길을 찾으며 거슬러 올라갈 때 중요하다.)

 

3. 시작점을 열린목록에서 빼고 필요없는 사각형들을 닫힌목록에 추가한다.

 

 

위의 그림은 인접한 모든 노드를 검색한 후 열린목록에 추가된 그림을 보여주는데

8개의 방향으로 검색이 된다. 

이제 이 다음 열린목록에 있는 인접한 사각형을 선택하게 되며, 앞에서 했던 내용들을 반복해서

수행하며 길을 찾게 된다.

 

사각형을 선택하게 될 때는 F비용에 가진 것을 선택하게 된다.

 

 

A* 알고리즘의 평가 함수

 

평가 함수 F(n) = G(n) + H(n) , F는 비용이다.

 

G(n) : 출발 노드로부터 노드 n까지의 경로 비용(Goal)

시작점으로 부터 새로운 사각형까지의 이동비용 (길을 찾아갈수록 G의 값은 커진다. 시작점으로부터 멀어지므로)

 

H(n) : 노드 n으로부터 목표 노드까지의 추정 경로 비용(Heuristic)

얻어진 사각형으로부터목적지까지의 예상이동비용( H는 모든 장애물에 대해서 고려하지 않고 현재 사각형에서 목적지까지의 거리를 계산할 때, 대각선이동이 아니라 가로세로이동에 대한 비용으로 계산하는 것임 )

 

위의 공식처럼 계산해보면 이런 식으로 값이 나온다. (가로세로의 값을 임의로 10이라고 가정하고 계산하였다.)

 

 

이제 이 공식으로 계속 길찾기를 해야한다.

열린목록에 있는 사각형에서 가작작은 F비용을 가지고 있는 사각형을 선택하고

그 사각형을 열린목록에서 빼고 닫힌목록에 추가한다.

(그 선택된 사각형은 부모노드가 되어서 자식노드를 생성할 준비가 된 것이다.)

 

다시 인접한 모든 사각형을 검색해서 닫힌 목록에서 있거나 장애물을 제외한 나머지 중에서

열린목록에 없는 사각형을 열린목록에 추가한다.

위에서 가장 작은 F비용을 가진 사각형을 열린목록에 추가된 새로운 사각형들의 부모로 만든다.

 

만약에 인접한 사각형중에서 이미 열린목록에 있는 사각형이 있으면 그 사각형으로 가는 길이 더 좋은 길인지 확인한다.(하나씩 길을 찾을 때마다 중복이 되는 노드가 있는데 그 노드를 체크해야 한다.)