[알고리즘] A* 알고리즘

※ 해당 포스팅은 개인의 공부 정리용 글입니다. 틀린 내용이 있다면 추후 수정될 수 있습니다.

※ 해당 포스팅은 하기 출처들을 참조하였습니다.

- 존 캐리, 코딩 테스트를 위한 자료구조와 알고리즘 with C++, 도서출판 길벗, 2022

 

 

 

이번 포스팅에서는 특정 정점간의 최단거리를 계산하는데 있어 효율적인 A* 알고리즘에 대해 알아보겠습니다.

1. 개요

 A* 알고리즘은 다익스트라 알고리즘과 마찬가지로 최단 거리(경로)를 구하는 데 사용하는 알고리즘이며, 시작점부터 방문하여 연결된 정점들과 값을 비교하는 방식은 비슷하나 다음과 같은 차이점이 있습니다.

 

- 1) 모든 정점이 아닌 시작점과 목표지점 간의 최단 거리(경로)를 계산

- 2) 정점의 값(F)을 지금까지의 이동 비용(G)과 목표 지점까지의 예상 이동 비용(H)의 합으로 계산(F = G + H)

- 3) 다음에 방문할 정점을 빠르게 찾기 위해 방문 예정을 우선순위 큐(priority queue)에 저장

 

  특히 2번의 목표지점까지의 예상 이동 비용을 휴리스틱 추정값(이하 H)이라고 하는데, 해당 값을 구하는 로직에 따라 알고리즘의 성능이 좌우됩니다. 좌표계에서 사용할 수 있는 일반적인 방법으로는 도착점까지의 직선거리를 피타고라스의 정의를 통해 구하는 방법이 있습니다.

 

그림 1. 그래프 예시

 그림 1은 A* 알고리즘을 적용하기 좋게 각 정점에 좌표를 설정한 그래프 예시입니다. 그래프 간의 거리는 좌표를 통해 계산한 직선 거리 값을 소수점 둘째자리까지 반올림한 것입니다. H는 현재 위치에서 목표지점까지의 직선거리를 계산하여 구하였습니다.

 

 다음은 그림1의 그래프의 0번에서 출발하여 6번 정점까지 가는 경로를 A* 알고리즘으로 구하는 과정을 도식화한 것입니다. 

 

그림 2. A* 알고리즘 예시

 우선 처음에는 다익스트라 알고리즘과 마찬가지로 시작점의 값을 0으로, 나머지 모든 정점의 값을 무한대(혹은 아주 큰 값)로 초기화합니다. 이어서 연결된 정점의 값을 계산하는데, 위에서 얘기한대로 현재까지의 이동 비용(G)과 예상 이동 비용(H)을 합쳐서(F) 계산합니다.

 

 그림 2에서 처음 1번 정점의 값을 계산하는 부분을 보면 G는 이전 정점의 G값(시작점이므로 0)과 해당 정점까지의 이동 비용(2)의 합으로 계산합니다. 그리고 H는 1번 정점의 좌표 (2, 0)에서 목표 지점(4, 4) 까지의 직선 거리를 피타고라스 법칙에 의해 계산한 값으로 약 4.47(√20)입니다. 합치면 F = 6.67이 되므로 해당 값을 1번 정점의 값으로 기록합니다. 같은 과정을 반복하면 2번 정점의 값은 5.66, 3번 정점의 값은 6.32가 됩니다. 참고로 이때 다음 G값 계산을 위해 G값도 함께 저장해야 합니다(각 정점의 괄호 안 수치).

 

 위의 계산값(F, G)들을 정점 번호와 함께 우선순위 큐에 저장하는데, 이 때 우선순위 큐는 F값이 낮을수록 우선순위가 높도록 구현해야 합니다. 이제 우선순위 큐에서 출력한 가장 예상 비용이 작은 정점을 방문하여 위 과정을 반복하면 됩니다. 위 예시에서는 0 > 2 > 4 > 6 순서로 이동 시 6.07로 가장 적은 비용의 경로임을 확인할 수 있습니다.

 

 

2. 코드 구현

 A* 알고리즘을 구현하려면 우선순위 큐를 먼저 준비해야 합니다. 우선순위 큐는 하기 포스팅에서 작성했던 코드를 그대로 사용하도록 하겠습니다.

https://sam0308.tistory.com/74

[알고리즘] 우선순위 큐(Priority Queue)

 

 그리고 Open에 F, G 등의 정보를 저장하기 위한 Node 클래스와 좌표를 저장하기 위한 Point 클래스를 선언하였습니다.

class Node : IComparable<Node>
{
    public int F;
    public int G;
    public int node;

    public int CompareTo(Node other)
    {
        if (F == other.F)
            return 0;

        return F < other.F ? 1 : -1;
    }
}

class Point
{
    public int x;
    public int y;
}

 최종 예상 비용 및 현재까지의 비용을 저장하기 위한 변수 F와 G, 그리고 현재 위치를 저장하기 위한 변수를 선언하였습니다. 우선순위 큐에서 사용할 수 있도록 IComparable 인터페이스를 상속하여 CompareTo를 구현하였으며, F가 가장 낮은 경우를 출력하도록 작성했습니다. Point 클래스는 단순히 좌표 저장용으로 작성했습니다.

 

 다음은 C#으로 구현한 A* 알고리즘 예제입니다.

