简单解释 A* 搜索
A* 是一种流行的基于启发式的搜索算法，用于从起始节点找到目标节点的最短路径。它结合了 Dijkstra 算法和贪婪最佳优先搜索的优点，同时考虑到到达节点的成本和到目标的估计成本。
想象一下，你正在使用地图从家到咖啡店。有很多可能的道路可以选择，但你想要最短或最快的那条。
A* 搜索的工作原理如下：
- 它从你当前的位置开始。
- 它查看你可以去的所有下一个地方。
- 对于每条可能的路线，它计算：
- 你已经走过的距离（称为“到目前为止的成本”）。
- 它认为到目标的距离（这是一个估计值，称为“启发式”）。
- 它将这两个数字相加，以决定哪条路线看起来最有希望。
- 它不断重复这个过程——总是选择得分最低的路径——直到到达目标。
因此，A* 就像一个聪明的旅行者，不仅关注他们已经走过的地方，还试图猜测哪条未来的路径看起来最短，并在途中不断调整。
算法
该算法使用以下公式来评估节点：
\[f(n) = g(n) + h(n)\]其中：
g(n)：从起始节点到当前节点n的成本。h(n)：从节点n到目标的启发式估计成本。f(n)：通过节点n的路径的总估计成本。
本质上，该算法通过结合到目前为止的成本（g(n)）和从当前节点到最终目的地的成本（h(n)）来选择最低成本的路径。h(n) 是通过两个节点之间的曼哈顿距离计算的。
\[h(n) = |x1 - x2| + |y1 - y2|\]其中：
- ( (x1, y1) ) 是第一个节点的坐标。
- ( (x2, y2) ) 是第二个节点的坐标。
- ( h(n) ) 是表示曼哈顿距离的启发式值。
这保证了 A* 的以下特性：
- 最优性：如果启发式函数
h(n)是可接受的（从不高估成本），A* 保证找到最短路径。 - 完备性：如果存在解决方案，A* 总能找到。
- 启发式函数：
h(n)的选择显著影响算法的性能。
A* 实现步骤：
- 从初始节点 A1 开始。
- 查看其邻居。
- 对于每个邻居：
- 计算 g(n) = g(当前) + 1
- 计算 h(n) = 到目标的曼哈顿距离
- 计算 f(n) = g(n) + h(n)
- 将邻居添加到“开放集”（一个优先级列表，用于决定下一个探索的地方）。
- 从开放集中选择 f(n) 最小的节点。
- 重复，直到到达目标。
A* 的逐步执行
假设我们有以下设置，其中 S 是起点，G 是目标，# 是障碍物。我们希望使用 A* 找到从 S 到 G 的最短路径。
S . . . .
# # . # .
. . . # .
. # # # .
. . . . G
其中：
- S = 起点
- G = 目标
#= 墙（不可通过）- . = 开放路径
步骤 1：从 ( S = (0, 0) ) 开始
- ( g(S) = 0 )
-
( h(S) = 0 - 4 + 0 - 4 = 8 ) - ( f(S) = g(S) + h(S) = 0 + 8 = 8 )
前沿: ( [(0, 0)] )
已访问: ( \emptyset )
步骤 2：扩展 ( (0, 0) )
- ( (0, 0) ) 的邻居：( (0, 1) )（开放），( (1, 0) )（墙，跳过）。
- 对于 ( (0, 1) ):
- ( g(0, 1) = g(0, 0) + 1 = 1 )
-
( h(0, 1) = 0 - 4 + 1 - 4 = 7 ) - ( f(0, 1) = g(0, 1) + h(0, 1) = 1 + 7 = 8 )
前沿: ( [(0, 1)] )
已访问: ( [(0, 0)] )
步骤 3：扩展 ( (0, 1) )
- ( (0, 1) ) 的邻居：( (0, 2) )（开放），( (1, 1) )（墙，跳过），( (0, 0) )（已访问，跳过）。
- 对于 ( (0, 2) ):
- ( g(0, 2) = g(0, 1) + 1 = 2 )
-
( h(0, 2) = 0 - 4 + 2 - 4 = 6 ) - ( f(0, 2) = g(0, 2) + h(0, 2) = 2 + 6 = 8 )
前沿: ( [(0, 2)] )
已访问: ( [(0, 0), (0, 1)] )
步骤 4：扩展 ( (0, 2) )
- ( (0, 2) ) 的邻居：( (0, 3) )（开放），( (1, 2) )（开放），( (0, 1) )（已访问，跳过）。
- 对于 ( (0, 3) ):
- ( g(0, 3) = g(0, 2) + 1 = 3 )
-
( h(0, 3) = 0 - 4 + 3 - 4 = 5 ) - ( f(0, 3) = g(0, 3) + h(0, 3) = 3 + 5 = 8 )
- 对于 ( (1, 2) ):
- ( g(1, 2) = g(0, 2) + 1 = 3 )
-
( h(1, 2) = 1 - 4 + 2 - 4 = 5 ) - ( f(1, 2) = g(1, 2) + h(1, 2) = 3 + 5 = 8 )
前沿: ( [(0, 3), (1, 2)] )
已访问: ( [(0, 0), (0, 1), (0, 2)] )
（后续步骤省略，逻辑类似）
最终路径：
从 ( S ) 到 ( G ) 的最短路径为：
(0, 0) → (0, 1) → (0, 2) → (0, 3) → (0, 4) → (1, 4) → (2, 4) → (3, 4) → (4, 4)
Javascript 示例实现
你可以在这里尝试在线演示：在线 A* 演示
可以自由更改起点、目标、网格大小，甚至定义自己的障碍物！
export function AStar(
start: [number, number],
end: [number, number],
obstacles: Set<string>,
terrain: number[][]
): { path: number[][]; visited: number[][] } {
const openSet = new Set<string>();
const cameFrom: { [key: string]: [number, number] } = {};
const gScore: { [key: string]: number } = {};
const fScore: { [key: string]: number } = {};
const allVisitedNodes: number[][] = [];
const getKey = (x: number, y: number) => `${x},${y}`;
// 初始化起始节点
const startKey = getKey(start[0], start[1]);
openSet.add(startKey);
gScore[startKey] = 0;
fScore[startKey] = heuristic(start, end);
allVisitedNodes.push(start.slice());
while (openSet.size > 0) {
const current = getLowestFScore(openSet, fScore);
const currentKey = getKey(current[0], current[1]);
if (current[0] === end[0] && current[1] === end[1]) {
return { path: reconstructPath(cameFrom, current), visited: allVisitedNodes };
}
openSet.delete(currentKey);
const neighbors = getNeighbors(current, terrain);
for (const neighbor of neighbors) {
const neighborKey = getKey(neighbor[0], neighbor[1]);
if (obstacles.has(neighborKey)) continue;
const tentativeGScore = (gScore[currentKey] || 0) + getDistance(current, neighbor, terrain);
if (!gScore[neighborKey] || tentativeGScore < (gScore[neighborKey] || Infinity)) {
cameFrom[neighborKey] = current;
gScore[neighborKey] = tentativeGScore;
fScore[neighborKey] = tentativeGScore + heuristic(neighbor, end);
if (!openSet.has(neighborKey)) {
openSet.add(neighborKey);
allVisitedNodes.push(neighbor.slice());
}
}
}
}
return { path: [], visited: allVisitedNodes };
}