A* 알고리즘

내용은 책 <GAME PROGRAMMING Gems > 1권, 5권, 7권에서 발췌.

A* 알고리즘의 역사는 너비 우선 탐색에서 시작한다.

너비 우선 탐색은 트리에서 한 노드의 모든 자식 노드를 점검한 후에 트리의 다음 수준으로 내력가는 방식이다.

현재 수준의 자식 노드들에서 목표를 발견하지 못하면 자식 노드들을 한 수준 더 전개해서 검색을 진행한다.

구현 환경은 Microsoft Visual Studio 2008

A*의 이론에 대해서는 다른 블로그에 자세히 설명되었으므로 여기서는 구현의 목적에 초점을 두도륵 한다.

 

필요한 자료구조

힙(최소힙), 연결 리스트이며, 기존의 힙은 최대 힙으로 구현을 하였는데,

최소 힙을 만드려면 부등호의 방향만 변경하면 된다.

designatedroom87.tistory.com/27?category=871993

최대 힙 - Basic

 

필요한 내용

정렬하는 부분이 필요하다. 이 중에서 퀵 정렬을 이용할 것이다.

정렬할 기준은 거리이다.

designatedroom87.tistory.com/21?category=870685

Quick Sort

 

디자인 패턴

싱글턴 패턴

 

설명에 앞서서

아래는 너비 우선 탐색 기반의 일반적인 길찾기이다. 

아래는 일반적인 길찾는 함수이다.. 자료구조 중에서 큐를 활용한다.

밑에 있는 영상을 보다시피 단순히 길만 찾을 뿐이지, 최단 경로는 찾지 못한다.

 

너비 우선 탐색의 길찾는 방식 

소스 파일

소스 파일.zip

0.01MB

 

 

설명

A* 알고리즘은 상태 공간 안의 특정 상태에 이웃한, 즉, 인접한 상태들을 조사해 나가면서

시작 상태로부터 목표 상태로 이르는 가장 싼 비용의 경로를 찾는 알고리즘이다.

 

본질적으로 A* 알고리즘은 아직 조사하지 않은 상태들 중 가장 유망한 상태를 조사하는 과정을

반복하는 것이다.

 

만일, 그 상태가 목표이면 알고리즘은 끝나고, 그렇지 않으면, 그 상태의 인접한 상태를 조사해 나간다.

 

A*는 두 종류의 상태 목록들을 관리한다.

하나는 아직 조사하지 않은 상태들을 담은 '열린' 목록( Open list )이고,

또 하나는 이미 조사한 상태들을 담은 '닫힌' 목록 ( Closed list )이다.

 

알고리즘의 시작에서 닫힌 목록은 비어 있으며, 열린 목록은 오직 시작 상태(처음 위치)만을 가지고 있다.

 

각 각의 반복에서 알고리즘은 '열린' 목록의 상태들 중 가장 유망한 것을 가져온다.(목록에서는 제거된다.)

그 상태가 목표가 아니면, 이웃한 위치들을 정렬한다.

이웃 위치들이 새로운 것이면 열린 목록에 넣고,

이미 열린 목록에 있는 것이면, 그리고 그것들에 의한 경로가 이전 것들보다 비용이 싸면 그 위치들에 대한 정보를 갱신한다.

 

반대로, 만일 그 위치들이 이미 닫힌 목록에 있는 것이면 이미 조사를 마친 것이므로 그냥 무시한다.

목표에 도달하기 전에 열린 목록이 비어 있게 되면, 시작 위치로부터 목표에 도달하는 경로가 존재하지 않는 것이다.

 

열린 목록 안의 "가장 유망한" 상태란 그 위치를 지나서 목표에 도달하는 경로의 비용이

가장 싼 (또는 가장 싼 가능성이 큰) 위치를 말한다.

 

각 각의 현재 노드 X는 그러한 "유망함"을 평가하기 위한 정보를 가지고 있다.

CostFromStart(X) : 시작 노드로부터 이 노드에 이르는 가장 싼 비용. 보통 G라 표현하고 유클리드 거리로 측정

