我正在尝试用 Java 实现 A* 算法，但我不确定我是否正确理解 f/g/h 分数。我正在帮助自己pseudocode of A* on Wikipedia 。这是一些伪代码:
while openSet is not empty
current := the node in openSet having the lowest fScore[] value
if current = goal
return reconstruct_path(cameFrom, current)
openSet.Remove(current)
closedSet.Add(current)
for each neighbor of current
if neighbor in closedSet
continue // Ignore the neighbor which is already evaluated.
// The distance from start to a neighbor
tentative_gScore := gScore[current] + dist_between(current, neighbor)
if neighbor not in openSet // Discover a new node
openSet.Add(neighbor)
else if tentative_gScore >= gScore[neighbor]
continue // This is not a better path.
// This path is the best until now. Record it!
cameFrom[neighbor] := current
gScore[neighbor] := tentative_gScore
fScore[neighbor] := gScore[neighbor] + heuristic_cost_estimate(neighbor, goal)
return failure
我不明白的是这部分:
else if tentative_gScore >= gScore[neighbor]
continue // This is not a better path.
邻居怎么已经有G分数了？我是这样解释算法的:
从开放集中选取 F 分数最低的节点。 (F Score = G Score + H Score，其中 G Score 是当前路径从起点到当前节点(我们要从开放集中选取的节点)的成本，H Score 是从当前节点开始的成本(我们要选择的那个)到结束节点，假设我们选择曼哈顿距离作为启发式。)
然后，检查我们刚刚选取的节点(当前节点)的所有邻居。
如果它已经在闭集中，则跳过它。如果不是，检查它是否在开集中。如果不是，则计算该邻居的 F 分数，其中 G 分数现在是当前节点的 G 分数 + 从当前节点到邻居的 G 分数。这就是我提供的代码中所谓的 tentative_gScore 。 H 分数更改为从邻居节点到末端节点计算的值。
问题是:
gScore[邻居]是什么？是在哪里计算的呢？它的值(value)是什么？ Tentative_gScore 我明白了，但是我们从哪里获取邻居的 gScore 以便我们可以测试条件:
else if tentative_gScore >= gScore[neighbor]
continue // This is not a better path.
最佳答案
好的，我明白了。
如果第一次找到邻居，您甚至不比较 g 分数，只需将其添加到开集中即可。
如果邻居已经在开集中(这也意味着它有某种 g 分数): gScore[neighbour] 是先前找到的添加到开放集中的邻居的 g 分数。如果你再次找到这个邻居，你可以比较 g 分数(新的 g 分数与旧的 g 分数(之前找到的))。如果新分数更好(即更低)，则相应地更改分数和父节点。
就这么简单。 :)
关于algorithm - A*(星号)算法: understanding the f/g/h scores，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/42884863/