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

Question

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

维基百科上的伪代码，http://en.wikipedia.org/wiki/A_star#Pseudocode ，因为 A* 似乎以另一种方式做到这一点，如果它不在探索/封闭集中，我们只将其添加到边缘/队列中。然而，它还有一个看起来像 Dijkstra 的部分，它确保继任者的 G 值最小。

这一切都假设我们使用一致的、最佳的启发式方法。有人可以帮助我更好地理解以任何一种方式实现它的后果吗？谢谢!

Answer 1

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

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

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

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

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