A* (A star) 알고리즘

A* (A star) 알고리즘

- 주어진 출발점에서 목표점까지 가는 최단 경로를 찾아내는 그래프 알고리즘 중 하나이다.

- 적절한 휴리스틱 추정값 h(x)<!--[endif]--> 을 가지고 이 알고리즘을 사용하면 최적의 해를 얻을 수 있다.

- A* 알고리즘은 최적의 경로를 탐색하기 위해, 각각의 지점에서 다음과 같은 함수 f(n)을 이용하여

가중치를 고려한다.

f(n) = g(n) + h(n)

  g(n) : 출발점으로부터 현재 위치까지의 경로 가중치

  h(n) : 현재 위치로부터 목표점까지의 추정 경로 가중치

1. 동작 원리

(1) 현재 위치(시작점)에서 이동할 수 있는 지점을 열린 목록(open list)에 추가한다.

(2) 현재 위치를 다시 확인할 필요가 없는 닫힌 목록(closed list)에 추가합니다.

(3) 열린 목록에서 가장 비용이 적은 위치를 꺼내 현재 위치로 지정합니다.

(4) 목표에 도달하기 전까지 위의 과정을 반복합니다.

 

[ Fig . 1 ] 동작 원리 - 1	[  Fig. 2 ] 동작원리 - 2
회색 칸 - 현재 위치(시작 위치) 검은색 칸 - 닫힌 목록(이동할 수 없는 지점) 빨간색칸 - 목표 지점 회색 테두리 - 현재 위치로부터 가장 비용이 적은 지점 각 칸의 숫자 - G + H로, 좌측은 g(x), 우측은 h(x) 값이다.	Fig. 1부터 살펴보면, 현재 위치로부터 열린 목록들의 비용을 나타내고 있다. f(x) 값을 토대로, 열린 목록 중 가장 비용이 적게 드는 곳을 선택하였다. Fig. 2을 보면, 기존 위치는 닫힌 목록이 되었고, Fig. 1에서 선택된 위치가 현재 위치가 되었다. 마찬가지로 비용이 가장 적은 위치를 탐색하였다.

2. 함수 설명

void astar() : A* 알고리즘의 메인 부분으로, 동작원리 (4)에 해당한다.
void add_openlist() : 동작원리 (1)에 해당하는 부분으로, 목표점이 리스트에 들어오면 종료한다.
int calc_heuristic( ) : 휴리스틱을 이용하여, 각 지점들에 이동하는 비용을 계산해준다.

enqueue() : 이동 가능한 지점을 큐에 배정하는 부분, 삽입과 동시에 정렬이 이루어진다.

                (= 최소값을 수월하게 찾기 위함)

3. 함수 구현

 

