
A* 알고리즘이란?
길 찾기 알고리즘 A*는 최선 우선 검색 알고리즘의 예입니다. A* 알고리즘의 목적은 한 지점에서 다른 지점으로의 경로를 찾는 것입니다. 이는 그래프 알고리즘 검색의 고전 중 하나입니다. 예제를 사용하여 어떻게 작동하는지 알아 보겠습니다. 하향식 보기가 가능한 2D 게임을 상상해 보세요. 게임 영역을 체스판처럼 8*8 셀과 같이 정사각형 탐욕으로 나누어 보겠습니다. 우리 세포는 통과할 수 있거나 통과할 수 없는(장애물) 두 가지 유형 중 하나일 수 있습니다. 플레이어 또는 플레이어에게 접근하는 적군이 한 칸씩 이동하는 기간입니다. 게임에서 통과 가능한 셀은 평탄한 도로, 잔디 또는 모래와 같이 다른 성격을 가질 수 있으며 이에 따라 이동의 어려움이 결정되지만 단순화를 위해 모든 통과 가능한 셀이 동일한 방식으로 통과된다고 가정하겠습니다. 아래 그림에서 파란색 셀은 장애물입니다.

-
G 비용 — 시작 노드로부터의 거리입니다.
-
H 비용(휴리스틱)은 끝(목표) 노드로부터의 거리입니다. 이 기능은 다를 수 있으며 개발자가 더 나은 기능을 결정합니다. 아마도 H의 선택은 A*에서 가장 중요하며, 이것이 알고리즘의 특정 구현을 다소 효과적으로 만드는 지점입니다. 이론적으로는 원하는 기능을 모두 사용할 수 있습니다.
우리의 경우에는 대상 셀의 위치를 알고 있으며 예를 들어 대상 셀과 현재 셀 사이의 기하학적 유클리드 거리를 계산할 수 있습니다. 거리가 짧을수록 목표에 더 가까워집니다.
-
F 비용 = G + H. 따라서 알고리즘은 모든 이웃 노드 F 비용을 계산하고 가장 낮은 F 비용 중 하나를 먼저 선택합니다. 하나를 선택하면 이를 닫힌 것으로 표시하고 이 노드 이웃에 대한 값을 계산합니다.
휴리스틱 함수 H를 어떻게 계산할 수 있나요?
이는 휴리스틱 기능입니다. 이름 자체는 경험에 의해 결정되며 다를 수 있음을 의미합니다. 여기서는 점 (x1, y1)과 (x2, y2) 사이의 소위 유클리드 거리와 동일하다고 가정합니다.



