경로 탐색 알고리즘 - A*

A* 알고리즘

다익스트라 알고리즘을 확장하여 만들어진 경로 탐색 알고리즘이다

 

추정치를 안 쓰는 알고리즘

다익스트라 알고리즘으로 탐색하다가 지정한 목적지를 탐색했을 경우 탐색을 종료한다

메모리는 다익스트라보다 더욱 쓰지만 탐색 횟수는 줄어든다

하지만 탐색한 경로가 정말로 최단 경로인지는 보장할 수 없다

 

추정치를 쓰는 알고리즘

다음 노드로 이동하는 비용을 휴리스틱이라는 추정치로 두고 탐색하는 방법이다

현재의 비용 + 휴리스틱 비용으로 탐색한다

 

자주 사용하는 휴리스틱 함수는 휴리스틱 유클리드 맨하탄이다

 

SSS