什么是实现 A* 算法的正确方法？我们是否更新 closedSet 中的节点？

Question

正如我在 A* 算法（A-star 算法）中一样，我们将节点保存在两个列表中：一个优先级队列和一个常规数组。优先级队列叫openSet，另一个叫closedSet。

'openSet'包含我们要访问的节点，closedSet是我们已经访问过的节点。

下面是实现A*算法的伪代码：

openSet.add(startNode)
while not openSet.empty():
    currentNode = openSet.get()
  
    if currentNode == targetNode: # This is to stop searching when target is found
        break
    
    closedSet.add(currentNode)


    for neighborNode in currentNode.neighbors:
        if neighborNode not in openSet and not in closedSet:
            neighborNode.previousNode = currentNode   #building a path from currentNode to neighbor node
            neighborNode.g = currentNode.g + adjecentEdge.weight
            neighborNode.h = heuristic(neighborNode, targetNode)
            neighborNode.f = neighborNode.g + neighborNode.h
            openSet.add(neighborNode)
        else if neighborNode.g > currentNode.g + adjecentEdge.weight:
            neighborNode.previousNode = currentNode   #building a path from currentNode to neighbor node
            neighborNode.g = currentNode.g + adjecentEdge.weight
            neighborNode.h = heuristic(neighborNode, targetNode)
            neighborNode.f = neighborNode.g + neighborNode.h
                #Should I remove this part or not?
                if neighborNode in closedSet:
                    closedSet.remove(neighborNode)
                    openSet.add(neighborNode)


return getPath(startNode, targetNode)

在这段代码中，如果成本较低，我会更新节点，我更新它是否是 closedSet 中的节点，如果它是 closedSet 中的节点，我将其从 closedSet 中删除并将其添加到 openSet。

我们是否在 A* 算法中更新 closedSet 中的节点？[=12=]

我确实在 Python 中实现了两者，两者都找到了最短路径。

当我不更新 closedSet 中的节点时，它会在我的图表中更快地找到路径，但这可能只是巧合。

这是另一个根本不更新 closedSet 中的节点的伪代码：

下面是实现A*算法的伪代码：

openSet.add(startNode)
while not openSet.empty():
    currentNode = openSet.get()
  
    if currentNode == targetNode: # This is to stop searching when target is found
        break
    
    closedSet.add(currentNode)


    for neighborNode in currentNode.neighbors:
        if neighborNode not in openSet and not in closedSet:
            neighborNode.previousNode = currentNode   #building a path from currentNode to neighbor node
            neighborNode.g = currentNode.g + adjecentEdge.weight
            neighborNode.h = heuristic(neighborNode, targetNode)
            neighborNode.f = neighborNode.g + neighborNode.h
            openSet.add(neighborNode)
        else if neighborNode not in closedSet and neighborNode.g > currentNode.g + adjecentEdge.weight:
            neighborNode.previousNode = currentNode   #building a path from currentNode to neighbor node
            neighborNode.g = currentNode.g + adjecentEdge.weight
            neighborNode.h = heuristic(neighborNode, targetNode)
            neighborNode.f = neighborNode.g + neighborNode.h

return getPath(startNode, targetNode)

在实现 A* 算法时，我们是否更新 closedSet 中的节点？[=12=]

如果我们更新closedSet中的节点，我们是否将它们再次添加到openSet中？

Answer 1

如果启发式consistent, the nodes in the closed set will not need to be updated. If the heuristic is admissible但不一致，则封闭集中的节点可能需要更新。

大多数 现实世界的启发式算法是一致的，所以大多数时候 A* 被实现，算法的那部分是不必要的，为了速度，根本没有实现.

什么是实现 A* 算法的正确方法？我们是否更新 closedSet 中的节点？

What is correct way to implement A* algorithm? Do we update nodes in closedSet or not?

algorithm

graph

a-star