[Study] A star Algorithm(A 스타 알고리즘, A* 알고리즘)

주어진 출발지 -> 최종 목적지 길까지 가는 최단 경로를 찾아내는 그래프/트리 탐색 알고리즘 중 하나.

이 알고리즘은 갈 길 x에 대해 그 길을 통과하는 최상의 경로를 추정하는 순위값인 “휴리스틱 추정값” h(x)을 매기는 방법을 쓴다.

알고리즘은 이 휴리스틱 추정값의 순서로 길 방문.

장애물을 피하고 막다른 골목을 빠지지 않고 길을 찾는데 쓰이게 된다.

깊이 우선 탐색 + 넓이 우선 탐색. 처음엔 계속 가능성이 높은 것 하나를 선택해서 깊게 나간다. 그러다 막히면 나머지 가능성 중에서 하나를 선택해서 넓게 나간다. 그 가능성 높은 방향을 선택하는 방법이 바로 A 스타 알고리즘이다.

 

A * 알고리즘은 길찾기를 위한 최적의 알고리즘이다.

지금부터 그 알고리즘에 대해서 자세하게 정리를 하겠다.

원래는 다른 사이트에 있던 것을 내가 다시 요약을 하고 살을 덛붙여서 다시 적어보도록 했다.

참고 사이트는 최하단에 있다.

---

탐색시 열린 목록에 데이터를 집어 넣고, 휴리스틱에 의해 열린 목록중 다음 경로를 선택한 후 닫힌 목록에 집어 넣음.

 

 

지점A(시작점)으로부터 모든 방향 8방향에 대해 열린목록(open list)에 추가한다.

열린목록은 쇼핑목록과 비슷한데, 지금은 목록상에 아이템이 하나지만 나중에 좀더 갖게 될 것이다.

 

2. 시작점 근처에 붙어있고 지나갈 수 있는 모든 사각형들을 본다. (벽, 물 또는 다른 잘못된 지역들은 무시합니다.) 그리고 그 지나갈 수 있는 사각형들을 열린목록에 추가한다. 추가된 각각의 사각형들에게 지점A를 부모사각형이라고 저장한다 (이 ‘부모사각형’은 우리가 길을 거슬러 올라갈 때 중요하다. 나중에 이것에 대해 확실하게 알게 될 것이다.)

3. 시작점A(녹색사각형)를 열린목록에서 빼고, 다시는 볼 필요가 없는 사각형들의 목록인 닫힌목록(closed list)에 추가한다.

(현재 열린 목록에는 8방향 저장, 닫힌 목록에는 시작점A가 저장되 있는 상태.)

State 

열린목록 : 아직 조사하지 않은 데이터

단힌목록 : 조사한 데이터

 

밑에 그림에서 중심에 있는 짙은 녹색 사각형은 출발사각형(시작점A)이다. 이것은 하늘색 외곽선으로 되어있고, 닫힌목록에 추가되었음을 의미한다.. 그리고 인접한 모든 사각형들은 검색된 후 열린목록에 들어간다.

(열린목록은 녹색 외곽선으로 되어있고 부모사각형인 시작점을 가리키고 있는 회색의 포인터를 가지고 있다.)

 

그 후로는 F비용을 이용하여 이와 같은 행동을 반복하게 되는데 F비용에 관해서는 바로 밑에 나온다.

 

다음 방정식으로 사각형을 선택하게 된다.

F = G + H

 

F = 비용

G = 시작점 A(녹색지점)로부터 새로운 사각형까지의 이동비용.

길을 찾아갈수록 G의 값은 커진다. (A로부터 멀어지므로)

H = 얻어진 사각형으로부터 최종목적지점 B(빨간지점)까지의 예상이동비용.

(이 값은 모든 장애물에 대해서는 고려하지 않고 현재 사각형에서 목적지점까지의 거기를 계산하는데 이때 대각선이동이 아닌 가로세로이동에 대한 비용으로 계산하는 것이 중요하다. 장애물을 고려하지 않았으므로 이 비용이 최종이동비용과 같지 않을 확률이 클 것이다.)

우리가 찾고자 하는 길은 열린목록과 F비용이 작은 사각형을 선택하는것의 반복을 통해서 얻어지게 되는 것이다.

