a-star - Astar 可以多次访问节点吗？

Question

我一直在阅读维基百科的 Astar article .在他们的实现中，他们检查每个节点是否在 closed 中。设置，如果是这样，他们会跳过它。如果启发式是可以接受的，但 是否可能？不是 一致，我们可能需要重新访问一个节点两次(或更多)以改进它 f值(value)？
这是相关代码

for each neighbor in neighbor_nodes(current)
    if neighbor in closedset //This if condition bothers me
        continue
    tentative_g_score := g_score[current] + dist_between(current,neighbor)
    if neighbor not in openset or tentative_g_score < g_score[neighbor] 
        came_from[neighbor] := current 
        g_score[neighbor] := tentative_g_score
        f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal)
        if neighbor not in openset
            add neighbor to openset

Answer 1

您问题的答案位于链接页面上的伪代码下方，以及该页面的“说明”部分。从伪代码下面的注释:

Remark: the above pseudocode assumes that the heuristic function is monotonic (or consistent, see below), which is a frequent case in many practical problems, such as the Shortest Distance Path in road networks. However, if the assumption is not true, nodes in the closed set may be rediscovered and their cost improved. In other words, the closed set can be omitted (yielding a tree search algorithm) if a solution is guaranteed to exist, or if the algorithm is adapted so that new nodes are added to the open set only if they have a lower f value than at any previous iteration.

所以是的，伪代码确实假设启发式是一致的，如果不是，则必须进行修改。