A*(에이스타) 알고리즘이란?
시작점에서 목표 지점까지 가장 비용이 적은 경로를 찾는 알고리즘.
휴리스틱 함수(Heuristic Function)
휴리스틱 함수는 알고리즘의 가장 중요한 부분이자 또 다른 길 찾기 알고리즘인 다익스트라 알고리즘과의 차이점이기도 하다.
A* 알고리즘은 f(n) = g(n) + h(n) 이라는 점수 계산 방식을 사용한다. 여기서
- f(n): 현재 노드 n의 점수. 탐색을 위해 선택할 기준.
- g(n): 시작 노드에서 현재 노드까지의 실제 경로 비용.
- h(n): 휴리스틱 함수, 현재 노드에서 목표 노드까지의 예상 경로 비용(미래 비용).
이다.
여기서 가장 적은 f(n)의 값이 가장 적은 노드를 탐색한다.
작동 과정
- 시작 노드 선택: 시작 노드를 탐색할 노드 집합인 열린 집합(Open Set)에 추가하고, 해당 노드의 g(n) 값을 0으로 설정.
- 목표 지점 탐색: 열린 집합에서 f(n) 값이 가장 작은 노드를 선택해 현재 노드로 설정.
- 이웃 노드 탐색: 현재 노드와 연결된 이웃 노드들을 확인하고, 이웃 노드들의 g(n)과 h(n)을 계산하여 f(n) 값을 갱신.
- 경로 갱신: 이웃 노드를 열린 집합에 추가. 이때, 경로가 더 짧은 경우 g(n) 값을 업데이트하고 이전 노드를 현재 노드로 기록.
- 목표 도달: 목표 노드에 도달하면 경로 탐색 완료. 시작 노드부터 목표 노드까지의 최단 경로를 추적.
Java
import java.util.*;
class AStarDiagonal {
static class Node {
int x, y;
int gCost; // 시작점에서 현재 노드까지의 실제 비용
int hCost; // 목표까지의 예상 비용(휴리스틱)
Node parent;
public Node(int x, int y) {
this.x = x;
this.y = y;
this.gCost = Integer.MAX_VALUE; // 시작 시 매우 큰 값으로 설정
this.hCost = 0;
this.parent = null;
}
public int getFCost() {
return gCost + hCost;
}
}
// 그리드 크기
static final int GRID_SIZE = 5;
// 8 방향 이동: 상하좌우, 대각선 4 방향
static final int[][] DIRECTIONS = {
{0, 1}, {0, -1}, {1, 0}, {-1, 0}, // 상하좌우
{1, 1}, {1, -1}, {-1, 1}, {-1, -1} // 대각선 4방향
};
// 목표까지의 휴리스틱 함수 (체스판 거리 사용)
public static int chebyshevDistance(Node a, Node b) {
return Math.max(Math.abs(a.x - b.x), Math.abs(a.y - b.y));
}
// A* 알고리즘
public static List<Node> aStar(Node start, Node goal, Node[][] grid) {
PriorityQueue<Node> openList = new PriorityQueue<>(Comparator.comparingInt(Node::getFCost));
Set<Node> closedList = new HashSet<>();
start.gCost = 0;
start.hCost = chebyshevDistance(start, goal);
openList.add(start);
while (!openList.isEmpty()) {
Node current = openList.poll();
if (current.equals(goal)) {
return constructPath(current); // 목표에 도달 시 경로 반환
}
closedList.add(current);
for (int[] direction : DIRECTIONS) {
int newX = current.x + direction[0];
int newY = current.y + direction[1];
if (isInBounds(newX, newY) && !closedList.contains(grid[newX][newY])) {
Node neighbor = grid[newX][newY];
int tentativeGCost = current.gCost + 1; // 기본 이동 비용 1
if (tentativeGCost < neighbor.gCost) {
neighbor.gCost = tentativeGCost;
neighbor.hCost = chebyshevDistance(neighbor, goal);
neighbor.parent = current;
if (!openList.contains(neighbor)) {
openList.add(neighbor);
}
}
}
}
}
return null; // 경로가 없을 경우
}
// 경로를 재구성하는 메소드
public static List<Node> constructPath(Node current) {
List<Node> path = new ArrayList<>();
while (current != null) {
path.add(current);
current = current.parent;
}
Collections.reverse(path); // 시작점부터 목표점 순으로 경로를 반환
return path;
}
// 그리드 범위 내에 있는지 확인하는 메소드
public static boolean isInBounds(int x, int y) {
return x >= 0 && x < GRID_SIZE && y >= 0 && y < GRID_SIZE;
}
public static void main(String[] args) {
// 5x5 그리드 생성
Node[][] grid = new Node[GRID_SIZE][GRID_SIZE];
for (int i = 0; i < GRID_SIZE; i++) {
for (int j = 0; j < GRID_SIZE; j++) {
grid[i][j] = new Node(i, j);
}
}
// 시작점과 목표점 설정
Node start = grid[0][0];
Node goal = grid[4][4];
// A* 알고리즘 실행
List<Node> path = aStar(start, goal, grid);
if (path != null) {
System.out.println("경로를 찾았습니다:");
for (Node node : path) {
System.out.println("(" + node.x + ", " + node.y + ")");
}
} else {
System.out.println("경로를 찾지 못했습니다.");
}
}
}
휴리스틱 값 설정하기
휴리스틱 값은 알고리즘이 효율적으로 탐색하기 위한 예상 값일 뿐이기 때문에 실제 값과 다를 수 있다.
휴리스틱 추정 방법
유클리드 거리 (Euclidean Distance):
주로 2차원 평면에서 두 지점 간의 직선 거리를 계산할 때 사용된다.
만약 노드들이 평면 위의 좌표로 표현된다면, 유클리드 거리 공식을 사용하여 추정할 수 있다.
예시: 
여기서 (x1, y1)는 현재 노드의 좌표, (x2, y2)는 목표 노드의 좌표이다.
맨해튼 거리 (Manhattan Distance):
격자 형태의 맵에서 사용할 수 있는 방법으로, 두 지점 사이의 가로, 세로 이동 거리를 합하여 추정한다.
예시:
Dijkstra 알고리즘 방식:
휴리스틱 값이 0인 경우, A* 알고리즘은 다익스트라 알고리즘처럼 동작한다. 즉, 모든 경로를 탐색하지만 가장 비용이 적은 경로를 선택한다.
목표 노드까지의 거리를 전혀 추정할 수 없을 때는 휴리스틱을 0으로 설정할 수 있다.
요약:
A* 알고리즘은 g(n)과 h(n)을 결합해 효율적으로 탐색합니다.
h(n)을 잘 설계하는 것이 중요합니다.
Working