CostToGoal(X) : 현재 노드X에서 목표 노드에 이르는 가장 싼 추정 비용. 보통 H라 표현하고 맨하탄 거리로 측정

TotalCost(X) : 노드 X의 총 경로 비용으로 CostFromStart(X) + CostToGoal(X) 이다.

 

A* 알고리즘은 현재 상태에 인접한 상태들 중 TotalCost(X)가 가장 낮은 상태를 찾아서

그 상태로 이동하는 과정을 반복함으로써 가장 싼 비용의 최종 경로를 찾는다.

 

그리고 각 상태는 자신의 "부모" 상태, 즉, 가장 싼 비용으로 자기 자신에 이르도록 한 상태를 가리키는 포인터도 가진다.

 

알고리즘이 목표에 다다르면, 그 포인터들을 이용해서 목표에 다다르기까지의 상태들을 거꾸로 밟아나가는데,

그렇게 해서 만들어진 것이 바로 시작 위치로부터 목표에 이르는 가장 싼 경로이다.

 

휴리스틱 비용의 조정

A* 알고리즘의 휴리스틱 비용은 목표까지의 실제 비용(물론 검색을 마치기 전까지는 알 수 없다.)을 미리 추정한 값이다.

휴리스틱 비용이 실제 비용보다 크면 "일단 목표 쪽으로 돌진하면서 길을 찾는" 방식으로 검색이 수행되며,

휴리스틱 비용이 실제 비용보다 작으면, "돌아가는 길이 더 빠를 수도 있으니 최대한 많은 가능성들을 시험해 보는" 방식으로 검색이 수행된다.

따라서 최적의 경로를 찾으려면, 항상 휴리스틱 비용을 실제보다 과소평가할 수 있어야 한다.

휴리스틱 비용을 항상 과소평가하기 위한 한 가지 방법은 현재 노드와 목표까지의 지리적 거리를 이용해서 휴리스틱 비용을 계산하는 것이다.

휴리스틱 비용은 '열린' 목록 중 어떤 노드를 우선 선택할 것인가의 판단에 영향을 미친다.

A*는 항상 총 비용( 현재 노드까지의 비용 + 휴리스틱 비용 )이 가장 작은 노드를 선택하기 때문이다.

 

노드가 가지고 있어야할 정보들

A*가 탐색하는 각 노드에 대해 다음과 같은 정보가 보존되어야 한다.

(1). 부모 노드를 가리키는 포인터

(2). 이 노드까지의 비용

(3). 총 비용( 이 노드까지의 비용 + 휴리스틱 비용 )

(4). 이 노드가 열린 목록에 들어 있는지의 여부

(5). 이 노드가 닫힌 목록에 들어 있는지의 여부

아래의 클래스는 노드(방)에 대한 것이다.

 

위의 Room 클래스를 그림으로 표현하면 아래와 같다.

좌측의 그림은 Room클래스의 m_Roomway[EIGHT] 포인터 배열이 필요한 이유이며, 우측의 그림은 m_Roomway[EIGHT] 포인터 배열로 각 Room들이 서로 연결된 그림이다. 그 예로  A노드를 중심으로 m_Roomway[EIGHT]포인터 배열은 A노드의 왼쪽 위는 장애물이므로 왼쪽 위 포인터는 NULL로 설정한다.

 

그리고 아래의 그림을 보자. Room클래스의 멤버변수 m_pParent 포인터 변수가 필요한 이유이다.

시작 노드에서 목적지 노드까지 최돤 경로가 존재한다고 가정하자.

최단 경로가 아래 왼쪽 그림과 같다고 하면, 각 노드들의 m_pParent 는 아래의 오른쪽 그림과 같이 연결된다.

m_pParent는 빨간색 선이다.

즉, 목적지 노드의 m_pParent 는 C노드이고, C노드의 m_pParent 는 A노드이고, A노드의 m_pParent 는 시작노드 이다.

이 포인터 변수가 있는 이유는 최단 경로가 존재할 때, 이 포인터 변수를 통해 최단 경로로 연결된 노드들을 찾아 낼 수 있기 때문이다.