#include <stdio.h> #include <malloc.h> #define MAX   10 #define DONTMOVE -1 #define WALL  -2 #define CLOSED  -3 #define UNDEF  -1 #define INF   0 typedef struct vertex{  int c;  int r;  int g; }VERTEX; typedef struct queue{  VERTEX v;  struct queue *next; }QUEUE; void astar( void); void add_openlist( VERTEX); int calc_heuristic( VERTEX, int, int); void enqueue( VERTICAL); VERTEX dequeue( void); int empty_queue( void); void print_character( void); void print_weights( void); QUEUE *Q; VERTEX s, e; int g[MAX][MAX]; int visit[MAX][MAX]; int pre[MAX][MAX]; /* 2 2 6 6 3 4 2 4 3 4 5 */ int main( void) {  int obc, obr;  int obcnt = 0;  int i;  scanf("%d%d", &s.c, &s.r); // input a column and a row of starting point.  scanf("%d%d", &e.c, &e.r); // input a column and a row of ending point.  s.c --; s.r--; // have to minus number 1 because the array begins from zero.  e.c --; e.r--;  scanf("%d", &obcnt); // input the number of walls  // input the coordinates of walls.  for( i = 0 ; i < obcnt ; i ++)  {   scanf("%d%d", &obc, &obr);   visit[obc-1][obr-1] = WALL;  }  // call the a star algorithm.  astar();  print_weights();  printf("\n\n");  print_character();  return 0; } /*  print_character()  with back tracking, display the shortest root. */ void print_character( void) {  int i, j, backtrack;  // to back track, calculate the coordinate.  i  = pre[e.c][e.r] / MAX;  j  = pre[e.c][e.r] % MAX;  // continuously calculate the previous coordinates.  while( pre[i][j] != UNDEF)  {   backtrack = pre[i][j];   g[i][j] = 7;   i  = backtrack / MAX;   j  = backtrack % MAX;  }  // display the root as characters.  for( i = 0 ; i < MAX ; i ++)  {   for( j = 0 ; j < MAX ; j++)   {    if( i == e.c && j == e.r)    {     printf("%5s", "★");    }    else if( i == s.c && j == s.r)    {     printf("%5s", "☆");    }    else if( g[i][j] == 7)    {     printf("%5s", "●");    }    else if( visit[i][j] == -2)    {     printf("%5s", "▤");    }    else    {     printf("%5s", "○");    }   }   printf("\n");  } } /*  print_weights()  display the weights of each vertexs. */ void print_weights( void) {  int i, j;  for( i = 0 ; i < MAX ; i ++)  {   for( j = 0 ; j < MAX ; j ++)   {    printf("%5d", g[i][j]);   }   printf("\n");  } } /*  empty_queue()  this function examine whether the queue is empty. */ int empty_queue( void) {  return Q == NULL; } /*  dequeue()  it give back the point that stored the first time. */ VERTEX dequeue( void) {  QUEUE *f = Q;  VERTEX v = {0,0,0};  if( f != NULL)  {   Q = f->next;   v.c = f->v.c;   v.r = f->v.r;   v.g = f->v.g;   free(f);   return v;  }  return v; } /*  enqueue()  it is used as the list for the open list.  it processes the insertion-sort */ void enqueue( VERTEX v) {  QUEUE *f = Q;  QUEUE *newq = (QUEUE*)malloc(sizeof(QUEUE));  VERTEX temp;  int cnt  = 0;  int key;  newq->next = NULL;  newq->v  = v;  if( f == NULL)  {   Q = newq;   return;  }  // with insertion-sort, begin sorting process.  while( f->next != NULL)  {   key = g[v.c][v.r];   if( key < g[f->v.c][f->v.r])   {    temp = f->v;    f->v = v;    v  = temp;   }   f = f->next;  }  newq->v = v;  f->next = newq; } /*  calc_heuristic()  calculate the weight with the heuristic  according to the heuristic, A star algorithm has different performance. */ int calc_heuristic( VERTEX v, int c, int r, int *gx) {  int result;  // calculate h(x) value.  result = ((abs(e.c - c) + abs(e.r - r)) * 10);  // get g(x) value of previous vertex.  *gx = v.g;  // examine whether this point is located on the diagonal.  // increase the count of moving  if( abs(v.c - c) == abs(v.r - r))  {   *gx = *gx + 14;    }  else  {   *gx = *gx + 10;  }  return result + *gx; } /*  add_openlist()  this function add the adjacency points to the queue. */ void add_openlist( VERTEX v) {  VERTEX temp;  int cnt  = 0;  int i, j, w, gx;  // check the vertexs that are located on the nearest points.  for( i = v.c-1 ;i <= v.c+1 ; i ++)  {   // if the point is off the map   if( i < 0 || i >= MAX) continue;   for( j = v.r-1 ; j <=  v.r+1 ; j ++)   {    // if the point is off the map or same with current point,    // the points that can't move.    if( j < 0 || j >= MAX || (i == v.c && j == v.r) ||     visit[i][j] <= DONTMOVE) continue;    // calculate the weight about the point    w = calc_heuristic( v, i, j, &gx);    // if the weight that have calculated now is lower than    // original weight.    if( w < g[i][j] || g[i][j] == INF)    {     g[i][j]  = w;     pre[i][j] = (v.c * MAX) + v.r;     // if this point is the same with ending point.     if( e.c == i && e.c == j)     {      Q = NULL;      return;     }    }    temp.c = i;    temp.r = j;    temp.g = gx;    // enqueue this point.    enqueue( temp);   }  } } /*  astar()  it is related with Dijkstra algorithm and  can find the shortest root about 8-ways. */ void astar( void) {  VERTEX v;  g[s.c][s.r]  = 0; // init weight on the starting point.  pre[s.c][s.r] = UNDEF; // the starting point don't have previous root.  s.g    = 0; // it means that the number of moving.  v = s; // make the starting point as current point.  // add adjacency vertexs to the open list.  add_openlist( v);  while( !empty_queue())  {   // add current vertex to the closed list.   visit[v.c][v.r] = CLOSED;   // update current vertex   v = dequeue();   // add adjacency vertexs to the open list.   add_openlist( v);  } }

 

4. 실행 결과

 

[ Fig. 3 ] 예제 그림

Fig. 3의 그림을 기준으로, 10 x 10 필드에 파란색이 출발점, 빨간색이 목표점 그리고 검은 색이 벽이다.

[ Fig. 4 ] 각 지점의 가중치 및 문자 표현

Fig. 3의 그림을 기준으로 알고리즘을 수행한 결과이다, 출발점, 목표점 및 벽은 가중치가 0 이고

나머지 지점은 각각 시작점으로부터의 각 최단거리 비용이다. 즉 (10, 2)에 도착하기 위한 최소한의

비용은 226이다. Fig. 4의 아래 그림은 백트래킹을 이용하여 최단거리 경로는 그림으로 표현한 것이다.

[ Fig. 5 ] 최단거리

위의 알고리즘 수행 결과를 토대로, 최단거리(초록색)을 표시하였다.