static void Main(string[] args)
{
    float[,] graph =
    {
        { -1f, 2.0f, 2.83f, 3.16f, -1f, -1f, -1f },
        { 2.0f, -1f, 2.0f, -1f, -1f, 1.41f, -1f },
        { 2.83f, 2.0f, -1f, 1.41f, 2.24f, 1.41f, -1f },
        { 3.16f, -1f, 1.41f, -1f, 2.24f, -1f, -1f },
        { -1f, -1f, 2.24f, 2.24f, -1f, -1f, 1.0f },
        { -1f, 1.41f, 1.41f, -1f, -1f, -1f, 3.16f },
        { -1f, -1f, -1f, -1f, 1.0f, 3.16f, -1f }
    };
    Point[] points =
    {
        new Point() { x = 0, y = 0 },
        new Point() { x = 2, y = 0 },
        new Point() { x = 2, y = 2 },
        new Point() { x = 1, y = 3 },
        new Point() { x = 3, y = 4 },
        new Point() { x = 3, y = 1 },
        new Point() { x = 4, y = 4 }
    };

    Astar(graph, points, 0, 6); 
}

static float CalDistance(int y, int x)
{
    float sum = (float)(Math.Pow(y, 2) + Math.Pow(x, 2));
    return (float)Math.Round(Math.Sqrt(sum), 2);
}

 우선 기존까지와 마찬가지로 그래프를 2차원 배열로 표현하였고, 도착지점까지의 거리를 계산하기 위하여(휴리스틱 연산) 각 정점들의 좌표를 저장한 배열을 선언하였습니다. 추가로 피타고라스 연산을 통해 거리를 계산하는 함수를 따로 선언하였습니다.

 

static void Astar(float[,] graph, Point[] points, int start, int goal)
{
    int size = graph.GetLength(0);
    int goalY = points[goal].y, goalX = points[goal].x;

    float[] open = new float[size];
    bool[] closed = new bool[size];
    Array.Fill(open, float.MaxValue);

    PriorityQueue<Node> que = new PriorityQueue<Node>();
    float dist = CalDistance(goalY - points[start].y, goalX - points[start].x);
    que.Enqueue(new Node() { F = dist, G = 0, node = start });

    while (que.Count > 0)
    {
        Node curNode = que.Dequeue();
        int cur = curNode.node;
        if (closed[cur])
            continue;

        int curX = points[cur].x;
        int curY = points[cur].y;
        closed[cur] = true;
        Console.WriteLine($"{cur}번 정점 방문!");
        if (cur == goal)
            break;

        // 연결된 노드 탐색
        for (int next = 0; next < size; next++)
        {
            // 이미 방문했거나 연결되지 않았다면 스킵
            if (closed[next] || graph[cur, next] < 0)
                continue;

            // 휴리스틱 연산
            float H = CalDistance(goalX - points[next].x, goalY - points[next].y);
            float G = curNode.G + graph[cur, next];
            // 현재 예상 비용보다 크다면 스킵
            if (G + H > open[next])
                continue;

            que.Enqueue(new Node() { F = G + H, G = G, node = next });
            open[next] = G + H;
        }
    }
    Console.WriteLine($"{start}정점부터 {goal}번 정점까지의 최단 거리: {Math.Round(open[goal], 2)}");
}

사진 1. A* 알고리즘 예제

 우선 예상 비용을 저장해둘 open 함수와 방문 여부를 저장할 closed 배열을 선언하였습니다. 정점 값을 저장해둘 open 배열은 다익스트라와 마찬가지로 아주 큰 값으로 초기화해두고, 방문 예정지점을 저장해둘 Node 클래스를 저장하는 우선순위 큐를 선언했습니다. Node 클래스는 CompareTo()를 F값이 작은 쪽의 우선순위가 높도록 구현했으므로, 저장해둔 예정 방문 지점 중 가장 예상 비용이 낮은 정점을 우선적으로 출력하게 됩니다.

 

 우선순위 큐에 시작점을 넣으며 시작하고 이 때 G는 0, H는 시작점에서 목표지점까지의 최단 경로를 계산한 값입니다. 반복문 내에서는 우선순위 큐에서 Node를 출력하여 방문하고, 방문 여부를 출력합니다(나중에 경로를 이용할 예정이라면 별도의 자료구조에 저장합니다). 이후 각 정점을 확인하여 아직 방문하지 않은 연결된 정점이라면 새롭게 F 값을 계산하고, 해당 값이 이미 저장된 값보다 작다면 해당 값으로 갱신하고 우선순위 큐에도 방문 예정을 추가합니다. 해당 과정을 반복하며 목표 지점에 도착하는 순간 루프를 종료합니다.

 

 사진1의 결과를 보면 그림2의 예시와 같이 0 > 2 > 4 > 6번 순으로 방문하며, 6.07의 비용을 출력함을 확인할 수 있습니다.

 

 

3. 장점과 단점

 예제를 보면 알 수 있듯이, A* 알고리즘은 보다시피 다익스트라 알고리즘처럼 그래프의 모든 정점을 방문하지는 않습니다. 대신 좀 더 고도화된 비용 계산 로직과 우선순위 큐를 이용하여 특정 정점간의 최단 경로 및 비용을 보다 신속하게 계산할 수 있다는 장점이 있습니다. 휴리스틱 추정 값을 계산하는 휴리스틱 함수를 어떻게 구현하느냐에 따라 더욱 빨라질 수 있습니다.

 

 단점은 휴리스틱 함수의 의존도가 높다는 것입니다. 목표 지점까지의 예상 비용을 계산하는 과정에 잘못된 부분이 있었다면, 해당 알고리즘의 결과물이 최단 거리(경로)인지 신뢰하기 어려워집니다. 또한 다익스트라와 달리 시작점 뿐 아니라 목표 지점까지 정확히 지정하여 연산을 수행하므로, 목표 지점이 변경된다면 완전히 처음부터 다시 계산해야 합니다. 물론 이런 단점들을 감수하더라도, 특정 정점간의 최단 거리(경로)를 계산하는 데 있어 유용한 알고리즘입니다.