A* 알고리즘

A* 탐색 알고리즘 A s* search algorithm 개요

- 초기 노드에서 목표 노드까지 경로 찾는 그래프 탐색 알고리즘

- 목표 노드까지 가장 좋은 경로 estimate of the best route 하기 위해 각 노드에 랭킹 부여하는 heuristic estimate를 사용하고, 그 순서를따라 노드 방문

 

 

A* 알고리즘의 장점

- 최단 거리 찾기 문제에서 다른 알고리즘(다익스트라, best-first search)보다 훨씬 빠름

 

 

A* 알고리즘 개발 배경

- 휴리스틱 방법(의사 결정시 해당 문제에 대한 정보를 이용하는것)

+ 형식적 방법(formal method : 문제 관련 정보를 사용하지 않지만 정형 분서이 될수있는것)을 결합하기 위해 1968년 개발

 

 

A* 알고리즘의 구조

- 그래프 탐색 알고리즘

- 타 그래프 탐색 알고리즘과 차이는 목표에 얼마나 근접한지 평가하기위해 휴리스틱 함수를 사용함

-> 휴리스틱에 의해 먼저 바람직한 방향을 탐색, 그 방향이 실패하면 다른 경로를 찾음

 

 

A*의 활용

- 경로 탐색기로 많이 사용

- 공간안 특정 상태에서 인접한 상태를 조사해 나가면서 목표 상태까지 가장 싼 비용의 경로를 찾음