결국 m_pParent 는 목적지점에서 시작점으로 거슬러 올라갈 때 필요한 변수이다.

Room클래스의 m_pParent포인터 변수가 필요한 이유

 

 

열린 목록 & 닫힌 목록

"가장 유망한" 다음 노드를 선택하기 위해, A*는 다음에 검색할 수 있는 모든 노드들을 '열린(Open)' 목록 안에 담아두고 그것들을 유망한 순서로 정렬한다.

열린 목록에 들어갈 노드는 지나갈 수 있는 노드만 저장.

A* 루프의 매 단계마다 가장 유망한 노드를 고르는 작업이 일어나는데,

여기서 '가장 유망한' 노드라는 것은 총 비용( 노드에 이르기까지의 비용 + 목표까지의 추정 비용 )이 가장 낮은 노드를 말한다.

이런 문제를 해결할 수 있는 가장 좋은 방법은 열린 목록에 어떤 노드를 추가하거나 제거할 때, 자동적으로 정렬 상태를 유지할 수 있도록 만드는 것인데 그러한 방식으로 작동하는 자료구조로는 우선 순위 큐가 있다.

우선 순위 큐를 열린 목록으로 사용하는 경우 A*는 다음과 같은 네 종류의 작업들을 수행하게 된다.

(1). 열린 목록에서 총 비용이 최소인 노드를 추출한다. (그리고 목록을 다시 정렬한다. )

(2). 열린 목록에 새 노드를 삽입한다. ( 그리고 목록을 다시 정렬한다. )

(3). 열린 목록 안에 있는 노드들의 총 비용을 갱신한다. ( 그리고 목록을 다시 정렬한다. )

(4). 열린 목록이 비어 있는지 판단한다.

닫힌 목륵은 다시 볼 필요가 없는 목록이다. 닫힌 목록은 연결 리스트로 구현한다.

 

 

열린 목록 & 닫힌 목록 역할

열린 목록과 닫힌 목록의 조합은 이전에 평가한 노드들의 목록 역할을 하는데,

이를 이용해서 이미 방문한 노드를 다시 전개하는 일을 방지할 수 있다.

 

 

A* 알고리즘 의사 코드

아래의 수도코드 함수의 세 번째 매개변수 Agent는 유닛의 종류를 의미한다. 여기서는 필요 없다.

간략화를 위해서, CostFromStart를 G라고 썼다.

​CostToGoal은 H로, TotalCost는 F라 썼다.

우선 A*는 시작으로부터 목표에 이르는 하나의 경로를 찾는다. ( 존재하는 경우에는 )

두 번째로, A*는 최적의 경로를 찾는다. 단, 이는 CostToGoal(X)이 '적절한' 평가치를 돌려주는 경우의 이야기이다.

여기서 적절한 평가치를 돌려준다는 말은  CostToGoal(X)이 항상 과소평가 된다는 것, 다시 말하면  

CostToGoal(X)의 반환값이 항상 실제로 가장 싼 경로(X에서 목표까지의 경로)의 비용보다 작거나 같은 값을 돌려준다는 뜻이다.

세번째로, A*는 휴리스틱을 가장 효율적으로 사용한다. 휴리스틱 함수  CostToGoal(X)이 동일하다고 할 때, A*보다 더 적은 수의 상태들을 탐색해서 최적의 경로를 찾아낼 수 있는

검색 알고리즘은 없다.(동일한 비용을 가진 상태들 사이의 동점 처리는 고려하지 않는다.)

 

Node가 목적지 노드라면 true를 리턴하고,

만약 while 루프를 빠져나오면 false를 리턴하는데, 그 이유는

목표에 도달하기 전에 열린 목록이 비어 있게 되면, 시작 위치로부터 목표에 도달하는 경로가 존재하지 않기 때문이다.

아래는 위의 알고리즘을 바탕으로 구현한 함수이다.

A* 알고리즘 의사 코드를 기반으로 구현함 길찾기 함수

위의 멤버함수 AstarSearch에서 맨 마지막 부분을 보면, 아래와 같다.

