A* 알고리즘이 도대체 뭔데?? (with java)

🖥️ A* 알고리즘의 동작 과정과 특징 with java

 

 

 

A* 알고리즘은 주로 게임에서 길을 찾는 데 활용됩니다!!

 

 

 

A* 알고리즘이란 '출발 노드에서 목표 노드까지의 최단 거리를 구하는 알고리즘'을 의미합니다. '에이스타 알고리즘'이라고도 합니다. 이는 다익스트라 알고리즘에 기반을 두고 있습니다. 따라서, A*에 대해 본격적으로 알아보기 전에 다익스트라에 대한 기본적인 부분을 간략하게 짚어보겠습니다.

 

 

---

✅  다익스트라 알고리즘에 대해 먼저 알아보자!

 

다익스트림 알고리즘이란 '출발 노드에서 다른 모든 노드까지의 최단 거리를 각각 구하는 알고리즘'을 의미합니다. 

 

 

동작 과정

동작과정을 간단히 추상화하자면 다음과 같습니다. 

1. 준비: 출발지와 최단 거리 테이블을 초기화합니다. 
2. 선택: 방문하지 않은 장소 중에서 최단 거리가 가장 짧은 노드를 선택합니다.
3. 갱신: 해당 노드를 거쳐 다른 노드로 가는 거리를 계산하여 해당 값에 따라 최단 거리 테이블을 갱신합니다.
4. 반복: 모든 노드를 방문할 때까지 선택과 갱신의 과정을 반복합니다. 

 

 

특징

다익스트라 알고리즘은 다이나믹 프로그래밍과 그리디 알고리즘에 기반을 두고 있습니다.

 

• 확실성: 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾습니다.
• 다이나믹 프로그래밍: 여러 단계를 거치며 한 번 처리된 노드의 최단 거리는 고정되어 변동되지 않습니다.
• 그리디: 매 상황에서 방문하지 않았으면서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복합니다.
• 동작 조건: 음의 간선이 없을 때만 사용 가능합니다. 왜냐하면 음의 간선에 따라서 이미 방문 처리한 노드가 다시 갱신되어야 할 수도 있습니다. 하지만 다익스트라에서는 이미 방문한 노드를 재방문하지 않기 때문입니다. 
• 최단 경로 정보: 최단 거리뿐만 아니라 경로에 관한 정보를 구하기 위해서는 기존 다익스트라 알고리즘에 추가적인 코드를 포함해야 합니다. 

 

 

 

---

⛱️  A* 알고리즘에 대해 알아보자!

 

 

다익스트라 알고리즘은 출발 노드에서 다른 모든 노드까지의 최단 거리를 구하지만,

A* 알고리즘은 출발 노드에서 목표 노드까지의 최단 거리만을 구합니다.

 

 

 

A*은 다익스트라 기반이지만,
어째서 목표 노드까지의 최단 거리만 구하는 걸까요?

다익스트라 알고리즘과의 가장 큰 차이점은 '휴리스틱'입니다. A*는 휴리스틱 함수를 통해 예상 비용을 계산하여 다음 방문할 노드를 고려합니다. 이에 따라 불필요한 노드를 방문하고 처리하는 과정을 단축시킬 수 있습니다.

 

 

얼마나 단축시킬 수 있는지 직접 시각화해서 살펴보겠습니다!

 

 

 

 

다익스트라 알고리즘

 

 

파랗게 색칠된 부분이 최단 경로를 구하면서 탐색한 노드들입니다. 여기서 A* 알고리즘을 사용한다면...!!

 

 

 

 

아래와 같이 탐색 노드 범위가 굉장히 줄어듭니다!

 

A* 알고리즘

 

 

 

이렇게 탐색 노드 범위를 줄여줄 수 있는 게 바로 휴리스틱 덕분입니다! 휴리스틱 함수를 사용하는 과정은 다음과 같습니다. 

 

 

 

여기 f(n)이라는 함수가 있습니다. 

 

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

 

 

 

g(n)은 출발 노드부터 현재 노드까지의 비용을 의미합니다. h(n)은 현재 노드에서 목표 노드까지의 예상 비용을 의미합니다. 그리고 g(n)과 h(n)을 더한 것이 f(n)입니다. 이 f(n)이 가장 작은 노드가 다음 노드로 선택됩니다. f(n)이 가장 적은 노드를 찾기 위해 일반적으로 우선순위 큐가 사용됩니다. 

 

 

