我正在尝试在 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 得分 = G 得分 + H 得分，其中 G 得分是从开始到当前节点（我们要从开放集合中选择的节点）的当前路径的成本，H 得分是从当前节点（我们要选择的节点）到结束节点的成本，假设我们为启发式选择了曼哈顿距离。）
然后，检查我们刚刚选择的节点（当前节点）的所有邻居。
如果它已经在封闭集中，跳过它。如果不是，检查它是否在开放集中。如果不是，则为此邻居计算 F 分数，其中 G 分数现在是当前节点的 G 分数 + 从当前到邻居的 G 分数。这就是我提供的代码中所谓的 tentative_gScore。H 分数更改为从邻居到结束节点计算的值。
这里是问题：
什么是 gScore [neighbor]?它在哪里计算?它的价值是什么?Tentative_gScore 我明白,但我们从哪里得到一个邻居的 gScore,以便我们可以测试条件:
else if tentative_gScore >= gScore[neighbor]
continue // This is not a better path.
好的，我知道了。
如果第一次找到邻居，您甚至不比较 g 分数，只需将其添加到开放集中即可。
如果邻居已经在开放集中（这也意味着它有某种 g 分数）：gScore [neighbor] 是先前找到的邻居的 g 分数，该邻居已添加到开放集中。如果再次找到该邻居，则可以比较 g 分数（新的 g 分数与旧的 g 分数（以前找到的））。如果新分数更好（即更低），则相应地更改分数和父节点。
就这么简单。:)
本站系公益性非盈利分享网址，本文来自用户投稿，不代表边看边学立场，如若转载，请注明出处
评论列表（23条）