목적지에 도달할 수 없는 경우에 대한 예외처리인데 여기서 하고자하는 것은 목적지까지 갈 수 없는 경우라면

목적지에 최대한 가까운 노드를 찾아 시작점부터 이 노드까지를 연결시키기 위함이다. 

이 닫힌 목록(연결리스트)의 첫 번째에 들어있는 노드가 목적지와 가장 가까운 노드가 들어있다.

이 노드의 부모 노드를 이용해서 시작점부터 이 노드까지의 경로를 알아낼 수 있다.

아래의 내용은 꼭 있어야 하는 것은 아니지만, 일종의 예외처리이다.

 

 

이웃한 상태들

일정한 크기의 타일로 이루어진 격자라면 인접한 타일이 바로 이웃한 상태이다.

격자인 경우에 (row , col)의 이웃은 (row + 1 , col) , (row + 1 , col  + 1) , (row , col + 1) 등 등이 된다.  

아래는 각 노드들을 서로서로 인접한 노드들과 연결시키는 함수이다.

 

위의 함수에 대한 이해를  돕고자 위의 그림을 다시 가지고 와보자. 

위에서는 인접한 노드가 장애물일 경우에 NULL로 설정한다고 했으나,

여기서는 상관없이 인접한 노드들과 연결을 진행한다. 이와같이 하는 이유는 

TiliManager라는 클래스가 별도로 존재하기 때문에 그렇다.

TiliManager 클래스가 이미 방에 대한 모든 정보들을 가지고 있어서 나중에 탐색을 했을 시에,

인접 위치의 노드가 장애물인지 갈 수 있는 길인지, 목적지 노드인지 파악 가능하다.

TiliManager 클래스가 있는 이유는 밑에서 설명하도록 한다.

 

 

 

구현의 방법

우리는 아래의 파일 내용을 읽어와서 길찾기를 진행할 것이다.

BOX는 장애물, EMP는 자니갈 수 있는 길, USR은 시작점, END는 목적지점을 의미한다.

이 파일에 있는 내용을 읽어와서 저장하는 역할을 TileManager 클래스가 할 것이다.

 

아래의 클래스가 TileManager 클래스이다.

이 TileManager는 싱글톤 클래스로 구현을 했다.

기본적으로 하는 역할은 파일에 있는 내용을 읽어와서 멤버변수m_pMap이라는 이차원 배열에 저장한다.

그리고 시작점과 목적지점에 대한 정보 또한 갖고 있다.

그리고 위치(행과 열)정보를 받으면 해당 노드(방)가 장애물인지 갈수 있는 길인지 등에 대한 정보를

리턴하는 멤버함수도 정의한다.

 

그리고 나서, main함수에서 Astar 클래스의 멤버함수 AstarSearch 호출해서 최단 경로를 찾는다.

최단 경로에 대한 정보는 함수의 리턴값인 stack에 저장되어 있다.

스택의 맨 위에는 시작점에 대한 정보가 있으므로 순서대로 꺼내서 출력을 하면 된다.

 

아래의 두 함수가 최단 경로의 노드들을 출력을 도와줄 것이다.

 

소스 파일

소스 파일.zip

0.01MB

 

영상

 

 

 

그리고 아래의 내용은 하나의 외전으로 보도록 하자.

위에서 우리는 콘솔 창을 띄워서 만들었는데, 너무 없어 보인다.

이를 API를 활용해서 좀 더 시각화 할 수 있다.

아래는 최단 경로를 찾는 프로그램의 초기화면이다.

아래의 그림은 Start와 Destination와 WALL, EMPTY버튼을 활용해서 UI화면에 오브젝트들을 나타낸 그림이다.

장애물을 피해 최단 경로를 찾기 위해서 FindPath버튼을 선택합니다.

아래의 그림이 최단 경로를 나타낸 그림입니다.

다시 처음부터 하시려면 Clear버튼을 선택하면 된다.

아래는 프로그램의 실행영상이다.

 

 

 

소스 파일

Astar.zip

0.01MB