重访 A* 算法：我必须检查开放列表还是封闭列表？
Re-visiting on A* algorithm : Do I have to check open list or closed list?
正在研究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
那么哪种方式是正确的？？
或者两者相同？
编辑：实际上两者都是对的，Correct formulation of the A* algorithm
但是，如果您的启发式仅可接受但不一致，则您只会使用教授算法，摘自 namin's 答案：
[Wikipedia's approach is optimal] if the optimal path to any repeated state is always the first to be followed. This property holds if the heuristic function has the property of consistency (also called monoticity). A heuristic function is consistent if, for every node n and every successor n' of n, the estimated cost of reaching the goal from n is no greater than the step cost of getting to n' from n plus the estimated cost of reaching the goal from n.
和
[Your proffessors version] is optimal if the heuristic function is merely admissible, that is, it never overestimates the cost to reach the goal.
鉴于你的启发式类似于欧氏距离 space（因此是一致的和可接受的），你不应该向封闭集中添加任何不是最小成本值的东西节点。以这种方式考虑，如果任何任意节点的成本可以无效为小于封闭集中的成本，它将导致必须重新评估所有其他依赖路径步骤，并且会破坏 运行 时间复杂度对于这个算法。
Wikipedia 在这些情况下是正确的，这也是您甚至首先将开放集设置为优先级队列的全部原因。理想情况下，您的开放集是一个 PQ，而您的封闭集是一个列表，该列表按照与您必须首先采取的步骤相关的某种顺序。
你需要修改开放集中路径成本的想法实际上意味着你需要一个带移除的优先级队列，这在日志时间中是可能的 hash-table-index-into binary heap structure/pairing heap/Fibonacci 堆等（有关如何完成此操作的答案可在别处找到）。这实际上成为 IMO 算法实现中最难的部分，因为仅遵循算法并不能实际告诉您如何完成此操作，并且会让您陷入困境，找出伪实现中缺少的部分。
你会注意到其他实现会谈论删除key/update键操作，这些在闭集中没有意义，只有基于优先级队列的开放集。
正在研究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
那么哪种方式是正确的？？
或者两者相同？
编辑：实际上两者都是对的，Correct formulation of the A* algorithm
但是，如果您的启发式仅可接受但不一致，则您只会使用教授算法，摘自 namin's 答案：
[Wikipedia's approach is optimal] if the optimal path to any repeated state is always the first to be followed. This property holds if the heuristic function has the property of consistency (also called monoticity). A heuristic function is consistent if, for every node n and every successor n' of n, the estimated cost of reaching the goal from n is no greater than the step cost of getting to n' from n plus the estimated cost of reaching the goal from n.
和
[Your proffessors version] is optimal if the heuristic function is merely admissible, that is, it never overestimates the cost to reach the goal.
鉴于你的启发式类似于欧氏距离 space（因此是一致的和可接受的），你不应该向封闭集中添加任何不是最小成本值的东西节点。以这种方式考虑，如果任何任意节点的成本可以无效为小于封闭集中的成本，它将导致必须重新评估所有其他依赖路径步骤，并且会破坏 运行 时间复杂度对于这个算法。
Wikipedia 在这些情况下是正确的，这也是您甚至首先将开放集设置为优先级队列的全部原因。理想情况下，您的开放集是一个 PQ，而您的封闭集是一个列表，该列表按照与您必须首先采取的步骤相关的某种顺序。
你需要修改开放集中路径成本的想法实际上意味着你需要一个带移除的优先级队列，这在日志时间中是可能的 hash-table-index-into binary heap structure/pairing heap/Fibonacci 堆等（有关如何完成此操作的答案可在别处找到）。这实际上成为 IMO 算法实现中最难的部分，因为仅遵循算法并不能实际告诉您如何完成此操作，并且会让您陷入困境，找出伪实现中缺少的部分。
你会注意到其他实现会谈论删除key/update键操作，这些在闭集中没有意义，只有基于优先级队列的开放集。