Java A* 搜索算法详解：步步寻路，高效抵达122

A* 搜索算法是一种启发式搜索算法，广泛应用于路径规划和优化问题。它结合了贪心搜索和启发式函数的力量，在探索搜索空间时做出更明智的决策，从而提高搜索效率。

Java 中的 A* 算法实现

在 Java 中实现 A* 算法需要以下步骤：
定义问题：确定起点、终点和遍历环境（例如，网格、图）。
初始化优先级队列：使用优先级队列存储节点，优先级由代价函数（f(n) = g(n) + h(n))决定，其中 g(n) 是从起点到当前节点的实际代价，h(n) 是从当前节点到终点的估计代价。
拓展当前节点：从当前节点生成相邻节点，并计算它们的代价和启发式值。
更新优先级队列：将新生成的节点添加到优先级队列，并更新其代价和启发式值，如果存在更优路径。
重复步骤 3 和 4，直至达到终点：每次从优先级队列中弹出具有最低代价的节点，作为新的当前节点，并重复拓展和更新过程，直到找到通往终点的路径。

示例代码
import .*;
public class AStar {
// 节点类
static class Node {
int x, y;
double g, h, f;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
// 计算从给定节点到目标节点的启发式代价
public double heuristic(Node goal) {
return ((x - goal.x) * (x - goal.x) + (y - goal.y) * (y - goal.y));
}
}
// A* 算法
public static List aStar(Node start, Node goal, Map graph) {
// 优先级队列
PriorityQueue openSet = new PriorityQueue((a, b) -> (int) (a.f - b.f));
// 闭集
Set closedSet = new HashSet();
// 初始化
start.g = 0;
start.h = (goal);
start.f = start.g + start.h;
(start);
while (!()) {
Node current = ();
if (current == goal) {
return reconstructPath(current);
}
(current);
// 获取当前节点的相邻节点
List neighbors = (current, new ArrayList());
for (Node neighbor : neighbors) {
if ((neighbor)) {
continue;
}
double tentativeG = current.g + 1; // 假设移动代价为 1
if (tentativeG < neighbor.g || !(neighbor)) {
neighbor.g = tentativeG;
neighbor.h = (goal);
neighbor.f = neighbor.g + neighbor.h;
(neighbor);
}
}
}
return null; // 未找到路径
}
// 重建路径
public static List reconstructPath(Node node) {
List path = new ArrayList();
while (node != null) {
(node);
node = ;
}
(path);
return path;
}
// 测试示例
public static void main(String[] args) {
// 定义网格环境
Map graph = new HashMap();
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
Node node = new Node(i, j);
(node, new ArrayList());
if (i < 9) {
(node).add(new Node(i + 1, j));
}
if (j < 9) {
(node).add(new Node(i, j + 1));
}
}
}
// 查找起点和终点
Node start = new Node(0, 0);
Node goal = new Node(9, 9);
// 执行 A* 搜索
List path = aStar(start, goal, graph);
// 打印路径
if (path != null) {
for (Node node : path) {
("(" + node.x + ", " + node.y + ")");
}
} else {
("未找到路径。");
}
}
}