3

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

Wikipedia 上的伪代码http://en.wikipedia.org/wiki/A_star#Pseudocode用于 A* 似乎是另一种方式,如果它不在探索中,我们只将它添加到边缘/队列中/已经封闭了。但是,它也有一个看起来像 Dijkstra 的部分,它确保后继者的 g-score 是最小的。

这一切都假设我们使用的是一致的、最优的启发式。有人可以帮助我更好地了解以任何一种方式实施它的后果谢谢!

4

1 回答 1

3

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

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

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

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

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

于 2012-10-06T12:58:26.397 回答