[최단거리] A* 알고리즘

개념

다익스트라 알고리즘을 확장하여 만들어진 경로 탐색 알고리즘이다. 드론이나 로봇 차량의 인공지능을 위해 개발되었다. 

 

A* 알고리즘은 현재 상태의 비용을 $ g(x) $  현재 상태에서 다음 상태로 이동할 때의 휴리스틱 함수를 $ h(x) $ 라고 할 때, 둘을 더한

$ f(x) = g(x) + h(x) $ 가 최소가 되는 지점을 우선적으로 탐색하는 방법이다. 

 

$ f(x) $ 가 작은 값부터 탐색하는 특성상 우선순위 큐가 사용된다. 

 

휴리스틱 함수 $ h(x) $ 에 따라 성능이 극명하게 갈리며, $ f(x) = g(x) $ 일 때는 다익스트라 알고리즘과 동일하다. 

 

• 다익스트라 : 가중치 그래프, 시작 노드 기준으로 모든 노드의 최단 경로 구함, 그리디 알고리즘
• A* : 가중치 그래프, 시작 노드에서 목표 노드까지의 최단 경로만을 구하려 함, 그리디 알고리즘

 

$ f(x) = g(x) + h(x) $
가장 좋은 길 = 지금까지 온 길 + 다음 목적지까지 가야하는 길

 

 

• 조사하지 않은 node 중에서 가장 효율적이라고 판단되는 node를 찾음
• 조사한 노드들은 CLOSED list에 저장, 조사하지 않은 노드들은 OPEN list에 저장
• 알고리즘의 시작 : CLOSED list는 공집합, OPEN list는 시작점만

 

알고리즘 스케치

1. OPEN list에 있는 node들 중 가장 효율적인 노드를 찾아 CLOSED list에 넣고 current 노드라고 함
2. Non-CLOSED 이웃이고 갈 수 있는 모든 노드들에 대해
   1. OPEN list에 없으면 그것을 OPEN list에 추가하고 current node를 그들의 부모노드로 만든다.
   2. $g(x)$와$h(x)$를 계산한다.
   3. 이미 OPEN list에 있으면 부모를 바꾸어 $g(x)$ 를 이용하여 비용을 갱신한다.
3. 목표노드가 CLOSED list에 추가되거나 OPEN list가 비어있으면 종료한다. 

 

 

휴리스틱 함수

 

 

다음 목적지까지 가야하는 길을 구하는 함수 h(x)를 휴리스틱 함수라고 한다.

 

가장 단순하며 대표적인 휴리스틱 함수로는 맨해튼 거리 함수와 유클라디안 거리 함수가 있다. 

 

맨해튼 거리 함수

2차원 평면 공간에서 두 점 p와 q 사이의 거리를 특정하는 방법 충 하나로, 두 점 사이의 수평 및 수직 이동 거리의 합으로 정의된다.

 

두 점을 (p1, p2) , (p2, q2) 이라고 하면

 

맨해튼 거리 = |p1 - q1| + |p2 - q2|

 

유클라디안 거리 함수

두 점 사이의 거리를 계산할 때 흔히 쓰는 방법이다. 이를 이용하여 유클리드 공간을 정의할 수 있으며, 이 거리에 대응하는 노름을 유클리드 노름이라고 부른다.

 

데카르트 좌표계로 나타낸 점 p와 q가 있을 때 두 유클리드 노름을 이용하여  두 점 p, q의 거리를 계산하면

 

유클리드 거리 계산하기

 

 

 

맨하탄 거리는 항상 유클라디안 거리보다 크거나 같다. 

 

 

예제

값 판정하기

현재 있는 위치에서 다음 위치로 넘어갈 때의 G값(지금까지의 거리) H값(남은 거리) 을 이용하여 F를 계산한다. 

예시 그림에서는 오른쪽 방향으로 가는 것이 가장 적합하므로 오른쪽으로 이동한다.

 

이를 계산하기 위해서는 각 좌표에 g, h 값을 기록해놔야한다. 

