A-star algorithm

출처: http://en.wikipedia.org/wiki

A-star algorithm은 초기노드에서 목표노드까지의 경로를 찾는 graph searching algorithm.

Best-first search의 한 종류인데, 그러면 best-first search는 과연 무엇인가?

Best-first search

: 어떤 rule에 따라서 가장 promising하다고 판단된 노드부터 먼저 방문하는 depth-first search를 최적화하는 graph search 알고리즘이다. 이때 어떤 rule이란, 노드에 대한 extra 정보를 의미함으로써, heuristic function을 정의한다. Dijkstra의 shortest path finding 알고리즘도 best-first search의 종류에 속한다고 한다. 하지만 Dijkstra는 지나온 path의 cost만 고려함으로써, heuristic  function은 고려하지 않는다.

이에 반해, 같은 best-first search 알고리즘에 속하면서 A-star algorithm은?

A-star algorithm

: f(n) = g(n) + h(n) 이 가장 minimize 되는 node부터 먼저 expanding. 즉, 지나온 node들의 cost와 목표 node까지의 cost를 함께 고려함으로써, computationally optimal하지는 못하지만(더 available한 information이 있을 때, A-star보다 더 좋은 complexity로 path를 찾아주는 알고리즘이 있다고 하는데...) 그래도, heuristic function이 실제 목표노드에 도달할 때까지의 cost를 overestimate하지 않는다면, A-star는 admissible(시작노드에서 목표노드까지 path가 존재한다면 항상 찾아준다)하다. Optimal이라는 말은, 가장 짧은 경로를 찾아준다는 말인데, 그렇단다.

출처 : http://blog.naver.com/allisabeth?Redirect=Log&logNo=90008015721