[알고리즘] A* 알고리즘

 

알고리즘 개요 및 소개

A* 알고리즘 gif [1]

A*(에이 스타) 알고리즘 1968년에 만들어진 것으로 AI 학계에서는 이 알고리즘을 이용해서 다양한 문제들을 해결해 왔다. 특히 유명한 문제는 15 퍼즐이 있으며 게임 개발자들에게 A*는 효율적인 길 찾기 알고리즘으로 애용된다.

A* 알고리즘은 아직 조사하지 않은 상태들 중 가장 유망한 상태를 조사하는 과정을 반복하며 반복을 진행하며 그 상태가 목표이면 알고리즘은 끝나고 그렇지 않으면 그 상태의 인접한 상태를 조사해 나간다. [2]

 

 

다익스트라 알고리즘과의 차이점

다익스트라 알고리즘은 최단경로를 찾는 알고리즘이지만 특정한 목적점 하나를 명시하지 않고 하나의 시작점만 주면 다른 모든 정점에 이르는 최단거리를 구한다. 하지만 이러한 다익스트라의 단점은 시작점에서의 모든 정점에 대한 최단 경로를 구하기 때문에 불필요한 탐색을 하게 된다.  또한 다익스트라는 h(x)(휴리스틱 값)이 0인 상태의 A* 알고리즘이라고도 할 수 있다. [3] 

 

A*의 특징 및 단점

A*는 두 종료의 상태 목록들을 관리한다. 

아직 조사하지 않은 상태들을 담은 '열린 목록'(Open List), 이미 조사한 상태들은 담은 '닫힌 목록'(Closed List)

을 가지고 있으며 시작 지점으로부터 현재 상태에 이르는 가장 싼 비용 g(x)와 현재 상태로부터 가장 싼 비용 h(x) 이 둘을 더해서 가장 싼 추정 비용을 가지는 상태를 찾아서 이동하는 과정을 반복함으로 써 가장 싼 비용의 최종 경로를 찾는다. [2]

: f(x)=g(x)+h(x)

A*는 h(x)가 실제치보다 크지 않다면 A* 알고리즘은 최적의 해를 보장한다.

 

A*는 현명하게 사용하지 않으면 시간 낭비가 될 수도 있다. 맵의 크기가 크면 '열린' 목록이나 '닫힌' 목록에 수백에서 수천 개의 노드들이 들어갈 수도 있으며, 그렇게 되면 상당한 메모리를 잡아먹으며 A*는 상당히 많은(실시간 게임에서는 허용할 수 없을 정도의) CPU 시간을 잡아먹는다. [2]

 

 

h(x) 휴리스틱

휴리스틱 비용이 실제 비용보다 크면 "일단 목표 쪽으로 돌진하면서 길을 찾는" 방식으로 검색이 수행되며 휴리스틱 비용이 실제 비용보다 작으면 "돌아가는 길이 더 빠를 수도 있으니 최대한 많은 가능성들을 시험해 보는"방식으로 수행된다.[2]

 

휴리스틱을 추정하는 대표적인 방법은 유클리드 거리(Euclidean distance)= Sqrt(x2-x1)^2+(y2-y1)^2 방식과

맨해튼 거리(Manhattan distance)= |x2-x1| + |y2-y1| 방식이 있다.

 

A*는 휴리스틱 비용에 따라서 성능의 차이가 발생하기 때문에 여러 번의 실험을 통해서 휴리스틱 비용을 조정해야 한다.

다음은 휴리스틱 값에 따른 A* 알고리즘의 탐색 성질을 볼 수 있다. [2]

 

h(x)=0

휴리스틱이 0인 경우는 시작 지점을 중심으로 한 원을 이룬다. 다익스트라 알고리즘과 비슷하게 작동하는 것을 확인할 수 있다.

 

 

h(x)를 유클리드 거리로 계산한 경우

휴리스틱 비용을 유클리드 거리를 사용하면 검색 노드의 모양은 시작과 목표를 초점들로 하는 타원 형태가 된다.

 

 

h(x)를 과대평가한 경우

휴리스틱 비용을 과대평가하면 시작과 목표를 양 끝 모서리로 하는 마름모나 육각형 모양이 된다.

 

 

프로젝트 진행 및 후기

A* 알고리즘에 대해서 간단하게 정리하였다. A* 관련 정리 글은 구글에 검색을 하거나 알고리즘 책을 보면 자세히 나와있기 때문에 간단하게 요약을 진행했고 이러한 A*를 시뮬레이션할 수 있는 프로젝트를 진행할 예정이다. 프로젝트는 쥐 가 치즈를 먹기 위해서 벽을 피해 최단거리로 찾아가는 것을 확인할 수 있도록 만들 예정이며 마우스를 통해 쥐, 치즈, 벽을 자유롭게 배치할 수 있도록 할 예정이다.

 

프로젝트에서 사용할 자체 제작 그림

 

 

 

출처 및 레퍼런스

[1] [Wiki] https://en.wikipedia.org/wiki/A*_search_algorithm

[2] [Mark Deloura] [GAME PROGRAMMING GEMS]: 정보문화사

[3] [문병로] [쉽게 배우는 알고리즘 관계 중심의 사고법]: 한빛아카데미

 

 

관련 글(알고리즘)

[자료구조 알고리즘/탐색 알고리즘(Search)] - [알고리즘] 깊이 우선 탐색(Depth First Search)

[자료구조 알고리즘/탐색 알고리즘(Search)] - [알고리즘] 너비 우선 탐색(Breadth First Search)

[자료구조 알고리즘/탐색 알고리즘(Search)] - [알고리즘] 다익스트라 알고리즘(Dijkstra algorithm)

 

관련 글(A* 프로젝트)

[자료구조 알고리즘/탐색 알고리즘(Search)] - [알고리즘] A* 치즈 찾기-맵 툴

[자료구조 알고리즘/탐색 알고리즘(Search)] - [알고리즘] A* 치즈 찾기-PathFinding

[자료구조 알고리즘/탐색 알고리즘(Search)] - [알고리즘] A* 치즈 찾기-PathFinding2