[Algorithm] A star(A*)

Posting : 2010.10.14
                          by 퓨림노

퍼가실 때는 URL 을 남겨주세요^-^*

(논문을 찾다가....아니 수학공식을 찾다가...
신기한(?) 그림이 있어서 냉큼~ 다운 받았죠. 근데 주소를 모르겠네요 ^^;;)

또 포스팅 시간이 돌아 왔습니다....


무엇인가를 잊어버린채...혼자서 이리저리 삽질하구나서 몇일동안 포스팅으로 열심히 달리고 있는...

요즘 나의 포스팅은...
다른사람이 정리 잘해둔 포스트를 URL 을 참조하는 방법!!!
그래서 난 내가 한부분판 Posting 하기로 한다.!

먼저. Wikipedia 에 정의 되어 있는 A star Algorithm 을 살펴보자.
( URL : http://en.wikipedia.org/wiki/A-star_search_algorithm )

아래를 클릭!!

In computer science, A* (pronounced "A star") is a computer algorithm that is widely used in pathfinding and graph traversal, the process of plotting an efficiently traversable path between points, called nodes. Noted for its performance and accuracy, it enjoys widespread use. Peter Hart, Nils Nilsson, and Bertram Raphael first described the algorithm in 1968^[1]. It is an extension of Edsger Dijkstra's 1959 algorithm. A* achieves better performance (with respect to time) by using heuristics.

그리고 내용을 읽다가보면...
f = g + h 라는 공식이 나온다.

F : Fitness, 적합도
G : Goal cost, 시작(S)노드로 부터 현재 노드까지의 cost 를 말함( 최종 Node(N)까지 의 cost가 아님)
H : Hueristic, (현재노드G로부터 최종노드(N)까지의 일직선 거리)


참 Wikipedia 에서 Example 로 맘에 드는 gif 그림이 있었습니다.
꼭 제블로그에 !! 올리고 싶어서!! 올립니다.

-

- 이해하시나요? 일단 숙제로 한 내용을 정리하도록 하겠습니다.
- 슬슬 따라와 주시기 바랍니다.

Part 0. Init

√ 시작점(S), 종료점(N) 으로 지정.
√ 각각의 점을 좌표로 계산 하여 Heuristic cost 계산

Part 1. Step

√ G+H = F, 를 계산하였습니다.
   - G는 S 와 각 노드간의 Goal cost를 계산하였습니다.
   - H는 각 노드에서 최종 목적노드인 N 노드까지의 거리를 측정하였습니다.
√ F(Fitness)가 가장 낮은 D Node 가 선택 되었습니다.

Part 2. Step

√ F가 가장 낮은 D노드로부터 연결되어있는 A,G 노드와의 Goal cost 를 계산하였습니다.
   - G = S-D 사이의 거리 + D와 각노드 사이의 거리
√ (S->D->G) 와 (S->D->A)의 Fitness 보다 (S->G)로의 Fitness 가 낮아 경로를 새롭게 이동합니다.

Part 3. Step

√ G = (S-G) + (G에서 각 노드까지의 Goal cost)
√ H = E,F,J,K 에서의 N(Goal node)까지의 Heuristic cost
√ K까지의 Fitness가 가장 낮으므로 노드를 생성합니다.( S->G->K)

Part 4. Step

√ G = (S-G) + (G+K) + (K에서 각 노드까지의 Goal cost)
√ H = F,H,J,L,M,N 에서의 N(Goal node)까지의 Heuristic cost
√ 최종노드인 N node까지의 거리가 가장 낮게 나와 현재까지의 경로를 선택합니다.

※ 최종노드 : S->G->K->N

A star 을 공부하면서 참조한 URL 을 정리해 봅시다.
1. 한글로 A*를 정리가 잘되어 있던 곳입니다. 많은 그림과 설명이 되어있어서 정말...꼭 보시길 강추!!
   - http://gameai.net/Article/Astar/Astar.htm 
2. 1번의 URL 과 마찬가지로 내용을 이해하는데는 한번 들어가서 보시길 바랍니다.
   - http://blog.daum.net/jty71/15645104
   - http://blog.naver.com/hioru/120042220470