A* Algorithm

경로탐색 알고리즘 중 하나로, 시작점부터 목표점까지의 최단경로를 찾는데 사용되는 알고리즘 으로,

 

그래프 탐색 알고리즘중 하나이다.

 

목표 꼭짓점까지 가는 최단경로를 찾아내는 알고리즘으로, 각 꼯짓점에 대해 그 꼭짓점을 통과하는 최상의 경로를 추정하는 휴리스틱( huristic )추정값을 매기는 방법을 사용한다.

 

기본적인 개념은 다이스트라 알고리즘과 비슷하게 들어간다.

 

기본정의

 

시작지점에서 목표지점까지 가는 최단경로를 찾는데 사용되는 알고리즘이다.

 

f(n)이 최소가 되는 노드를 우선해서 탐색한다. f(n) = g(n) + h(n)이며,

g(n) = start -> n 까지의 비용

h(n) = n에서 End까지의 비용이다.

 

휴리스틱 함수

휴리스틱은 정해진 알고리즘을 사용하여, 가능한 최소비용에 대한 해를 구하는 방식이다.

 

예를들면, 최단경로를 찾을 때, 현재위치에서 목표까지의 직선거리가 최대 휴리스틱 값 이라고 할 수 있다.

 

휴리스틱의 결과는 실제비용보다 작거나 같아야한다.

 

동작방식

 

OpenList가 비어있지 않는 한, 계속해서 반복해 수행한다. 제귀함수형태

 

1. 현재 Node 와 목표Node가 일치하는지 확인
   • 현재 Node와 목표Node가 일치하면 경로를 완성하고 제귀종료
2. 이웃Node 탐색
   • 현재 Node와 이웃 Node를 탐색한다. 각 이웃 Node에 대해 작업을 수행한다.
   • 이웃 Node가 CloaseList에 속해있는지 확인(이동이 가능한지 확인) 한 후, 존재한다면 무시
   • 이웃 Node가 OpenList에 속해있지 않다면, 리스트에 추가하고, 비용과 휴리스틱값을 계산.
   • 이미 OpenList에 있다면, 현재 경로를 통해 이웃에 도달하는 비용을 비교하고, 더 낮은 비용으로 도달할 수 있다면, 경로를 재계산한다.
   • 현재 Node를 닫힌 리스트로 이동시킨다.
3. 경로 완성
   • 목표에 도달하면 최종 경로를 생성한다. 그로서, 목표Node에서 시작Node로 역으로 거슬러 올라가며 경로를 구성한다.

휴리스틱 을 사용하여, 최적의 경로를 찾고, 우선순위 큐나 힙을 사용하여 노드를 정리하여 탐색속도를 향상시킨다.

 

A*알고리즘에서 사용되는 Node는 Map에 격자형으로 설치되고, 해당 격자에서 인접노드를 탐색하는 식으로 동작한다.

 

그럼으로, 다이스트라 알고리즘과 다르게, 전방위 탐색이 아닌, 제한적 부분탐색의 형태로 진행된다.

 

예시를 통해 더 쉽게 이해해보자.

먼저, 각 Node가 다음과 같은 데이터를 가진다고 가정한다.

Index

F

G

H

From

vector<edges>

여기서 edges는 다음과 같은 항목을 가진다.

struct edges

{

     int index;

     int cost;
}

vector<int> via

via는 지나친 경로를 의미한다. 현재 지나친 경로들을 기록하여. 최종도착시 사용한다.

State.

여기서 State는 다음과 같은 상태값을 가진다.

None, Open, Close, Using, Obstruction

 

Node의 규칙은 다음과 같다.

1. Node는 8방위로 인접한 node를 가진다.
2. Node는 인접한 node끼리만 연산한다.
3. Node는 연산시, None, Open 인 Node만 연산이 가능하다.
4. Node는 인접연산 종료시 Close상태로 변환된다.

상 하 좌 우 는 각 Cost가 1로, 대각선은 루트2임으로 약 1.41로 계산한다.

 

H의 경우, 대각선 이 아닌 직선거리로 계산한다.

방식은 맨하탄 거리측정 방식을 사용한다.

		O			E
		O
		O
S		O

S = 시작점

O = 이동불가지점

E = 종료지점

 

으로 연산해보자.

 

1연산

		O			E
		O
8	7.4	O
S	8	O
10	9.4

 

2연산

		O			E
8.8	8.4	O
8	7.4	O
S	8	O
10	9.4

 

3연산

		O			E
8.8	8.4	O
8	7.4	O
S	8	O
10	9.4	9.4

 

4연산

10.8	9.4	O			E
8.8	8.4	O
8	7.4	O
S	8	O
10	9.4	9.4

 

5연산

10.8	9.4	O			E
8.8	8.4	O
8	7.4	O
S	8	O
10	9.4	9.4	9.4

 

6연산

10.8	9.4	O			E
8.8	8.4	O
8	7.4	O
S	8	O	9.4
10	9.4	9.4	10.4

 

7연산

10.8	9.4	O			E
8.8	8.4	O
8	7.4	O	9.4	8.8
S	8	O	9.4	9.4
10	9.4	9.4	10.4

 

8연산

10.8	9.4	O			E
8.8	8.4	O		8.8	8.2
8	7.4	O	9.4	8.8	8.8
S	8	O	9.4	9.4
10	9.4	9.4	10.4

 

9연산

10.8	9.4	O			E
8.8	8.4	O		8.8	8.2
8	7.4	O	9.4	8.8	8.8
S	8	O	9.4	9.4
10	9.4	9.4	10.4

 

이렇게 하여 목표점까지 도착하고, 이동하는 경로중 최단경로를 역순으로 추정하면 다음과 같이 연결된다.

		O			E
		O			ㅁ
		O		ㅁ
S	ㅁ	O	ㅁ
		ㅁ