A* 알고리즘

최단 경로를 찾을 때 가장 많이 사용하는 알고리즘으로 다익스트라 알고리즘을 확장시킨 알고리즘이다. A* 알고리즘은 출발점을 제외한 각각의 점에 대해 도착점까지의 예상 거리 (예를 들어, 지도상의 좌표로 계산된 직선 거리)를 추가하여 고려한다. 즉, A* 알고리즘은 각 지점마다 출발점으로부터의 거리뿐만 아니라 도착점까지의 예상 거리의 합까지 고려하여 다익스트라 알고리즘을 수행한다. 도착점과 반대 방향에 있는 점이 출발점에 가깝다 하더라도, A* 알고리즘은 도착점 방향에 있는 점들의 최단 경로를 우선적으로 계산해 출발점과 도착점간의 최단 경로를 다익스트라 알고리즘보다 빨리 찾는다. A* 알고리즘은 **휴리스틱 함수(heuristic function)**를 이용한다.

탐색과정

![]({{ "/assets/images/algo/astar1.png" | absolute_url }})

녹색 출발지점(A), 빨간색 도착지점(B), 파란색 벽일때, 검색지역(흰색)이 사각형 Grid형태로 나누어져있다. 이 탐색범위를 단순히 2차원 배열로 만들어준다.

갈 수 있는길(흰색), 갈 수 없는길(파란색, 장애물)로 상태가 기록해두어 갈 수 있는 길만 탐색한다.

![]({{ "/assets/images/algo/astar2.png" | absolute_url }})

출발노드(A)에 붙어있고 지나갈 수 있는 모든 길(벽, 범위를 벗어난 곳)을 open list에 추가한다. 추가된 노드들은 출발노드(A)를 부모 노드라 기록한다.(Backtracking)
출발노드를 open list에서 빼고, 방문했다는 것을 표시하기 위해서 closed list에 추가한다.

open list에 저장된 인접노드(화살표)중 어떤 노드를 선택해야할까? 가장 적은 F비용을 가진 것을 선택한다.

A* 알고리즘은 출발 노드로부터 목표 노드까지의 최적 경로를 탐색하기 위한 것이다. 이를 위해서는 각각의 노드에 대한 평가 함수를 정의해야 한다. 이를 위한 평가 함수 f(n)은 다음과 같다.

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

g(n) : 출발 노드로부터 현재 노드 까지의 경로 가중치
- g(n) 은 부모노드(이전노드)로 부터 경로 가중치를 얻어와 더해준다.
h(n) : 현재 노드로부터 목표 노드까지의 추정 경로 가중치( 장애물에 대해서 고려하지 않고 계산한다.)
- h(n) 은 노드의 위치의 변화에 따라서 예측할 수 있다. h(n)이 휴리스틱 함수이며, 여기서는 맨하탄 방식(manhattan method)를 사용할 것이다. : 대각선 이동을 제외한 가로, 세로 이동한 총 숫자 * 10

보통 가로, 세로 10, 대각선은 14의 경로 가중치를 할당한다.

![]({{ "/assets/images/algo/astar3.png" | absolute_url }})

출발노드 open list(우선순위 큐)에 넣는다.
출발노드 open list에서 pop(), closed list에 추가
출발노드를 기준으로 주변노드를 탐색해 F가중치와 부모노드 구함
계산된 주변 노드 open list에 push()

![]({{ "/assets/images/algo/astar4.png" | absolute_url }})

open list에서 F값이 가장 작은 노드 pop()
주변 탐색 가능한 노드 찾기
- 출발노드는 closed list에 존재하므로 무시
- 장애물도 무시
F가 54인 두개 노드는 open list에 있으므로 현재 노드를 거쳐가는 경로 가중치와 비교
- F=54의 G=14가 F=40을 거쳐가는 G=20보다 작으므로 값을 변경하지 않음
F=40 closed list push

![]({{ "/assets/images/algo/astar5.png" | absolute_url }})

open list에서 F값이 가장 작은 노드 pop() : F=54
주변 탐색 가능한 노드 찾기
- closed list에 존재하는 노드 무시
- 장애물도 무시
F가중치를 비교해 기전의 값이 더 작으면 갱신하지 않음
open list에 없는 노드 F 가중치 계산후 push()

위와 같은 과정을 반복한다.

![]({{ "/assets/images/algo/astar6.png" | absolute_url }})