A*은 휴리스틱 함수에 따라 그 성능이 좌지우지됩니다. 휴리스틱 함수에는 여러 종류가 있으며, 이는 A*의 전반적인 동작 과정을 살펴본 뒤 마지막에 자세히 다뤄보겠습니다.

 

 

 

 

A* 알고리즘 동작과정

동작과정에 대해 정리했습니다. 

 

1. 초기화
   •    시작 노드 생성
   •    우선순위 큐에 시작 노드 삽입 
   •    최소 비용 저장 배열을 무한대로 초기화 (단, 시작 노드는 0으로 초기화)
   •    경로 복원을 위한 경로 저장 배열 선언
2. 선택
   •    우선순위 큐에서 '현재비용 + 예상 비용'이 가장 적은 current 노드 추출
   •    목적지에 도달한 경우, 경로 복원
3. 갱신
   •    current 노드에서 이웃 노드까지의 예상 비용 각각 계산
   •    이웃 노드까지의 '현재 비용 + 예상 비용'이 원래의 비용보다 적다면 비용 갱신, 우선순위 큐 이웃 노드 삽입, 경로 저장
4. 반복
   •    목적지에 도착할 때까지 2, 3의 과정 반복

 

 

 

휴리스틱 함수가 멍청하다면
최단 경로를 찾지 못할 수도 있을까?

 

 

 

우선 휴리스틱 함수가 제대로 된 예상 비용을 전달해주지 못한다면, 우선순위 큐 질서가 흐트러질 것입니다. 이에 따라 최단 경로에 적합하지 않은 노드가 갱신될 수 있습니다. 휴리스틱으로 현재 노드를 적절하게 선택하게 하지 못한다면, 최단 경로를 못 찾을 수도 있습니다.

 

 

예를 들어 A부터 B까지 최단 경로가 10이라면 13이라는 더 큰 값을 찾게 될 수도 있습니다. 물론 이러한 경우는 드문 걸로 알고 있습니다. 각 문제 상황에 따라 적절한 휴리스틱을 사용하는 것이 중요합니다. 

 

 

그러면 어떤 휴리스틱 함수를 어떻게 사용하는 게 바람직할까요? 이를 위해서 휴리스틱 함수의 의미부터 살펴봅시다. 

 

 

휴리스틱 함수란 '가용한 정보를 기반으로 각 분기 단계에서 어느 한 분기를 선택하기 위해 사용하는 다양한 탐색 알고리즘의 대안 함수'을 의미합니다. 말이 조금 어려운데 '어림짐작', '예상거리'라고 간단히 파악하셔도 됩니다. 대표적인 예시는 다음과 같습니다. 

 

 

 

1. 맨해튼 거리(Manhattan Distance)

 

 

 

 : 두 지점 간의 x 좌표 차와 y 좌표 차의 합을 통해 가로와 세로의 길이를 구합니다. 

 

맨해튼

 

맨해튼 도로가 격자무늬로 나누어졌다 보니 거리를 계산할 때 x차 y차 더하기만 하면 됩니다. 신기하죠..ㅎㅎ 한국에도 이런 길이 있으려나요? 그래서 위와 같은 함수를 맨해튼 거리라고 한답니다. 

 

 

 

2. 유클리드 거리(Euclidean Distance)

 

​

 : 두 노드 사이의 대각선 길이를 구하는 공식입니다. 피타고라스 공식과 동일합니다. 맨해튼 거리와는 다르게 대각선 이동이 가능할 때 사용되곤 합니다. 

 

 

3. 패턴 데이터베이스

 : 특정 문제에 대해 미리 계산된 패턴 데이터베이스를 통해 휴리스틱을 계산합니다. A*을 활용하는 실제 서비스에서는 하나의 수식만을 통해서 휴리스틱을 계산하기에는 정확성이 떨어질 수 있습니다. 따라서 데이터베이스를 미리 구축하는 것이 최단 경로 계산에 도움이 될 것입니다. 

 

 

A* 알고리즘 특징

1. 기반: 다익스트라 알고리즘 원리에 기반을 두었습니다. 차이점은 휴리스틱 함수를 통해 우선순위 큐를 업그레이드합니다.
2. 연산 시간: 출발 지점과 도착지점이 거리가 멀 경우 연산이 오래 걸린다는 단점이 있습니다. 
3. 성능: 휴리스틱 함수에 따라 성능이 극명하게 달라집니다. 따라서, A*에 기반을 두어 개량한 다양한 알고리즘 등장했습니다.(Weighted A*, LPA*, IDA*, D*, D* Lite, JPS)

 

 

