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

A* 알고리즘이란?

---

Dijkstra 알고리즘의 확장판으로 Best-First 검색을 이용해 시작점->도착점 까지의 가장 적은 비용을 사용하는 경로를 찾음

- 조사하지 않은 node중 가장 효율적이라 판단되는 node를 찾음

- 찾은 node가 도착점이면 종료, 아니면 인접 node들 중 다시 찾음

- 조사한 node들은 close list에 저장, 조사하지 않은 node들은 open list에 저장

 

** Dijkstra 알고리즘은 시작노드만 지정하고 다른 모든 노드에 대한 최단 경로를 파악,

A* 알고리즘은 시작노드와 목적지 노드를 분명하게 지정하여 이 두 노드간의 최단 경로를 파악한다는 것이 다르다!

 

 

<원리>

- 각 정점은 목적함수값 g(x)를 가지고있으며 best-first 검색을 통해 g(x)값이 가장 좋은것부터 방문한다.

- 목적지 노드에 이르는 "잔여 추정 거리 h(x)"를 고려한다

   * 추정치 h(x)는 실제치보다 크면 안된다!

- 노드 x를 평가-> f(x) = g(x) + h(x)

 

 

< example >

 

 

1. 각 인접 노드의 f(x)를 비교한 결과 23+34=57로 가장 적은 가중치 23노드가 선택됨
2. 다음으로 f(x)가 좋은 노드 f(x)=60이 선택, 23+18 = 41이 됨
3. 그 다음은 노드가 하나뿐이라 자연적으로 41+20=60이 목적지 노드까지의 최단거리가 된다

 

 

<참고>

http://www.gisdeveloper.co.kr/?p=3897 

최단 경로 탐색 – A* 알고리즘 – GIS Developer