A* 알고리즘 단계별
Java에서 알고리즘을 구현하려면 다음 단계를 수행해야 합니다. 1. 먼저 열린 노드와 닫힌 노드에 대한 두 개의 목록을 만들어야 합니다. 2. 두 목록을 모두 초기화합니다. 닫힌 목록에서 시작 노드는 열린 목록을 가리킵니다. 3. 열려 있는 목록에 요소가 있는 동안: 3a. 가장 작은 F 3b를 갖는 노드 최소값을 찾습니다. 열린 목록에서 min을 제거합니다. 3c. 최소 이웃을 결정합니다(대각선을 고려하는 경우 최대 8개). 3d. 각 이웃 확인: a) 이웃이 대상 셀이면 검색을 중지합니다. b) 그렇지 않으면 이에 대해 G, H를 계산합니다. G = min.G + 이웃과 최소 사이의 거리 F = G + H c) 이웃과 동일한 위치를 가진 노드가 공개 목록에 있고 그 F가 이웃의 F보다 작으면 해당 이웃을 건너뜁니다. d) 다음 경우 이웃과 동일한 위치를 가진 노드가 닫힌 목록에 있고 f가 이웃의 노드보다 작으면 해당 이웃을 건너뜁니다. 그렇지 않으면 노드를 열린 목록에 추가합니다. 내부 루프의 끝 3e. 닫힌 목록에 min 추가 외부 루프의 끝 따라서 각 반복에서 다음 작업을 수행합니다.- 열린 목록에서 예상 총점이 가장 낮은 셀을 선택하세요.
- 열린 목록에서 이 셀을 제거하십시오.
- 열려 있는 목록에 접근할 수 있는 모든 셀을 추가합니다.
- 이 작업을 수행할 때 해당 노드의 새 점수를 각 새 노드로 처리하여 지금까지의 성능이 개선되었는지 확인하고, 개선된 경우 해당 셀에 대해 알고 있는 내용을 업데이트합니다.
A* 의사코드
다음은 A* 길찾기에 대한 간략한 의사코드입니다.Input: a grid with locked and empty cells, with start and goal cell.
Output: least cost path from start to goal cell.
Initialisation
openList = {startCell} //list of traversed cells
closedList = {} //list of already traversed cells
g.startCell = 0 //cost from source cell to a cell
h.startCell = h(startCell, goal) //heuristic
f.startCell = g.startCell + h.StartCell
while openList is not empty
do
//let the currentCell equal the cell with the least f value
currentCell = Cell on top of openList, with least f
if currentCell == end return
remove currentCell from openList
add currentCell to closedList
foreach n in child.currentCell
if n in closedList
continue
cost = g.currentCell + distance(currentCell,n)
if (n in openList and cost < g.n)
remove n from closedList
g.n = cost
h.n = h(n, goal)
f.n = g.n + h.n
의사코드에서 Java의 A* 구현까지
A* Java 구현의 길 찾기에는 알고리즘을 제공하는 몇 가지 방법이 있어야 합니다.- 셀(Cell), 필요한 매개변수를 보유하는 구조체
- 열린 목록과 닫힌 목록
- 휴리스틱 함수 계산 방법
- 출발지에서 목적지까지의 경로를 추적하는 방법
- 해당 셀이 차단되었는지, 이미 도달했는지, 유효한지 등을 확인하는 방법
package Asterist;
import java.util.PriorityQueue;
import java.util.Stack;
public class AAsterisk {
//Java Program to implement A* Search Algorithm
//Here we're creating a shortcut for (int, int) pair
public static class Pair {
int first;
int second;
public Pair(int first, int second){
this.first = first;
this.second = second;
}
@Override
public boolean equals(Object obj) {
return obj instanceof Pair && this.first == ((Pair)obj).first && this.second == ((Pair)obj).second;
}
}
// Creating a shortcut for tuple<int, int, int> type
public static class Details {
double value;
int i;
int j;
public Details(double value, int i, int j) {
this.value = value;
this.i = i;
this.j = j;
}
}
// a Cell (node) structure
public static class Cell {
public Pair parent;
// f = g + h, where h is heuristic
public double f, g, h;
Cell()
{
parent = new Pair(-1, -1);
f = -1;
g = -1;
h = -1;
}
public Cell(Pair parent, double f, double g, double h) {
this.parent = parent;
this.f = f;
this.g = g;
this.h = h;
}
}
// method to check if our cell (row, col) is valid
boolean isValid(int[][] grid, int rows, int cols,
Pair point)
{
if (rows > 0 && cols > 0)
return (point.first >= 0) && (point.first < rows)
&& (point.second >= 0)
&& (point.second < cols);
return false;
}
//is the cell blocked?
boolean isUnBlocked(int[][] grid, int rows, int cols,
Pair point)
{
return isValid(grid, rows, cols, point)
&& grid[point.first][point.second] == 1;
}
//Method to check if destination cell has been already reached
boolean isDestination(Pair position, Pair dest)
{
return position == dest || position.equals(dest);
}
// Method to calculate heuristic function
double calculateHValue(Pair src, Pair dest)
{
return Math.sqrt(Math.pow((src.first - dest.first), 2.0) + Math.pow((src.second - dest.second), 2.0));
}
// Method for tracking the path from source to destination
void tracePath(
Cell[][] cellDetails,
int cols,
int rows,
Pair dest)
{ //A* Search algorithm path
System.out.println("The Path: ");
Stack<Pair> path = new Stack<>();
int row = dest.first;
int col = dest.second;
Pair nextNode = cellDetails[row][col].parent;
do {
path.push(new Pair(row, col));
nextNode = cellDetails[row][col].parent;
row = nextNode.first;
col = nextNode.second;
} while (cellDetails[row][col].parent != nextNode); // until src
while (!path.empty()) {
Pair p = path.peek();
path.pop();
System.out.println("-> (" + p.first + "," + p.second + ") ");
}
}
// A main method, A* Search algorithm to find the shortest path
void aStarSearch(int[][] grid,
int rows,
int cols,
Pair src,
Pair dest)
{
if (!isValid(grid, rows, cols, src)) {
System.out.println("Source is invalid...");
return;
}
if (!isValid(grid, rows, cols, dest)) {
System.out.println("Destination is invalid...");
return;
}
if (!isUnBlocked(grid, rows, cols, src)
|| !isUnBlocked(grid, rows, cols, dest)) {
System.out.println("Source or destination is blocked...");
return;
}
if (isDestination(src, dest)) {
System.out.println("We're already (t)here...");
return;
}
boolean[][] closedList = new boolean[rows][cols];//our closed list
Cell[][] cellDetails = new Cell[rows][cols];
int i, j;
// Initialising of the starting cell
i = src.first;
j = src.second;
cellDetails[i][j] = new Cell();
cellDetails[i][j].f = 0.0;
cellDetails[i][j].g = 0.0;
cellDetails[i][j].h = 0.0;
cellDetails[i][j].parent = new Pair( i, j );
// Creating an open list
PriorityQueue<Details> openList = new PriorityQueue<>((o1, o2) -> (int) Math.round(o1.value - o2.value));
// Put the starting cell on the open list, set f.startCell = 0
openList.add(new Details(0.0, i, j));
while (!openList.isEmpty()) {
Details p = openList.peek();
// Add to the closed list
i = p.i; // second element of tuple
j = p.j; // third element of tuple
// Remove from the open list
openList.poll();
closedList[i][j] = true;
// Generating all the 8 neighbors of the cell
for (int addX = -1; addX <= 1; addX++) {
for (int addY = -1; addY <= 1; addY++) {
Pair neighbour = new Pair(i + addX, j + addY);
if (isValid(grid, rows, cols, neighbour)) {
if(cellDetails[neighbour.first] == null){ cellDetails[neighbour.first] = new Cell[cols]; }
if (cellDetails[neighbour.first][neighbour.second] == null) {
cellDetails[neighbour.first][neighbour.second] = new Cell();
}
if (isDestination(neighbour, dest)) {
cellDetails[neighbour.first][neighbour.second].parent = new Pair ( i, j );
System.out.println("The destination cell is found");
tracePath(cellDetails, rows, cols, dest);
return;
}
else if (!closedList[neighbour.first][neighbour.second]
&& isUnBlocked(grid, rows, cols, neighbour)) {
double gNew, hNew, fNew;
gNew = cellDetails[i][j].g + 1.0;
hNew = calculateHValue(neighbour, dest);
fNew = gNew + hNew;
if (cellDetails[neighbour.first][neighbour.second].f == -1
|| cellDetails[neighbour.first][neighbour.second].f > fNew) {
openList.add(new Details(fNew, neighbour.first, neighbour.second));
// Update the details of this
// cell
cellDetails[neighbour.first][neighbour.second].g = gNew;
//heuristic function cellDetails[neighbour.first][neighbour.second].h = hNew;
cellDetails[neighbour.first][neighbour.second].f = fNew;
cellDetails[neighbour.first][neighbour.second].parent = new Pair( i, j );
}
}
}
}
}
}
System.out.println("Failed to find the Destination Cell");
}
// test
public static void main(String[] args) {
//0: The cell is blocked
// 1: The cell is not blocked
int[][] grid = {
{ 1, 1, 0, 0, 1, 0, 0, 0 },
{ 1, 0, 0, 1, 1, 0, 1, 0 },
{ 1, 1, 0, 1, 0, 0, 1, 0 },
{ 1, 1, 0, 1, 1, 1, 1, 1 },
{ 1, 1, 0, 0, 0, 1, 1, 1 },
{ 0, 1, 1, 1, 0, 1, 1, 0 },
{ 1, 1, 0, 1, 1, 1, 1, 0 },
{ 0, 1, 1, 1, 1, 1, 1, 1 }
};
// Start is the left-most upper-most corner
Pair src = new Pair(0,0);
//(8, 0);
// Destination is the right-most bottom-most corner
Pair dest = new Pair(6, 6);
AAsterisk app = new AAsterisk();
app.aStarSearch(grid, grid.length , grid[0].length, src, dest);
}
}
여기 예에서는 위 그림과 동일한 그리드가 있습니다. 2D 배열로 "그리기"만 하면 됩니다. 프로그램은 다음 경로를 출력합니다.
경로: -> (0,0) -> (1,0) -> (2,1) -> (3,1) -> (4,1) -> (5,2) -> (5, 3) -> (6,4) -> (6,5) -> (6,6)
이는 두 지점 사이에 구축할 수 있는 여러 최단 경로 중 하나임을 알 수 있습니다. 그림의 예와 프로그램 출력의 여섯 번째 단계는 경로가 동일하게 효과적임이 밝혀졌지만 서로 다릅니다. 프로그램은 가장 효과적인 여러 옵션 중 하나를 선택합니다.
GO TO FULL VERSION