티스토리 뷰

A* 알고리즘은 f (=g+h)값이 가장 작은 것을 향해 나아가는 알고리즘이다.
먼저, 어떤 상태에서 최적인 목표 G까지의 평가함수 f(G)가 있다고 가정한다.
그 다음 G보다는 덜 최적화된 결과인 H까지의 평가함수 f(H)가 있다고 가정한다.
이 경우 f(H) > f(G) 이다.
마지막으로 A* 알고리즘이 H를 선택하였다고 가정해 보자.
여기서 G로 가는 길 중간의 노드 n이 있다고 할때, 평가함수 f 중의 h가 admissible(실제 결과값 보다 항상 작다) 하기 때문에 f(G) > f(n) 이다.

여기에서 모순이 발생하게 된다.
f(H)로 갔다는 것은 A*알고리즘이 f(n)보다 작기 때문에 선택했다고 볼 수 있기 때문에, f(n) > f(H) 이다.
위에서 f(G) > f(n)이라고 하였고 f(n) > f(H) 라면 결과적으로는 f(G) > f(H) 가 되는데 그러면, 위쪽의 가정 f(H) > f(G)에 모순이 된다.
그렇기 때문에 A* 알고리즘은 h함수가 admissible하다면 항상 최적인 값을 찾아낼 수 있다.




출처 : http://rhasya.egloos.com/tb/2561130

'기억하자정보 > 알고리즘' 카테고리의 다른 글

A* 알고리즘 요약  (0) 2006.12.26
A* 알고리즘  (0) 2006.12.26
최단 경로 다익스트라 알고리즘  (0) 2006.12.26
최단경로 구하기  (0) 2006.12.26
A-star algorithm  (0) 2006.12.26
댓글
안내
궁금한 점을 댓글로 남겨주시면 답변해 드립니다.