A*搜索算法可以在没有封闭列表的情况下实现吗？

Question

A*搜索算法通常使用开放列表和封闭列表（或其他数据结构）来实现。最近我在维基百科上读到一个仅使用开放列表的伪代码。

• 平时的实现中，关闭列表是否多余？如果是这样，为什么？

Answer 1

启发式函数具有一些可能为假或为真的属性，包括：可允许和一致。

如果算法将节点放入封闭列表中（将该节点的最后一次评估标记为最终评估），那么我们必须假设启发式是“一致的”。如果不是，我们可能会将节点放入封闭列表中，但仍可以以较低的成本到达。这可能会导致非最佳路径。 维基百科文章中提供的算法不会将节点放入封闭列表中，而是始终检查当前节点的邻居是否可以获得更好的评估，即使该邻居之前已在开放列表中。

伪代码

下面的文字解释了这一点：

备注：

在此伪代码中，如果一个节点通过一条路径到达，从 openSet 中删除，随后通过一条更便宜的路径到达，它将再次添加到

openSet

中。如果启发式函数可接受但不一致，这对于保证返回的路径是最佳的至关重要。如果启发式是一致的，当从 openSet 中删除一个节点时，到它的路径保证是最优的，因此如果再次到达该节点，测试

tentative_gScore < gScore[neighbor]

将始终失败。

您可以说条件

tentative_gScore < gScore[neighbor]

起到了封闭列表检查的作用，但在其应用中更通用，因为现在该算法也适用于非一致性启发式函数。