重新访问A *算法：是否必须检查打开列表或关闭列表？

Question

我正在研究A *算法，并且对重新访问有些困惑。

当我的教授解释A *时，他说如果我重新访问一个已经在封闭列表中的节点，

我必须检查重新访问的费用与原始费用。

如果重新访问便宜，我应该在封闭列表中放弃一个节点，然后在其上添加重新访问的节点。

所以伪代码是这样的：

GeneralGraphSearch( v )
Prepare two empty lists: OPEN, CLOSED
Insert v with Coste(v) into OPEN
While forever
    If OPEN is empty, return failure
    while forever
       v = the node with the lowest cost in OPEN
       remove v from OPEN
       if v is not in CLOSED // v is not visited
        break 
       else if the new cost is cheaper than the cost of v in CLOSED
        remove v in CLOSED
        break
       end if
    end while
    If v is a goal, return success
    Insert v into CLOSED
    Expand v
    Insert all children of v with their costs into OPEN
end while
End

但是，当我查找维基百科时，似乎他们只是忽略了某个节点（如果该节点已处于关闭列表中）。

相反，它们处理已在打开列表中的节点。

他们的伪代码版本如下：

function A*(start, goal)
    // The set of nodes already evaluated.
    closedSet := {}
    // The set of currently discovered nodes that are not evaluated yet.
    // Initially, only the start node is known.
    openSet := {start}
    // For each node, which node it can most efficiently be reached from.
    // If a node can be reached from many nodes, cameFrom will eventually contain the
    // most efficient previous step.
    cameFrom := the empty map

    // For each node, the cost of getting from the start node to that node.
    gScore := map with default value of Infinity
    // The cost of going from start to start is zero.
    gScore[start] := 0 
    // For each node, the total cost of getting from the start node to the goal
    // by passing by that node. That value is partly known, partly heuristic.
    fScore := map with default value of Infinity
    // For the first node, that value is completely heuristic.
    fScore[start] := heuristic_cost_estimate(start, goal)

    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

function reconstruct_path(cameFrom, current)
    total_path := [current]
    while current in cameFrom.Keys:
        current := cameFrom[current]
        total_path.append(current)
    return total_path

那么哪种方法是正确的？

还是两者都一样？

Answer 1

编辑：实际上都是正确的，A *算法的正确公式

但是，仅当您的行为方式是可接受的但不一致时才使用教授算法，这取自namin的答案：

如果到任何重复状态的最佳路径始终是第一个遵循的路径，那么[维基百科的方法是最佳的]。如果启发式函数具有一致性（也称为单调性）属性，则此属性成立。如果对于n的每个节点n和每个后继n'，从n达到目标的估计成本不大于从n到n'的逐步成本加上达到目标的估计成本，则启发式函数是一致的从n。

和

如果仅允许使用启发式函数，则[您的处理器版本]是最佳的，也就是说，它永远不会高估达到目标的成本。

鉴于您的启发式操作类似于欧几里德空间中的欧几里德距离（因此是一致且可容许的），因此您不应在封闭集中添加不是该节点的最小成本值的任何内容。以这种方式考虑，如果任意节点的成本可以无效化而小于封闭集中的成本，则将导致必须重新评估所有其他依赖路径步骤，并且会破坏该算法的运行时复杂性。

在这些情况下，Wikipedia是正确的，这全是您甚至将开放设置为优先队列的全部原因。理想情况下，您需要将开放集设为PQ，将封闭集设为列表，列表的顺序与您必须首先执行的步骤有关。

实际上，您需要修改开放集中的路径成本的想法意味着您需要一个具有删除权限的优先级队列，这可以在日志时间通过将hash-table-index-into到二进制堆结构/配对堆/ Fibonacci堆等中来实现（如何做到这一点的答案在其他地方找到）。这实际上成为IMO算法实现中最困难的部分，因为仅遵循该算法实际上并不会向您展示如何完成此操作，并且会使您难以确定伪实现中缺少的部分。

您会注意到，其他实现将讨论删除键/更新键操作，这些操作在封闭集中没有意义，仅在基于优先级队列的开放集中有意义。