A* (A star algorithm) 알고리즘이란??
그래프의 한 정점에서 다른 한 정점까지의 최단거리를 각각 구하는 알고리즘
목적지까지의 거리를 계산하는 휴리스틱 추정값을 이용해 다익스트라를 개선한 알고리즘휴리스틱 함수의 성능에 따라 알고리즘 성능이 달라진다.
시간복잡도
O(b^d) (완전 탐색) ~ O(E log V) (최적화 시)
- b는 분기 계수 (한 노드에서 이동할 수 있는 평균 갈래 수)
- d는 최단 경로의 깊이(시작점에서 목표까지의 단계 수)
- E는 그래프의 간선 수, V는 노드 수
공간복잡도
O(b^d) (최악) ~ O(V) (일반적인 경우)
다익스트라와의 차이점
다익스트라
- 출발점에서 모든 노드에 대한 최단거리를 탐색함
- 단순히 현재 지나온 거리가 가장 짧은 노드를 선택해 탐색
A*
- 출발점에서 도착점까지의 최단 거리만 탐색함
- 휴리스틱 함수를 이용해 목표 방향으로 우선 탐색
- 시간복잡도는 비슷하지만, 휴리스틱을 이용해 탐색하는 노드의 수가 더 적어질 수 있어서 속도가 더 빠를 수 있음
추천 상황
| 상황 | 추천 알고리즘 |
| 모든 노드의 최단 거리 필요 | 다익스트라 |
| 목표 지점까지의 최단 거리 필요 | A* |
| 가중치 없는 그래프 | BFS |
| 가중치 있는 그래프 | A* |
구현 방식
아래 사진은 A* 알고리즘의 기본적인 형태이다.출발 지점(초록 사각형), 도착 지점(빨간 사각형)이 있고, 각 노드에는 f, g, h라는 값을 설정해 준다.g는 출발 노드에서 현재 노드 n까지 도달하기 위한 최단 비용h는 현재 노드 n에서 목표 노드(도착지점)까지의 예상 이동 비용, 이를 휴리스틱 알고리즘으로 측정한다.
- 자주 사용되는 휴리스틱 알고리즘은 맨해튼, 유클리드, 체비쇼프 등이 있다.
f는 g와 h를 더한 총비용이다.
- 출발 노드를 열린 목록에 넣는다.
- 열린 목록에서 가장 작은 f 값을 가진 노드를 꺼낸다.
- 해당 노드에서 갈 수 있는 노드의 f, g, h 비용을 계산하여 열린 목록에 넣어준다.
- 해당 노드에서 갈 수 있는 노드가 이미 열린 목록에 있는 경우는 f의 값이 줄어들면 업데이트하고 아니면 그대로 둔다.
- 1 ~ 3을 열린 목록이 빌 때까지 수행한다. 만약 열린 목록이 비었는데 목표지점에 도착하지 못했다면 갈 수 없는 경로인 것이다.
예제
예제 코드
A*
package Path.astar;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
public class Astar {
private AstarNode[][] map;
// N 크기의 map 생성하고 초기화
public void initMap(int N) {
map = new AstarNode[N][N];
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
map[i][j] = new AstarNode(i, j);
}
}
}
/** A* 알고리즘으로 최단경로 찾기
* 열린 목록을 그냥 리스트로 작성했는데 우선순위 큐(최소힙)을 사용하면 성능이 개선된다.
* 도착점을 찾으면 부모 노드를 이용해 경로를 출력한다.
*/
public void findPath(int startX, int startY, int endX, int endY) {
List<AstarNode> openList = new ArrayList<AstarNode>();
map[startX][startY].f = 0;
map[startX][startY].g = 0;
map[startX][startY].h = Heuristic(startX,startY,endX,endY);;
openList.add(map[startX][startY]);
int[] dx = {-1, -1, -1,1,1, 1, 0, 0};
int[] dy = {0, -1, 1, 0, -1, 1, -1, 1};
while(!openList.isEmpty()) {
AstarNode node = getMinNode(openList);
node.close = true;
if(node.x == endX && node.y == endY) {
System.out.println(node.f);
while(true) {
System.out.println(node.x + " " + node.y);
node = node.parent;
if(node == null) {
break;
}
}
return;
}
for(int i = 0; i < dx.length; i++) {
int newX = node.x + dx[i];
int newY = node.y + dy[i];
if(newX >= 0 && newX < map.length && newY >= 0 && newY < map[0].length) {
if(!map[newX][newY].block && !map[newX][newY].close) {
int cost;
if(Math.abs(dx[i]) + Math.abs(dy[i]) == 2) {
cost = 14;
}
else cost = 10;
int g = node.g + cost;
int h = Heuristic(newX,newY,endX,endY);
int f = g+h;
if(f < map[newX][newY].f) {
map[newX][newY].g = g;
map[newX][newY].h = h;
map[newX][newY].f = f;
map[newX][newY].parent = node;
if(!openList.contains(map[newX][newY])) {
openList.add(map[newX][newY]);
}
}
}
}
}
}
System.out.println("no path");
}
// 유클리드 알고리즘
public int Heuristic(int posX, int posY, int endX, int endY) {
return (int) ((Math.sqrt(Math.pow(posX - endX, 2) + Math.pow(posY - endY, 2))));
}
// 열린목록 중에 최소 f 값을 가진 노드를 찾는 함수
public AstarNode getMinNode(List<AstarNode> list) {
int min = Integer.MAX_VALUE;
AstarNode returnNode = null;
for(AstarNode node : list) {
if(node.f < min) {
min = node.f;
returnNode = node;
}
}
list.remove(returnNode);
return returnNode;
}
}
AstarNode
package Path.astar;
public class AstarNode {
int x;
int y;
int f;
int g;
int h;
boolean block;
boolean close;
AstarNode parent;
public AstarNode(int x, int y) {
this.x = x;
this.y = y;
f = Integer.MAX_VALUE;
g = 0;
h = 0;
parent = null;
block = false;
close = false;
}
}
Main
package Path;
import Path.astar.Astar;
public class Main {
public static void main(String[] args) {
int N = 5; // 정사각현 map의 한 변 길이
Astar astar = new Astar();
astar.initMap(N);
astar.findPath(0,0,4,2);
}
}
실행화면
참고
'알고리즘공부 > 알고리즘' 카테고리의 다른 글
| [알고리즘] 벨만포드 (0) | 2025.01.24 |
|---|---|
| [알고리즘] 플로이드 워셜 (0) | 2025.01.24 |
| [알고리즘] 다익스트라 (0) | 2025.01.24 |
| [알고리즘] 정렬 (2) | 2025.01.22 |
| [알고리즘] 최단 경로 찾기 (0) | 2025.01.20 |