일반적인 2차원 정수 배열에서는 여러 값을 넣을 수 없기에 구조체를 선언하여 좌표별로 노드를 만들어준다.

 

struct Node {
    int x, y;
    int g, h;
    Node(int x, int y, int g, int h) : x(x), y(y), g(g), h(h) {}
    int f() const { return g + h; }
};

 

 

가장 작은 값을 탐색해야 하기 때문에 노드를 우선순위 큐에 넣어준다.

 

f값이 작은 순서대로 pop 될 수 있도록 Compare 함수도 만들어준다.

 

struct CompareNode {
    bool operator()(const Node& a, const Node& b) const {
        return a.f() > b.f();
    }
};

 

완성된 A* 알고리즘 코드는 다음과 같다.

 

input으로 갈 수 있는 곳과 갈 수 없는 곳이 구분된 지도와 시작 좌표, 목표 좌표가 들어오고

 

목표지점까지의 거리와 경로를 반환한다. 경로를 찾을 수 없는 경우에는 빈 벡터를 반환한다.

 

상, 하, 좌, 우로만 이동할 수 있으며 기본 거리는 1로 계산한다.

 

vector<pair<int, int>> a_star() {
    vector<vector<int>> g_cost(m + 1, vector<int>(n + 1, INF)); // 비용 추적
    priority_queue<Node, vector<Node>, CompareNode> pq; // 노드들을 f값을 기준으로 정렬하는 우선순위 큐
    map<int, map<int, pair<int, int>>> parent; // 각 노드의 부모 노드를 추적하여 경로를 재구성하기 위한 자료구조
    vector<pair<int, int>> path; // 경로를 추적하고 반환

    g_cost[start_x][start_y] = 0;
    pq.push(Node(start_x, start_y, 0, heuristic(start_x, start_y, target_x, target_y)));
    parent[start_x][start_y] = make_pair(-1, -1);

    while (!pq.empty()) {
        Node current = pq.top();
        pq.pop();

        int x = current.x, y = current.y;

        if (x == target_x && y == target_y) {
            while (x != -1 && y != -1) {
                path.push_back(make_pair(x, y));
                pair<int, int> p = parent[x][y];
                x = p.first;
                y = p.second;
            }
            reverse(path.begin(), path.end());
            return path;
        }

        for (int dir = 0; dir < 4; ++dir) {
            int nx = x + dx[dir], ny = y + dy[dir];
            if (nx >= 0 && nx <= m && ny >= 0 && ny <= n && grid[nx][ny] == 1) {
                int new_g = g_cost[x][y] + 1;
                if (new_g < g_cost[nx][ny]) {
                    g_cost[nx][ny] = new_g;
                    parent[nx][ny] = make_pair(x, y);
                    pq.push(Node(nx, ny, new_g, heuristic(nx, ny, target_x, target_y)));
                }
            }
        }
    }

    return path;  // 비어있는 벡터 반환 (경로를 찾을 수 없는 경우)
}

 

 

 

다익스트라 vs A*

 

• 다익스트라는 A*의 특수한 경우이다. (휴리스틱이 0일 때)
• 다익스트라는 임의의 시작점으로부터 시작하여 모든 정점을 탐색, 최적 경로를 보장하지 않는다.
• A*는 시작지점부터 목표지점까지의 휴리스틱 함수를 통해 추정하여 점수를 매기고, 그 점수를 바탕으로 빠른 탐색을 한다. 최적 경로의 근사값을 보장한다.

다익스트라의 작동 예

A*의 작동 예

 

추정 잔여거리를 사용함으로써 탐색의 단계가 현저히 준 것을 볼 수 있다.

 

 

참고

https://velog.io/@code-10/%EB%A7%A8%ED%95%B4%ED%8A%BC-%EA%B1%B0%EB%A6%ACManhattan-Distance

맨해튼 거리(Manhattan Distance)

https://ablearn.kr/newsletter/?idx=13834809&bmode=view

다수결의 원칙이 적용되는 머신러닝이 있다고요? : "디지털"한 일잘러 되는 비법

https://hyo-ue4study.tistory.com/195