java - 为 A* 搜索计算 f_score[neighbor]

Question

我正在查看维基百科上的 A 星伪代码 ( wikipedia:A*_search_algorithm )，我对这段代码有疑问:

for each neighbor in neighbor_nodes(current)
    tentative_g_score := g_score[current] + dist_between(current,neighbor)
    tentative_f_score := tentative_g_score + heuristic_cost_estimate(neighbor, goal)
    if neighbor in closedset and tentative_f_score >= f_score[neighbor]
        continue

在 if 语句的第二部分 - tentative_f_score >= f_score[neighbor] - 我想知道计算 f_score[neighbor] 与计算 有何不同code>tentative_f_score.

基本上，我将如何计算 f_score[neighbor]？谢谢。

Answer 1

f_score[neighbor] 是您为所有节点存储的内容。这个邻居是一个你已经有 F 分数的节点，因为它已经在封闭集中。新的 F-score 可能会有所不同，因为您到达该节点的方式与之前到达该节点的方式不同，因此父级将不同于您已经为该节点存储的内容(因此也可能G，因此 F)。

基本上那里的条件说明了如果不是这种情况(或者如果新的 F 更糟)会发生什么，那么您可以忽略该节点。

它下面的代码处理了找到该节点的新路径比您之前到达它的路径更短的情况，因此它将当前节点设置为其父节点并更新其 G(因此更新 F)。