위에 설명된 것처럼, G는 출발점으로부터 하나씩 얻게 되는 사각형으로 이동하는데 드는 이동비용이다. 이 예제에서 우리는 세로 또는 가로로 이동하는데 각각 10의 비용, 대각선이동에 대해서는 14의 비용을 할당 할 것이다.

(정사각형이고 가로세로가 10이면 대각선의 길이는 이등변삼각형 길이비 루트2:1:1에 의해 루트2 *10 : 10 : 10이 되므로(루트2는 약1.414) 약 14의 값이 나온다.)

컴퓨터에서 숫자를 사용하는 것은 그만큼 빠르기 때문인데 단순화 시킨 숫자를 사용하지 않으면 길찾기가 매우 느려진다는 것을 알게 될 것이다.

 

위에 설명된 것처럼, G는 출발점으로부터 하나씩 얻게 되는 사각형으로 이동하는데 드는 이동비용이죠. 이 예제에서 우리는 세로 또는 가로로 이동하는데 각각 10의 비용, 대각선이동에 대해서는 14의 비용을 할당 할 것이다.

(정사각형이고 가로세로가 10이면 대각선의 길이는 이등변삼각형 길이비 루트2:1:1에 의해 루트2 *10 : 10 : 10이 되므로(루트2는 약1.414) 약 14의 값이 나오게 된다.)

컴퓨터에서 숫자를 사용하는 것은 그만큼 빠르기 때문인데 단순화 시킨 숫자를 사용하지 않으면 길찾기가 매우 느려진다는 것을 알게 될 것이다.

 

 

 

현 사각형의 G비용 = 그 부모로부터 G 비용 + 직각이면 10 or 대각선으로 움직였으면 14

현 사각형의 H비용 = 목표사각형까지 도달 가로세로 거리(단, 어떤 방해물도 무시)(맨하탄방식(Manhattan method))

 

 

어떤 방해물도 무시하는 방식은 발견적방식이라고도 불리는데, 좀더 알기를 원하는 사람은 여기에서 참고할 수 있을 것이다.

G와 H를 더하므로써 F 가 계산된다. 우리가 진행한 검색의 첫단계 결과를 아래 그림에서 볼 수 있다.

F,G,H 비용이 각각의 사각형에 표시되어 있는데, 시작점 우측에 있는 사각형안에 표시된것처럼, F는 좌상단에, G는 좌하단에, 그리고 H는 우하단에 표시된다.

 

녹색사각의 우측 사각형을 보면, F = G+H (40 = 10+30) 이죠. 이사각형은 부모사각형이 시작점이 된다. (그렇죠? 바로 아랫단계로 물려받았으니까요. 한번씩 사각형들이 퍼질때마다 자식들이 탄생한다고 보시면 되겠다.)

G는 시작점과 새로운 사각형의 거리라고 했으니 10이다. (한변은 10)

H는 장애물을 무시하고 가로세로 이동으로 목적지(빨간사각형)까지의 이동비용이므로 가로 3번*10이므로 30이다. (G값이 14인 사각형들은 대각선 이동을 했기 때문)

 

찾기 계속하기(Continuing the Search)

계속해서 검색을 해 나가기위해 우리는 단순히 열린목록에 있는 사각형들 중에서 가장 작은 F비용을 가지고 있는 사각형을 선택 -> 그 선택된 사각형으로 다음의 과정을 진행하면 된다.

4. 선택된 사각형을 열린목록에서 빼고 닫힌목록에 추가합니다.(부모가 되어 자식노드 생성가능)

(현재 닫힌목록 – 시작점(A) 와 선택된 사각형)

5. 인접한 모든 사각형을 검색해서 닫힌목록에 있거나 갈수없는것(벽,물,그밖에 장애물)들을 제외한 나머지 중에서 열린목록에 없는 사각형을 열린목록에 추가한다.

선택되었던 사각형을 열린목록에 추가된 새로운 사각형들의 부모로 만든다.

(선택되었던 사각형 = 4번에서 단힌목록에 추가된 그 사각형

새로운 사각형 = 5번에서 열린목록에 새롭게 추가된 사각형)

6. 만약 인접한 사각형중에 이미 열린목록에 있는 사각형이 있다면 그 사각형으로 가는길이 더 좋은 길인지 확인하자. 다시 말하면, 현재 선택된 사각형보다 G비용이 더 작은지를 검사하라는 것입니다. 만약 아니라면 아무것도 할 필요가 없지만 G비용이 더 작다면 선택되었던 사각형의 인접사각형들의 부모를 새로운 사각형으로 바꾸자.