A* 알고리즘 자바 소스코드

아래 소스코드는 GPT를 통해 얻은 간단한 소스코드입니다. A*의 전반적인 이해를 위해 가볍게 읽어보시는 걸 추천합니다. 더 자세히 알아보고 싶다면 'a* algorithm java' 검색해 보셔서 살펴보세요! 한국에는 자료가 많이 없더라고요.

 

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

class Node implements Comparable<Node> {
    int x, y;  // 현재 노드의 좌표
    int cost;  // 시작점에서 현재 노드까지의 총 비용
    int heuristic;  // 현재 노드에서 목적지까지의 예상 비용

    public Node(int x, int y, int cost, int heuristic) {
        this.x = x;
        this.y = y;
        this.cost = cost;
        this.heuristic = heuristic;
    }

    // PriorityQueue에서 우선순위를 정하기 위한 메서드
    @Override
    public int compareTo(Node other) {
        return Integer.compare(this.cost + this.heuristic, other.cost + other.heuristic);
    }
}

public class AStar {
    // 이동 가능한 방향 (상, 하, 좌, 우, 대각선)
    private static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};

    public static List<int[]> findPath(int[][] grid, int[] start, int[] goal) {
        int rows = grid.length;
        int cols = grid[0].length;

        PriorityQueue<Node> openSet = new PriorityQueue<>();
        openSet.add(new Node(start[0], start[1], 0, heuristic(start, goal))); // 초기화: 시작 노드 초기화

        // 이전 노드를 저장하기 위한 배열
        Node[][] cameFrom = new Node[rows][cols];

        // 초기화: 시작점에서 각 노드까지의 최소 비용을 저장하는 배열
        int[][] costSoFar = new int[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                costSoFar[i][j] = Integer.MAX_VALUE;
            }
        }
        costSoFar[start[0]][start[1]] = 0;

        while (!openSet.isEmpty()) {
            Node current = openSet.poll();

            if (current.x == goal[0] && current.y == goal[1]) {
                // 목적지에 도달했을 경우 경로를 복원(복기)
                return reconstructPath(cameFrom, goal);
            }

            for (int[] direction : DIRECTIONS) {
                int nextX = current.x + direction[0];
                int nextY = current.y + direction[1];

                if (nextX >= 0 && nextX < rows && nextY >= 0 && nextY < cols && grid[nextX][nextY] == 0) {
                    int newCost = current.cost + 1;

                    if (newCost < costSoFar[nextX][nextY]) { // 갱신: 이 때 휴리스틱은 연관x(휴리스틱은 우선순위 큐 조정에만 도움을 줌.)
                        costSoFar[nextX][nextY] = newCost;
                        Node neighbor = new Node(nextX, nextY, newCost, heuristic(new int[]{nextX, nextY}, goal));
                        openSet.add(neighbor);
                        cameFrom[nextX][nextY] = current;
                    }
                }
            }
        }

        // 경로가 없는 경우
        return Collections.emptyList();
    }

    private static int heuristic(int[] a, int[] b) {
        // 휴리스틱 함수 (예상 비용) - 여기서는 맨해튼 거리 사용
        return Math.abs(a[0] - b[0]) + Math.abs(a[1] - b[1]);
    }

    private static List<int[]> reconstructPath(Node[][] cameFrom, int[] goal) {
        List<int[]> path = new ArrayList<>();
        Node current = new Node(goal[0], goal[1], 0, 0);

        while (current != null) {
            path.add(new int[]{current.x, current.y});
            current = cameFrom[current.x][current.y];
        }

        Collections.reverse(path);
        return path;
    }

    public static void main(String[] args) {
        int[][] grid = {
                {0, 0, 0, 0, 0},
                {0, 1, 1, 0, 0},
                {0, 0, 0, 1, 0},
                {0, 1, 0, 0, 0},
                {0, 0, 0, 0, 0}
        };

        int[] start = {0, 0};
        int[] goal = {4, 4};

        List<int[]> path = findPath(grid, start, goal);

        if (!path.isEmpty()) {
            for (int[] point : path) {
                System.out.println("(" + point[0] + ", " + point[1] + ")");
            }
        } else {
            System.out.println("경로가 없습니다.");
        }
    }
}