A* Algorithm?
얼마 전에 스타크래프트 길찾기 알고리즘과 관련된 글을 읽으면서 길찾기 알고리즘에 관심이 생기게 되었습니다. 물론 코딩 테스트를 준비하면서 다익스트라를 안보고 풀어보려고 얼마 전에 시도하긴 했지만, 이 다익스트라를 현실 문제에 적용하기엔 썩 좋은 방법은 아니죠. 우리가 사는 세상은 디지털 세상이 아니기 때문입니다.(시뮬레이션 우주 가설이 맞다면 이건 또 다른 문제죠.) 아날로그 세상이기 때문에 고려할 요소들이 너무나도 많습니다.
Dijkstra!
그래도 일단 다익스트라 알고리즘에 대해서 짚어보고 넘어갑시다. 간단하게요.
그래프에서 여러 개의 노드가 있을 때, 특정 노드에서 출발하여 다른 노드로 가는 경로를 구하는 알고리즘 (음의 간선x)
음의 간선은 어쩌냐고 물어보신다면 Bellman-Ford Algorithm을 검색해서 학습하세요. 다익스트라에 대한 이해도가 있다면 금방 구현할 수 있을 것입니다. 일단, 다익스트라는 기본적으로 그리디 알고리즘입니다. 왜 Why? 매번 “가장 비용이 적은 노드”를 선택해 임의의 과정을 반복하기 때문이죠.
다익스트라는 크게 다음과 같은 절차로 진행됩니다.
1. 시작 노드 선정
2. 최단 거리 테이블 생성
3. 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드 선택
4. 해당 노드 거치며 다른 노드로 가는 비용 계산 → 최단 거리 테이블 갱신 (3-4 반복)
음, 하지만 다익스트라를 기본 코드 그대로 구현하게 된다면? 노드의 개수가 많을 경우 너무 느려집니다.
(왜요?) → 모든 노드를 탐색해야 하고, 최소 비용 노드를 또다시 탐색해야 하기 때문입니다.
(그래서 어떻게 해야 해요?) → 수행 속도를 줄이려면, Heap 자료구조(우선순위 큐)를 사용해서 개선된 다익스트라 알고리즘을 사용해야 합니다.
(코드 좀요;) → 얼마 전에 제가 작성한 예제 코드를 첨부할 테니, 천천히 읽어보면 되겠습니다.
import java.util.*;
class Solution {
static int INF = Integer.MAX_VALUE;
static class Node implements Comparable<Node>{
int num, distance;
Node (int n, int d){
this.num = n;
this.distance = d;
}
@Override
public int compareTo(Node node){
return this.distance - node.distance;
}
}
// 인접 리스트 만들기
static List<ArrayList<Node>> list = new ArrayList<ArrayList<Node>>();
// 정점별 최단거리 테이블
static int[] arr;
public int solution(int N, int[][] road, int K) {
int answer = 0;
// 최단거리 테이블 초기화
arr = new int[N+1];
Arrays.fill(arr, INF);
// 인접 리스트 초기화
for(int i = 0; i <= N; i++)
list.add(new ArrayList<Node>());
// 그래프 생성 (양방향인지 단방향인지 신경쓰는 것 필수)
for(int i = 0; i < road.length; i++){
list.get(road[i][0]).add(new Node(road[i][1], road[i][2]));
list.get(road[i][1]).add(new Node(road[i][0], road[i][2]));
}
// 다익스트라 (우선순위 큐 사용)
PriorityQueue<Node> pq = new PriorityQueue<>();
// 1번노드(기준 노드)
pq.add(new Node(1, 0)); arr[1] = 0;
// System.out.println(Arrays.toString(arr));
while(!pq.isEmpty()){
Node tmp = pq.poll();
int cur = tmp.num;
int dis = tmp.distance;
if(arr[cur] < dis) continue;
// 인접 리스트 순회
ArrayList<Node> tmpList = list.get(cur);
for(int i = 0; i < tmpList.size(); i++){
Node next = tmpList.get(i);
int cal = arr[cur] + next.distance;
if(cal < arr[next.num] && cal <= K) {
arr[next.num] = cal;
pq.add(new Node(next.num, cal));
}
}
}
// System.out.println(Arrays.toString(arr));
for(int i = 0; i < arr.length; i++)
if(arr[i] <= K) answer++;
return answer;
}
}
A*!
사실 저는 A* 알고리즘을 이번에 처음 알게 된 것은 아닙니다. 스마트홈 프로젝트를 진행하면서 곁에서 보고 들었던 알고리즘이고, 실제로 프로젝트에 적용되었던 알고리즘이거든요. 기본적으로 A* 알고리즘은 그래프 탐색 알고리즘의 한 종류로, 출발 지점에서 목표 지점까지의 최적 경로를 찾아내는 데 사용됩니다. 이 알고리즘은 특히 경로 탐색 문제에서 많이 사용되며, 최단 경로를 효율적으로 찾으면서도 계산 비용을 최소화하기 때문입니다.
A* 알고리즘은 기본적으로 다익스트라(Dijkstra) 알고리즘과 비슷하지만, 두 가지 중요한 차이가 있습니다.
• 실제 비용(g 값): 출발 지점에서 현재 지점까지의 실제 경로 비용.
• 추정 비용(h 값): 현재 지점에서 목표 지점까지의 예상 경로 비용(휴리스틱).
휴리스틱이라는 단어는 인공지능을 다루면서 많이 들어보셨을 겁니다. 전 휴리스틱을 좋아합니다. 재밌거든요. (내 X대로 해도 된다는 뜻)
A* 알고리즘의 핵심은 휴리스틱 함수(h 값)입니다. 이 함수는 현재 지점에서 목표 지점까지의 “추정” 비용을 계산하는데, 일반적으로 맨해튼 거리(Manhattan Distance)나 유클리드 거리(Euclidean Distance)가 사용됩니다.
• 맨해튼 거리: 직선 경로를 사용할 수 없는 경우(예: 그리드 기반 맵)에서 사용하는 방식으로, 가로와 세로 이동만 가능한 경우에 사용합니다.
• 유클리드 거리: 평면 상에서 두 점 간의 직선거리를 계산하는 방식으로, 직선 경로가 허용되는 환경에서 자주 사용됩니다.
휴리스틱 함수는 A* 알고리즘의 성능에 크게 영향을 미칩니다. 휴리스틱 함수가 목표 지점과의 실제 거리를 정확하게 예측할수록 탐색 효율이 높아집니다. 휴리스틱이 없다면 일반적인 다익스트라와 차이가 없다고 봐도 무방하죠. 그만큼 핵심이라는 겁니다. 내 마음대로 성능을 조절할 수 있다니 얼마나 관대한가!
A* 알고리즘 절차
-
f(x)를 오름차순 우선순위 큐에 노드로 삽입
-
우선순위 큐에서 최우선 노드를 pop
-
해당 노드에서 이동할 수 있는 노드를 탐색
-
그 노드들의 f(x)를 구한다.
-
그 노드들을 우선순위 큐에 삽입
-
목표 노드에 도달할 때까지 반복
단점? 단점이라면..
아니, 이렇게 완벽한 알고리즘인데 단점이 있다고요? 그렇죠. 모든 길찾기 연산은 비용입니다. 맵이 복잡하면 복잡할수록 성능이 나빠질 수도 있습니다.
일반적으로 스타크래프트는 region으로 맵을 나누고 region을 기반으로 A* 알고리즘을 적용하는 것으로 알려져 있습니다. A* 알고리즘이 최적의 경로를 찾아내는 능력은 뛰어나지만, 실제 게임 환경에서는 종종 예기치 못한 상황들이 발생할 수 있습니다. 예를 들어, 드라군과 같은 유닛이 특정 위치를 인식하지 못하고 다른 경로를 선택하게 되는 문제는 동적 환경에서 발생하는 전형적인 문제입니다. 이는 A* 알고리즘이 환경의 변화를 실시간으로 처리하는 데 한계를 보일 수 있다는 점을 반영합니다.
.. 그래도 뭐 반복적으로 명령을 내려주면 해결되니까 좋았쓰!
A* Algorithm in Java
import java.util.*;
class Node implements Comparable<Node> {
public int x, y, g, h;
public Node parent;
public Node(int x, int y, int g, int h, Node parent) {
this.x = x;
this.y = y;
this.g = g;
this.h = h;
this.parent = parent;
}
public int getF() {
return g + h;
}
@Override
public int compareTo(Node other) {
return Integer.compare(this.getF(), other.getF());
}
}
public class AStar {
private static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public static List<Node> findPath(int[][] grid, Node start, Node goal) {
PriorityQueue<Node> openList = new PriorityQueue<>();
Set<Node> closedList = new HashSet<>();
openList.add(start);
while (!openList.isEmpty()) {
Node current = openList.poll();
if (current.x == goal.x && current.y == goal.y) {
return constructPath(current);
}
closedList.add(current);
for (int[] direction : DIRECTIONS) {
int newX = current.x + direction[0];
int newY = current.y + direction[1];
if (isValid(grid, newX, newY) && !isInClosedList(closedList, newX, newY)) {
int newG = current.g + 1;
int newH = Math.abs(goal.x - newX) + Math.abs(goal.y - newY); // Manhattan distance
Node neighbor = new Node(newX, newY, newG, newH, current);
openList.add(neighbor);
}
}
}
return Collections.emptyList(); // 경로가 없는 경우
}
private static List<Node> constructPath(Node node) {
List<Node> path = new ArrayList<>();
while (node != null) {
path.add(node);
node = node.parent;
}
Collections.reverse(path);
return path;
}
private static boolean isValid(int[][] grid, int x, int y) {
return x >= 0 && x < grid.length && y >= 0 && y < grid[0].length && grid[x][y] == 0;
}
private static boolean isInClosedList(Set<Node> closedList, int x, int y) {
return closedList.stream().anyMatch(node -> node.x == x && node.y == y);
}
public static void main(String[] args) {
int[][] grid = {
{0, 0, 0, 0},
{1, 1, 0, 1},
{0, 0, 0, 0},
{0, 1, 1, 0},
{0, 0, 0, 0}
};
Node start = new Node(0, 0, 0, 0, null);
Node goal = new Node(4, 3, 0, 0, null);
List<Node> path = findPath(grid, start, goal);
path.forEach(node -> System.out.println("Node: (" + node.x + ", " + node.y + ")"));
}
}
여담
사실 스타크래프트 말고 리그오브레전드의 길찾기 알고리즘에 대해서 좀 알아보고 싶었으나.. 관련된 자료를 찾을 수 없었습니다. 심지어 롤 계정은 4년 전에 영구 탈퇴를 한 상황이라 인게임에서 확인도 못해보고. 아무튼 오늘 이야기는 여기까지..
'Computer Science > Algorithm' 카테고리의 다른 글
| [자료구조] C언어로 하노이 탑 만들기 (5) | 2019.10.12 |
|---|