다양한 검색 알고리즘은 다양한 작업에 맞게 조정됩니다. 오늘은 가장 효과적인 길 찾기 알고리즘 중 하나인 A* 검색에 대해 이야기하겠습니다. 이것은 컴퓨터 게임과 도시 간 길 등 검색 그래프를 만드는 데 매우 적합합니다. 예를 들어 전략적 또는 전술적 비디오 게임에서 버튼을 누른 후 플레이어나 그룹이 지체 없이 즉시 시작하여 필드를 가로질러 지정한 지점으로 이동하는 방법을 알아차렸을 것입니다. 게임은 플레이어가 어떤 곳으로 가야 하는지 정확하게 계산하는 효과적인 알고리즘을 사용하기 때문에 지연이 없습니다. 또는 플레이어를 틀림없이 발견하고 멀리서 올바른 방향으로 걷기 시작하는 적. 일반적으로 이러한 작업에는 A* 알고리즘이 사용됩니다.
A* 알고리즘이란?
길 찾기 알고리즘 A*는 최선 우선 검색 알고리즘의 예입니다. A* 알고리즘의 목적은 한 지점에서 다른 지점으로의 경로를 찾는 것입니다. 이는 그래프 알고리즘 검색의 고전 중 하나입니다. 예제를 사용하여 어떻게 작동하는지 알아 보겠습니다. 하향식 보기가 가능한 2D 게임을 상상해 보세요. 게임 영역을 체스판처럼 8*8 셀과 같이 정사각형 탐욕으로 나누어 보겠습니다. 우리 세포는 통과할 수 있거나 통과할 수 없는(장애물) 두 가지 유형 중 하나일 수 있습니다. 플레이어 또는 플레이어에게 접근하는 적군이 한 칸씩 이동하는 기간입니다. 게임에서 통과 가능한 셀은 평탄한 도로, 잔디 또는 모래와 같이 다른 성격을 가질 수 있으며 이에 따라 이동의 어려움이 결정되지만 단순화를 위해 모든 통과 가능한 셀이 동일한 방식으로 통과된다고 가정하겠습니다. 아래 그림에서 파란색 셀은 장애물입니다.
한 셀(또는 노드)을 시작 셀(문자가 들어 있는 셀)로 할당하고 다른 셀을 대상 또는 목표 셀(플래그가 있는 셀)로 할당하고 이 경우 A* 알고리즘이 어떻게 작동하는지 설명하겠습니다. 문자는 셀 (1,1)에 있고 대상은 셀 (7,7)에 있습니다. 각 셀에는 수평, 수직 및 대각선 이웃이 있습니다. 대각선 노드를 계산하는지 여부는 게임에 따라 다릅니다. 예를 들어 Bomberman이나 Pacman과 같은 많은 하향식 뷰 게임에서 캐릭터는 수평 또는 수직으로만 이동할 수 있습니다. 이 경우 가장자리에 닿는 것을 제외하고 모든 노드에는 4개의 이웃만 있습니다. 캐릭터가 대각선으로 이동할 수 있는 게임의 경우 각 노드에는 최대 8개의 이웃이 있을 수 있습니다. 알고리즘의 첫 번째 단계에서 캐릭터가 위치한 셀에는 두 개의 이웃이 있습니다. 더 정확하게는 3개인데 그 중 하나가 장애물이다. 
대각선 길이가 더 긴 것은 분명합니다. 셀의 측면을 조건부로 1과 동일하게 설정하면 이 셀의 대각선 길이는 2의 제곱근과 같습니다. 이것이 피타고라스의 정리가 말하는 것입니다. 셀 A에서 셀 B로 이동하려면 먼저 인접한 셀 중 하나를 선택한 후 다음 셀을 선택해야 합니다. 또한 그 과정에서 초기 셀에서 대상 셀로 이동하는 것이 가능한지 이해합니다. 각 단계의 A* 알고리즘은 함수 F의 값에 따라 인접 셀 중 하나를 선택합니다. 이 함수는 후보 셀이 최단 경로에 얼마나 좋은지 측정합니다. 이것이 비용 함수이고, 이동 함수 G와 휴리스틱 함수의 합이다.
-
G 비용 — 시작 노드로부터의 거리입니다.
-
H 비용(휴리스틱)은 끝(목표) 노드로부터의 거리입니다. 이 기능은 다를 수 있으며 개발자가 더 나은 기능을 결정합니다. 아마도 H의 선택은 A*에서 가장 중요하며, 이것이 알고리즘의 특정 구현을 다소 효과적으로 만드는 지점입니다. 이론적으로는 원하는 기능을 모두 사용할 수 있습니다.
우리의 경우에는 대상 셀의 위치를 알고 있으며 예를 들어 대상 셀과 현재 셀 사이의 기하학적 유클리드 거리를 계산할 수 있습니다. 거리가 짧을수록 목표에 더 가까워집니다.
-
F 비용 = G + H. 따라서 알고리즘은 모든 이웃 노드 F 비용을 계산하고 가장 낮은 F 비용 중 하나를 먼저 선택합니다. 하나를 선택하면 이를 닫힌 것으로 표시하고 이 노드 이웃에 대한 값을 계산합니다.
휴리스틱 함수 H를 어떻게 계산할 수 있나요?
이는 휴리스틱 기능입니다. 이름 자체는 경험에 의해 결정되며 다를 수 있음을 의미합니다. 여기서는 점 (x1, y1)과 (x2, y2) 사이의 소위 유클리드 거리와 동일하다고 가정합니다.
그림에서 첫 번째 단계에는 두 가지 옵션이 있으며 비용은 동일합니다. 하지만 다음 단계에서 캐릭터는 옵션 중 하나에서 막다른 골목에 빠지게 됩니다. 그러므로 우리는 다른 방향으로 가고 있습니다. 다음 반복에서는 이미 4가지 옵션이 있습니다. 
그 중 두 개는 뒤로 가기 때문에 적합하지 않고, 다른 옵션도 똑같이 좋지만 알고리즘은 대각선으로 셀(3,2)로 가는 것이 가장 좋다고 결정했습니다. 또한 각 단계에서 문자가 대상 셀에 도달할 때까지 함수 F의 계산이 반복됩니다. 물론 그런 구절이 존재한다면 말이다. 
GIF 그림의 녹색 길은 캐릭터가 깃발에 도달하는 최적의 경로를 나타냅니다.
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);
}
}
경로: -> (0,0) -> (1,0) -> (2,1) -> (3,1) -> (4,1) -> (5,2) -> (5, 3) -> (6,4) -> (6,5) -> (6,6)
이는 두 지점 사이에 구축할 수 있는 여러 최단 경로 중 하나임을 알 수 있습니다. 그림의 예와 프로그램 출력의 여섯 번째 단계는 경로가 동일하게 효과적임이 밝혀졌지만 서로 다릅니다. 프로그램은 가장 효과적인 여러 옵션 중 하나를 선택합니다.
GO TO FULL VERSION