A-star 알고리즘

A-star 알고리즘이란?

A* 알고리즘은 최단 경로 탐색 알고리즘으로, 다익스트라(Dijkstra)의 장점과 휴리스틱(Heuristic)을 결합한 방식이다.

• 다익스트라: 실제로 이동한 비용(g(n))을 최소화
• A-star: g(n) + 미래에 걸릴 비용 추정(h(n)) = f(n)을 최소화

즉, $f(n)=g(n)+h(n)$ 다음과 같은 식을 가지게 된다.

• g(n): 시작점에서 현재까지 온 실제 비용
• h(n): 현재 위치에서 목표까지의 추정 비용 (휴리스틱)

A-star 알고리즘을 사용하는 이유

• 다익스트라는 모든 방향을 탐색하기 때문에 비효율적일 수 도 있다.
• A-star 는 목표 지향적으로 움직여 불필요한 탐색을 줄이고, 빠르게 경로를 찾아냅니다.

휴리스틱 함수란?

A*의 핵심은 h(n) 을 어떻게 정의하느냐에 달라진다

• 맨해튼 거리 (Manhattan Distance)(격자 지도, 상하좌우 이동에 적합)
  

$$h(n) = |x1 - x2| + |y1 - y2|$$

• 유클리드 거리 (Euclidean Distance)(대각선 이동 가능할 때)

$$h(n) = \sqrt{(x1 - x2)^2 + (y1 - y2)^2}$$

• 체비쇼프 거리 (Chebyshev Distance)(8방향 이동 가능할 때)

$$h(n) = \max(|x1 - x2|, |y1 - y2|)$$

예시)

격자(Grid) 형태의 지도에서 시작점(Start)에서 목표점(Goal)까지 최단 경로를 구하는 방법

• 지도는 0과 1로 구성
• 0 → 빈 칸 (이동 가능)
• 1 → 벽 (이동 불가)
• [0, 0] → [3, 4] 로 가는 최단 경로

import java.util.*;

public class AStarGrid {

    static final int[] DY = {-1, 1, 0, 0};
    static final int[] DX = {0, 0, -1, 1};
    static final int INF = 1_000_000_000;

    static class Node {
        int r, c, g, f;
        Node(int r, int c, int g, int f) {
            this.r = r; this.c = c; this.g = g; this.f = f;
        }
    }

    // 휴리스틱: 맨해튼 거리 (4방향 이동에 대해 Admissible & Consistent)
    static int h(int r, int c, int gr, int gc) {
        return Math.abs(r - gr) + Math.abs(c - gc);
    }

    // 경계 체크
    static boolean inRange(int r, int c, int n, int m) {
        return 0 <= r && r < n && 0 <= c && c < m;
    }

    public static List<int[]> aStar(int[][] grid, int sr, int sc, int gr, int gc) {
        int n = grid.length, m = grid[0].length;

        // 입력 가드: 시작/목표 유효성 및 벽 체크
        if (!inRange(sr, sc, n, m) || !inRange(gr, gc, n, m)) return List.of();
        if (grid[sr][sc] == 1 || grid[gr][gc] == 1) return List.of();

        int[][] g = new int[n][m];
        for (int[] row : g) Arrays.fill(row, INF);

        boolean[][] closed = new boolean[n][m];
        int[][] pr = new int[n][m], pc = new int[n][m];
        for (int[] row : pr) Arrays.fill(row, -1);
        for (int[] row : pc) Arrays.fill(row, -1);

        // 타이브레이커: f 우선, 동률이면 g가 작은 쪽(진척 더 큰 경로)을 먼저
        PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> {
            if (a.f != b.f) return Integer.compare(a.f, b.f);
            return Integer.compare(a.g, b.g);
        });

        g[sr][sc] = 0;
        pq.add(new Node(sr, sc, 0, h(sr, sc, gr, gc)));

        while (!pq.isEmpty()) {
            Node cur = pq.poll();
            if (closed[cur.r][cur.c]) continue;
            closed[cur.r][cur.c] = true;

            // 목표 도착: 최적 경로 확정
            if (cur.r == gr && cur.c == gc) {
                return reconstruct(pr, pc, gr, gc);
            }

            // 이웃 확장
            for (int d = 0; d < 4; d++) {
                int nr = cur.r + DY[d], nc = cur.c + DX[d];
                if (!inRange(nr, nc, n, m) || grid[nr][nc] == 1 || closed[nr][nc]) continue;

                int ng = cur.g + 1; // 균일 격자: 이동비용 1
                if (ng < g[nr][nc]) {
                    g[nr][nc] = ng;
                    pr[nr][nc] = cur.r; pc[nr][nc] = cur.c;
                    int nf = ng + h(nr, nc, gr, gc);
                    pq.add(new Node(nr, nc, ng, nf));
                }
            }
        }
        // 경로 없음
        return List.of();
    }

    // 경로 복원
    static List<int[]> reconstruct(int[][] pr, int[][] pc, int gr, int gc) {
        LinkedList<int[]> path = new LinkedList<>();
        int r = gr, c = gc;
        while (r != -1 && c != -1) {
            path.addFirst(new int[]{r, c});
            int nr = pr[r][c], nc = pc[r][c];
            r = nr; c = nc;
        }
        return path;
    }

    // 실행 예시
    public static void main(String[] args) {
        int[][] grid = {
            {0,0,0,1,0},
            {0,1,0,1,0},
            {0,1,0,0,0},
            {0,0,0,1,0}
        };
        List<int[]> path = aStar(grid, 0, 0, 3, 4);
        if (path.isEmpty()) System.out.println("No path");
        else path.forEach(p -> System.out.println(Arrays.toString(p)));
    }
}