![]({{ "/assets/images/algo/astar7.png" | absolute_url }})

![]({{ "/assets/images/algo/astar8.png" | absolute_url }})

![]({{ "/assets/images/algo/astar9.png" | absolute_url }})

![]({{ "/assets/images/algo/astar10.png" | absolute_url }})

목표노드에서 부터 부모노드를 따라서 되돌아가면 최단경로가 구해지는 것을 볼 수 있다.

C언어 구현

heuristic

int heuristic(Vertex v, int x,int y, int *pre){
    int res;
    
    // h(x)함수 즉, 출구에서 얼마나 걸리는지 계산한다.(맨하탄)
    res = ((abs(end.x-x)+abs(end.y-y))*10);
    
    *pre = v.g_x;
    
    // 대각선인 경우
    if(abs(v.x-x)==abs(v.y-y)){
        *pre = *pre +14;
    }else{
        *pre = *pre +10;
    }
    // f(x) = g(x) + h(x)
    return res+(*pre);
}

open list

void add_openlist(Queue * q,Vertex v){
    Vertex tmp;
    // pw는 이전 weigt
    int i,j,w,pre;
    
    // 인접한 정점 확인
    for(i=v.x-1;i<=v.x+1;i++){
        
        if(i<1||i>MAX)continue;             // 범위를 벗어나면 통과한다.
        for(j=v.y-1;j<=v.y+1;j++){
            if(j<1||j>MAX)continue;         // 범위를 벗어나면 통과한다.
            if(i==v.x&&j==v.y)continue;     // i와 j가 현재 노드랑 같으면 통과
            if(map[i][j]!=0)continue;      // 길이 아니면 통과
            
            // 가중치 f(x)
            w = heuristic(v, i, j, &pre);
            
            // 가중치가 현재보다 낮거나 기록이 안되어있으면 갱신
            if(w<weight[i][j]||weight[i][j]==0){
                weight[i][j]=w;
                // 부모 노드의 정보를 저장한다.
                parent[i][j] = (v.x*MAX+2)+v.y;
                
                // 출구를 찾으면 종료
                if(end.x == i && end.y ==j)return;
                
            }
            tmp.x = i;
            tmp.y = j;
            tmp.g_x = pre;
            enQueue(q, tmp);
        }
    }   
}

astar

void astar(Vertex s,Vertex e){
    
    Queue * q = creat_queue();
    
    Vertex v;
    
    // 시작점의 weight는 0이다.
    weight[s.x][s.y] = 0;
    // 시작점은 부모노드를 갖고 있지 않는다.
    parent[s.x][s.y]=-1;
    // 시작점에서 움직인 거리(gx)는 0이다.
    s.g_x = 0;
    
    v = s;
    
    add_openlist(q,v);
    
    while(!is_empty(q)){
        
        // 현재 점을 Closed list에 추가 >> maze에 바로표시
        maze[v.x][v.y]=CLOSED;
        v = front(q);
        deQueue(q);
        
        // 새로운 인접노드를 추가해준다.
        add_openlist(q, v);   
    }   
}

backtracking

void backtracking(){
    int i, j, back;
    
    i  = parent[end.x][end.y] / MAX+2;
    j  = parent[end.x][end.y] % MAX+2;
    
    while( parent[i][j] != -1)
    {
        back = parent[i][j];
        
        maze[i][j] = FINAL;
        
        i  = back / MAX+2;
        j  = back % MAX+2;
    }
    map[start.x][start.y] = FINAL;
}

단점

맵의 크기가 커지면 open list나 close list의 목록에 수백에서 수천 개의 노드가 들어갈 수 있기 때문에, 메모리를 많이 사용하게 된다. 또한 시작노드에서 목표노드까지 경로가 존재하지 않는다면, A*는 시작 위치에서 도달 할 수 있는 모든 위치를 검색해 비효율적이다.

A* 알고리즘의 가장 근본적인 약점은 열린 목록과 닫힌 목록을 관리하는 비용이다. 이를 극복하기 위하여 열린 목록과 닫힌 목록을 사용하지 않는 IDA* 알고리즘이 제안되었다. 그러나 IDA* 알고리즘은 깊이 우선 검색을 사용하여 메모리 공간을 적게 사용하는 대신 노드들을 재 방문해야하는 단점이 있다.

참고사이트

위키피디아

PreviousRed-Black 트리 NextHeap

Last updated 3 years ago

Was this helpful?