选择不展开节点还是不将其添加到A*中具有已探索的封闭集的队列中，这重要吗？(图形搜索)

Question

我现在正在EdX上上伯克利AI课程，我们正在学习A*搜索。我以前使用过A*图搜索，我实现了它，以便在向边缘/队列添加后继者时，如果后继者已经在边缘或已探索/封闭的集合中，则不会添加后继者。然而，班上的教授说，对于A*图搜索，我们应该将节点添加到边缘，如果我们将它们弹出，并且它们已经在探索的集合中，则跳过它们(即拒绝扩展它们，但仍然向边缘添加重复的节点)。

然而，它也有一个看起来像Dijkstra的部分，它确保后继者的g分数是最小的。

这都是假设我们使用的是一致的、最优的启发式。有没有人能帮我更好地理解实现这两种方法的后果，谢谢！

Answer 1

您正在讨论两种处理以前遇到的节点的方法

在第一种方法中，您从队列中弹出一个项目，将其添加到您的封闭集合中。执行此操作时，您必须将其后继者添加到队列中。如果后继者已经在队列中，那么您只需更新它的值(因此它是最小的)。这将需要至少n次查找操作(每个节点的后继操作一次)。每次一个节点已经在您的队列中时，您必须将它的值与新的值进行比较，并可能更新优先级。在最坏的情况下，您必须对队列执行n次查找、n次比较和n次更新操作。

在你的第二种方法(来自你的教授的方法)中，所有的后继者都被放入队列中，而不检查他们是否已经存在。在计算节点时，这将只需要n次插入。但是，您必须在每次弹出队列的节点时检查它是否已经在您的封闭集合中，然后才能探索它。对于添加到队列中的每个节点，这将需要一个查找操作(尽管不在队列中)。一个节点可以多次出现在队列中(而在第一种方法中，队列中只有一个副本)。

正如您所看到的，这两种方法的差异将取决于您使用的队列类型(例如fibonacci堆、二进制堆等)。以及相应操作的成本。如果更新操作代价很高，那么第二种方法会更快。第二种方法确实需要为队列提供更多的内存(因为它可以同时包含同一节点的多个副本)。队列将变得更大，这将对您在其上执行的操作产生影响。

您应该查看您使用的队列，并根据所需的操作和您的图形确定最佳方法。