25/04/07 | TIL 알고리즘3 - A*알고리즘과 이진힙구조

A*알고리즘의 이해

- 로봇의 인공지능을 연구하면서 발견함

모바일 로봇의 자율행동을 연구하는 프로젝트에서 출발함

Shakey프로젝트에서의 경로찾기

시작위치로부터 도착 위치까지의 경로를 탐색

공간을 격자( Grid ) 형태로 분석하고 장애물이 놓은 상황을 파악해 회피

 

A* (A New Heuristic Search Method) -경험적지식을 활용해 답을 구하는 Heuristic을 이용함

 

A* 알고리즘은 Dijkstra의 확장형

이전 Dijkstra 알고리즘 - 1959년에 발표.

노드 : 주요한 지점에 대한 정보

---

A* 길 찾기 알고리즘의 이해와 구현

- Dijkstra 알고리즘에서 휴리스틱을 활용해 메모리 사용 및 검색 속도를 개선한 알고리즘

- 휴리스틱 : 경험적 지식을 활용해 답을 구하는 방법

- 응용분야 : 컴퓨터 게임 - 자동차 내비게이션 - 자연어 파싱 -등등.. 

 

A-G까지 최단경로는 모든 경로를 계산해야 하기때문에, 

모든 경로의 경우의 수를 계산하고, 가장작은 값을 가진 경로를 찾는 원리

정확하지만 모든 노드의 계산을 수행함

메모리와 계산량이 많아지는 단점

 

- 동작원리

Dijkstra 알고리즘  = g(n) 만 있음!

---

휴리스틱의 설정

- 일반적으로 목적지까지의 최단 거리로 설정

- 휴리스틱을 통해 다양한 상황에 대해 유연하게 대처할 수 있음

- 휴리스틱의 사전적의미  : 시간이나 정보가 불충분하여 합리적인 판단을 할 수 없거나,

  굳이 체계적이고 합리적인 판단을 할 필요가 없는 상황에서 신속하게 사용하는 어림짐작의 기술

---

일반적으로 목적지까지의 최단 거리로 설정

휴리스틱을 통해 다양한 상황에 대해 유연하게 대처할 수 있음.

 

각 노드마다 경로값과 휴리스틱값을 더한 최종 값을 계산함.

거리와 휴리스틱 값의 합산을 통해 가장 낮은 점수를 가진 경로를 선택

 

A*알고리즘 Step 1

B(5.5)와 C(6.5) 중에서 점수가 작은 쪽을 선택

6.5를 넘기지 않은 상태에서 B경로를 계속 탐색

 

C의 최종값 6.5를 저장함.

 

A*알고리즘 Step 2

5의 점수를 가진 D는 6.5보다 작기 때문에 계속 탐색

 

A*알고리즘 Step 3

9의 점수를 가진 F는 6.5보다 크기 때문에 중지

 

A*알고리즘 Step 4

9보다 큰 점수가 나올때 까지 계속 탐색

 

A*알고리즘 Step 5

7의 점수를 가진E는 9보다 작기 때문에 계속 탐색

 

A*알고리즘 최종결과

A-C-E-G로 최단 경로 탐색

Dijkstra 알고리즘과 달리 F-G의 경로를 계산하지 않아도 문제를 해결할 수 있음.

목표 지점까지 경로 값이 최솟값인지 확인함

---

A*알고리즘의 장점

F-G 노드를 계산하지 않아도 되어서 

메모리와 계산량을 줄일 수 있음

실시간 연산이 필요한 게임에서 유용함

---

A*알고리즘의 구현

오픈셋(Open Set)과 클로즈드 셋 (Closed Set)의 두 가지의 컨테이너를 준비한다.

오픈 셋 에는 가중치를 계산할 노드를 관리한다.

클로즈드 셋에는 앞으로 더 이상 계산하지 않는 노드를 취합한다.

 

데이터를 담을 2가지 컨테이너를 만들고,

중복 데이터를 허용하지 않는 오픈 셋과 클로즈드 셋

A*알고리즘의 구현 과정 Step 1

시작 노드를 오픈 셋에 추가한다.

 

