Astar算法是否可以重复访问节点？

Question

我一直在阅读维基百科上的Astar 文章。在他们的实现中，他们检查每个节点是否在closed集合中，如果是，则跳过它。如果启发式函数是可接受但不连续的，那么我们可能需要多次重新访问一个节点以改进它的f值，这是否有可能呢？ 以下是相关代码：

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

- Shmoopy

Answer 1

链接页面上伪代码下面和描述部分都有你问题的答案。从伪代码下方的注释中可以看出：

备注：上述伪代码假设启发式函数是单调的（或一致的，见下文），这在许多实际问题中是常见的情况，例如道路网络中的最短距离路径。然而，如果这个假设不成立，那么关闭集合中的节点可能会被重新发现并且它们的成本会得到改善。换句话说，如果解决方案保证存在，或者算法被调整为仅当新节点具有比任何先前迭代的f值更低时才将其添加到开放集合中，则可以忽略关闭集合（产生树搜索算法）。

因此，是的，伪代码假定启发式函数是一致的，如果不是，则必须进行修改。

- asm