(위쪽 그림에서 보면, 선택된 사각형으로 향하는 포인터들의 방향을 바꾸는 것을 말합니다.)

마지막으로, 그 사각형의 F와 G를 다시 계산한다.

 

직접 해보자.

 

최초 – 시작(A지점) 닫힌 목록에 넣음. 열린목록= 8개의 주변 사각형

F비용이 가장 작은 오른쪽 사각형 선택, 하늘색 외곽선으로 표시

 

이 사각형 : 열린 목록 -> 닫힌 목록에 넣음.

인접한 사각형들 검색 ( but, 오른쪽이 벽과 왼쪽에 시작점이므로 무시)

 

장애물 3개와 시작점 제외하니 4개의 사각형 남았으나 이미 열린목록 임을 확인함.

다른 좋은 것이 있는지 G비용 검색. 

녹색사각형의 우상단 사각형은 사실 G 비용은 14이나, 현재 선택된 사각형( 녹색점의 우측사각형)을 거쳐서 그곳으로 이동한다고 하면 G비용은 20일 것이다(현재사각형이 G비용이 10이고 이것에서 수직으로 위쪽으로 한번 이동하였으므로 10을 더함.). G비용 20은 14보다 크므로 좋은 길이 아니게된다.

한번에 대각선이동이 비용 적게 듬.

 

더 이상 최소 비용의 길이 없으므로 인접한 사각형 주목

 

현재 열린 목록의 사각형 7개중 가장 작은 F비용 가지고 있는 것 하나를 고른다.

두 개의 사각형이 54 그러므로 속도상의 목적으로는 둘중 열린목록에 더 늦게 추가된 것을 선택하는 것이 빠름.

(각각 다른 두개의 A* 버전을 만들더라도 길이가 같은 각각 두개의 길을 찾게 될 것이기 때문에 F점수가 둘 다 같더라도 서로 다르게 처리해도 상관 없게 된다.)

그래서, 우리는 그냥 아래쪽에 있는 것을 선택한다.

 

 

다시 인접한 사각형을 검색....

그러면 벽은 무시하고 닫힌 목록에 있는 두 사각형을 무시하면 2개의 열린 목록을 추가( 벽이있어서 대각선 오른쪽 아래로는 못감)

현재 사각형(시작점A의 오른쪽아래) 가 부모가 됨

빨간 사각형(목표)를 열린 목록에 추가 할때까지 이와 같은 계속 반복

시작점 밑 2번째 사각형의 부모사각형이 이전 그림과 변경되었다는 것을 주목해야 한다.

전) G비용 – 28 오른쪽위 사각형 가리킴

현재) G비용 – 20 위쪽 사각형 가리킴

이 일은 우리가 길찾기를 처리해 나가면서 어디선가에서 일어난 것이다. 어딘가에서 G비용을 검사했고 여기서 더 비용이 적게드는 길을 찾아냈다. 그러므로써 부모가 바뀌것이고 G, F비용이 다시 계산되어진 것이다.

이런 식으로 목표지점으로 가는 가장 좋은 길을 찾아 검색을 하면서 바뀔 수 있는 사각형의 비용을 바꿔가면서 길을 찾을 것이다.

최종적인 진짜 길은 빨간지점(목표지점)에서 부모사각형을 찾아가며 거꾸로 되짚어가면서 녹색지점(시작지점)까지 가면 된다. (부모노드를 따라서)

이것은 다음의 그림에서 볼수있다.

 

단점 

맵의 크기가 커지면 ‘열린’ 목록이나 ‘닫힌’ 목록에 수백에서 수천 개의 노드들이 들어갈 수 있기 때문에 시스템의 메모리를 전부 잡아먹을 수도 있으며, 상당히 많은 CPU 시간을 잡아먹을 수도 있다. 또한 시작 위치에서 목표까지의 경로가 존재하지 않으면(막혀있다면) A*는 시작위치에서 도달 할 수 있는 모든 위치를 검색하므로 매우 비효율적이다.

http://cozycoz.egloos.com/9748811

http://blog.daum.net/jty71/15645104