A*알고리즘의 구현 과정 Step 2

오픈 셋에서 가장 낮은 값을 가지는 노드를 가져온다.

동일한 값을 가지는 경우 어떻게 우선 순위를 부여할 지 규칙을 정한다.(예)순서, h(n)의 값)

오픈 셋의 노드 중 가장 낮은 값을 가진 노드 호출

* 우선순위 규칙 - h(n)값이 작은 노드, 먼저 들어온 노드

                              - 아래쪽 노드

 

A*알고리즘의 구현 과정 Step 3

가져온 노드가 종착 노드면 탐색을 종료하고 경로를 수집한다.

아닌 경우에는 선택한 노드를 클로즈드 셋으로 이동시킨다.

 

A*알고리즘의 구현 과정 Step 4

노드에 인접한 이웃 노드를 가져오되 중복이 없도록 점검하고 막힌 곳은 제외한다.

노드를 오픈 셋에 넣을때 g(n)과 h(n)값을 계산해 저장 한다.

각 노드에 부모 노드의 정보를 넣는다.

 

새로 추가한 노드의 부모 노드를 시작 노드로 지정

시작 노드를 부모로 가지는 8개의 노드를 오픈 셋에 추가

오픈 셋에서 가장 낮은 값을 가지는 노드를 1번 노드로 지정

 

A*알고리즘의 구현 과정 Step 5

Step2 과정과 동일 하게 오픈 셋에서 가장 낮은 값을 가지는 노드를 가져온다.

1번 노드와 종착 노드가 동일하지 않으면 클로즈드 셋으로 이동

 

A*알고리즘의 구현 과정 Step 6

선택한 노드는 종착노드가 아니므로 클로즈드 셋으로 이동시킨다.

A*알고리즘의 구현 과정 Step 7

선택한 노드의 인접한 노드를 가져오는데, 클로즈드 셋에 있거나 막힌 노드는 제외한다.

인접 노드가 이미 오픈 셋에 들어있다면 값이 작은 쪽으로 교체한다.

 

A*알고리즘의 구현 과정 Step 8

남은 오픈 셋에서 우선 순위가 가장 높은 노드를 가져온다.

아랫쪽이 우선순위가 있기에 아랫쪽 부터 먼저 계산 해본다

 

A*알고리즘의 구현 과정 Step 9

다시 종착 노드와 비교하고 일치하지 않으므로 클로즈드 셋으로 이동시킨다.

A*알고리즘의 구현 과정 Step 10

해당 노드와 인접한 노드를 구하고 이를 목록에 추가한다.

A*알고리즘의 구현 과정 Step 11

오픈 셋에서 가장 우선순위가 높은 노드를 가져온다.

A*알고리즘의 구현 과정 Step 12

클로즈드 셋으로 이동시키고 인접 노드를 추가한다.

A*알고리즘의 구현 과정 Step 13

오픈 셋에서 가장 우선 순위가 높은 노드를 가져온다

A*알고리즘의 구현 과정 Step 14

클로즈드 셋으로 이동시키고 주위 노드를 오픈 셋에 넣는다

 

A*알고리즘의 구현 과정 Step 15

오픈 셋에서 가장 우선 순위가 높은 노드를 가져온다

A*알고리즘의 구현 과정 Step 16

클로즈드 셋으로 이동시키고 주위 노드를 오픈 셋에 넣는다

A*알고리즘의 구현 과정 Step 17

가장 우선 순위가 높은 노드가 종착 노드와 동일하기 때문에 루프를 종료한다.

A*알고리즘의 구현 과정 Step 18

노드에 담긴 부모 정보를 활용해 최단 경로를 역추적해 리스트를 만든다.

(D -> 5 -> 4 -> 3 -> S)

완성된 리스트를 뒤진으면 최단 길찾기 경로가 완성된다.

---

A*알고리즘의 구현 (Unity) 30' - 구현해보기!

변수 선언

gridX

gridY

gCost

hCost

 

플레이어와 목적지를 설정하고, 플레이어가 이동할 수 없는 장애물을 설정한다.

