
什麼是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 中刪除 min。決定鄰居最小值(如果考慮對角線,則最多 8 個)3d。檢查每個鄰居:a)如果鄰居是目標小區,則停止搜尋b)如果不是,則為其計算G、H。G = min.G + 鄰居與 min 之間的距離 F = G + H c) 如果與鄰居位置相同的節點在開放列表中且其 F 小於鄰居的 F,則跳過該鄰居 d) 如果與鄰居位置相同的節點在關閉清單中,且其f小於鄰居的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