19FEB19 길찾기-A* algorithm

 

격자에서 8가지 움직일 수 있는 방향(노드) 가 있다. 이중 가로세로로 이동에는 travel cost 를 10, 대각선 이동에는 14로 지정한다. 이값은 직각이등변 삼각형의 변의 길이의 비가 1:1:√2 이기 때문에 근삿값으로 지정한 것. 최단경로를 찾기 위해선 이 travel cost를 최소화해야 한다.

 

이 과정에는 10가지 정보를 다룬다.

 

1 Node number : 움직일 수 있는 모든 경로의 격자마다 숫자를 붙인다.

 

2. X and Y Coords : x 와 y 좌표.

 

3. G-Cost : start node 에서 current node 까지의 travel cost 이다.

 

초록점 : start node

파란점 : current node

빨간점 : end node

검은점 : obstruction node(장애물)

 

사진상에서의 G-Cost는 10+10=20 이다.

 

4. H-Cost : current node 에서 end node 까지의 travel cost이다.

 

사진상에서의 H-Cost는 14+14+10+10=48 이다.

 

G-Cost , H-Cost 는 obstruction node를 고려하지 않는다.

 

 

 

 

5. F-Cost : G-Cost + H-Cost

 

20+48=68이다.

 

 

6. Parent Node # : 발견된 노드

 

7. Obstruction Node : 해당 노드가 방해물인지 알게 해주는 노드

 

8. Null Set : 발견되지도, 방문하지도 않은 노드

 

9. Closed Set : 방문한 노드

 

10. Open Set : 발견되었으나, 방문하지 않은 노드

 

 

 

하늘색은 Open Set 이다. 아직 움직이지 않아 Current node 는 Start Node다. Open Set에 적혀진 숫자는 각각 G-Cost, H-Cost, F-Cost 다.

 

 

 

Open Set 중 F-Cost가 가장 적은 노드가 Current Node가 된다. 그러자 새로운 Open Set이 생겼다.

 

 

 

 

한번 더 나아가려는데 이번엔 F-Cost가 같은 노드가 3개가 있다. 그럴땐 H-Cost가 최소인 노드를 선택한다.

 

 

Point)

 

 

A)                                                                                                            B)

                                    

                 

 

 

 

이 알고리즘은 최단경로를 찾는다. 그래서  A의 경우가 더 효율적인 경우이고

 

좌상단의 노드가 우측 하단의 노드의 Parent node가 된다.

 

 

하지만 명확하게도 위와같은 경로가 최단경로다. 동그라미친 노드는 아직 컴퓨터가 발견하지 못했지만 결국에는 발견될 것이다.

 

 

 

F-Cost와 H-Cost 까지 동일한 경우에는 randomize하게 선택해서 end node에 다다를 때까지 진행한다. Parent node를 따라 이어가자 결과가 도출

 

되었다.

 

 

 

흥미로운점은 G-Cost의 비중을 F-Cost에 비해 훨씬 크게 두고 길찾기를 하면 처리속도는 느리지만 최단 경로를 찾아낸다.

 

 

 

반대의 경우, 처리속도는 빠르지만 허점이 보인다.

 

출처 : https://youtu.be/pKnV6ViDpAI