티스토리 뷰

  A*는 맵을 탐색하면서 맵의 여러 위치들에 해당하는 노드들을 만들어 나간다. 이러한 노드들은 검색의 진행 상황을 기록하는 용도로 쓰인다. 노드들은 맵의 위치를 저장할 뿐만 아니라,흔히 f, g, h라고 부르는 중요한 세 가지 속성들도 저장한ㄷ. f, g, h는 각각 fitness(적합도), goal(목표), heuristic(휴리스틱) 값들을 의미한다. 이 값들을 좀더 설명하자면 :

  g는 시작노드로부터 이 노드까지 오는 데 드는 비용이다. 시작 노드에서 맵의 이 이치까지 오는 경로들은 여러 개가 있을 수 있는데, 이 노드는 그 경로들 중 특정한 하나를 의미한다.

  h는 이 노드에서 목표까지 가는데 드는 '추정된' 비용이다. 이때 h는 휴리스틱을 의미하며, 휴리스틱이란 '경험에 기초한 추측'을 뜻한다. 이것이 '추측된' 비용인 이유로 목표까지의 실제 비용을 아직은 알지 못하기 때문이다.(아직 최단 경로를 찾지 못했으므로).

  f는 g와 h의 합으로. 이 노드를 거쳐 가는 이 경로의 비용에 대한 최선의 추측을 의미한다 f 값이 낮을 수록 이 경로가 진짜 최단 경로일 가능성이 크다.


  g는 지금까지 오는데 드는 비용이므로 완전히 정확한 값을 계산할 수 있다. 그러나 h는 이 노드에서 목표까지 얼마나 더 가야 할 지 알 수 없으므로, 추측이 불가피하다. 추측이 정확할 수록 f의 값은 실제 값에 가까워지며, 그럴 수록 A*는 좀더 빠르게, 불필요한 노력을 좀더 덜 들여서 목표에 도달할 수 있다.


알고리즘

A*의 기본적인 알고리즘은 다음와 같다

1. 시작 지점을 노드 P로 둔다.

2. P에 f, g, h 값들을 배정한다.

3. P를 열린 목록에 추가한다. 이 시점에서,열린 목록에는 P밖에 없다.

4. 열린 목록의 노드들 중 최선의 노드(최선의 노드란 f 값이 가장 작은 노드이다)를 B로 둔다.

  a. B가 모표 노드이면 경로를 찾은 것이므로 알고리즘을 끝낸다.

  b. 열린 목들이 비었다면 경로를 찾을 수 없는 것이므로 역시 알고리즘을 끝낸다.

5. B에 연결된 유효한 노드를 C로 둔다.

  a. C에 f, g, h 값들을 배정한다.

  b. C가 열린 목록이나 닫힌 목록에 들어 있는지 점검한다.

     i. 만일 들어 있다면, 새 경로가 더 효율적인지(즉 f 값이 더 작은지) 점검한다.

       1. 만일 그렇다면 경로를 갱신한다.

     ii. 들어있지 않다면 C를 열린 목록에 추가한다.

  c. 단계 5를 B에 연결된 모든 유효한 자식 노드들에 대해 반복한다.

6. 4부터 다시 반복한다.




http://blog.naver.com/yoonkh2000/50011068967

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

길찾기(A*) 알고리즘 테스트  (0) 2006.12.26
A* 알고리즘 요약  (0) 2006.12.26
A*(A Star)는 최적인가?  (0) 2006.12.26
최단 경로 다익스트라 알고리즘  (0) 2006.12.26
최단경로 구하기  (0) 2006.12.26
댓글
안내
궁금한 점을 댓글로 남겨주시면 답변해 드립니다.