search - A* 搜索是否多次扩展同一个节点？

Question

A* 搜索似乎重新计算了 Arad、Sibiu 和其他重复状态的 f 值，它不应该这样做，因为这些节点已经展开并处于关闭状态。那么我在这里错过了什么？（图片来自 Russel 和 Norvig - 人工智能。

图片：

在这种情况下，这些节点不会扩展，因为它们的 f 值大于最佳路径，如果不是这样怎么办？即，如果最近的 f 值返回到前一个节点怎么办？A*会这样做吗？

Answer 1

大多数 A* 算法回溯，这意味着一个节点只能被访问一次。否则，反向指针链被破坏，路径无法恢复。但是，如果对角线移动比方形移动更昂贵，您可能会遇到这样一种情况，即优先级队列中较低的节点可以访问成本更低的访问节点。通常你会忽略它并将访问的节点视为不可访问 - 除非你使用奇怪而奇妙的启发式或有一个非常奇怪的图形，否则它几乎不会对路径长度产生影响。