UnWalkable로 레이어를 설정하고, 이동할 수 없다고 설정함.

A*게임 오브젝트는 Grid Script + Pathfinding Script

Grid Script = 배경을 1M 단위격자로 나누어 주는 역할

                          UnWalkable 레이어 설정

 

 

Pathfinding Script = 오픈셋과 클로즈셋을 활용해 노드를 추가하고, 계산하는 Script

길을 찾았을때, 마지막 노드와 현재의 노드 - 부모를 찾아 올라가는 Reverse()를 활용해 최단거리를 구할 수 있음.

GetDistance() 를 활용해 거리를 계산 함.

---

A*알고리즘의 최적화

1. 최소 값 검색

리스트 자료 구조에서 최소 값 검색은 O(N)의 복잡도를 가짐

가장 작은 값 3을 찾기 위해서는 3개의 노드를 뒤져야함.

 - 모든 노드를 순회하여 최솟값을 찾는 List구조

 

우선순위 큐 (Priority Queue) 컨테이너

우선 순위 큐 컨테이너는 항상 가장 작은 값(또는 가장 큰 값)이 처음에 위치해 있음

따라서 한번에 가장 작은 노드를 찾을 수 있음.

우선 순위 큐에서 최소값 검색의 복잡도는 O(1)을 가짐.

모든 요소가 내림 차순 혹은 오름 차순으로 나열 된 정렬과는 다른 구조를 가짐.

우선순위 큐 (Priority Queue) 의 구현

보통 두개의 가지로만 구성된 트리 구조인 이진힘(Binary Heap) 구조로 구현함.

이진힙의 내부 데이터는 배열로 구성되어 있음.

 

이진힙에서의 규칙

이진힙에서 노드의 위치는 정해져있음.

부모는 항상 두개의 자식만 가질 수 있기에 일정한 규칙 부여가 가능

 

특정 인덱스에서 부모의 인덱스를 찾는 공식(소수점은 버림)

 

우선순위 큐 유니티에서 활용

//PriorityQueueTest.sc
public List<int> priorityQueueData;

void Start()
{
    PriorityQueue<int> pq = new PriorityQueue<int>();
    pq.Enqueue(23);
    pq.Enqueue(10);
    pq.Enqueue(8);
    pq.Enqueue(9);
    pq.Enqueue(3);
    pq.Enqueue(5);
    
    priorityQueueData = pq.data;
}
void Update()
{
	
}

 

 

2. 최소 값 제거

이진힙 구조에서 최소값을 얻은 후 빼내기

뺀 후에도 최소 값이 맨 앞에 있어야 하고 이진힙 구조도 유지해야함

구조를 유지하기 위해 가장 마지막의 데이터를 루트로 설정

뺀 후에도 최소값이 맨 앞에 있어야 하고 이진힙 구조도 유지해야함

루트로부터 내려가기 위해서 두 자식 중 가장 작은 값을 파악하기

오른쪽이 왼쪽보다 작으므로 루트와 오른쪽 노드를 비교

루트 노드와 오른쪽 자식 노드를 비교하고 루트가 더 크면 교체10은 5보다 크므로 교체

루트 노드와 오른쪽 자식 노드를 비교하고 루트가 더 크면 교체10은 5보다 크므로 교체

가장 하단에 도달할 때 까지 해당 작업을 반복 수행

더이상의 자식이 없으므로 삭제 작업을 마무리

 

 

 

3. 중복 노드 확인

4. 새로운 노드의 추가

5. 중복 노드의 교체

---

리스트와 이진힙 구조의 비교

리스트는 분산된 메모리 블럭을 사용하고 이진힙은 메모리가 한 데로 모아진 배열구현가능.

실제 성능 비교는 벤치마크 비교를 통해 검증해야함.

 

게임에서 발생하는 상황을 가정한 후 

벤치마킹을 통해 성능을 검증 해야함

 

* 아직도 알고리즘은 많이 어렵지만 오늘의 A*알고리즘은 어느정도 이해가 된 것 같다.

내일은 활용해서, 코딩테스트 문제를 찾아봐야겠다!