IDA*算法与A*算法相比有何优劣之处？

Question

我不理解IDA*如何节省内存空间。 根据我的理解，IDA*是使用迭代加深的A*算法。

A*与IDA*在内存使用量上有什么区别。

难道IDA*的最后一次迭代行为不会像A*那样并且使用相同数量的内存吗？当我追踪IDA*时，我意识到它还必须记住所有低于f(n)阈值的节点的优先级队列。

我了解ID-深度优先搜索如何帮助深度优先搜索，使其能够进行类似广度优先的搜索而不必记住每个节点。但我认为A*已经像深度优先那样行为，即沿途忽略某些子树。迭代加深如何使其使用更少的内存？

另一个问题是，迭代加深的深度优先搜索允许您通过使其行为类似广度优先来找到最短路径。但是，A*已经返回最优最短路径了（假设启发式函数是可接受的）。迭代加深如何帮助它呢？我觉得IDA*的最后一次迭代与A*完全相同。

- tcui222

Answer 1

在IDA*算法中，与A*不同的是，你不需要保留一个意图访问的临时节点集合，因此，你只需要专注于递归函数的本地变量，因此内存消耗更低。

尽管该算法内存消耗较少，但它也有其缺陷:

与A*不同，IDA*不利用动态规划，因此经常会多次探索相同的节点。(IDA*在维基百科) 启发式函数仍然需要在您的情况下指定，以便不扫描整个图形，但每个时刻所需的扫描内存仅为当前扫描路径而不包括其周围的节点。

这是每种算法所需内存的演示:

在 A* 算法中，所有节点及其周围节点都需要包含在“需要访问”列表中，而在 IDA* 中，当到达其前一个节点时，“懒惰地”获取下一个节点，因此不需要将其包含在额外的集合中。

如评论中所述，IDA* 基本上只是带有启发式的 IDDFS：

- Tamir Vered

---

但是IDA仍然需要存储它打算访问的节点，因为它仍然会回溯，而当回溯时，它希望找到下一个最佳路径。A需要存储节点，IDA与A相同，但在达到一定f(n)后停止并重新启动。您是说IDA*只是具有启发式的IDDFS吗？也就是说，阈值以下的所有节点都被视为相等，并且访问节点的子节点没有特定顺序，只要所有子节点的f(n)都低于阈值？ - tcui222

IDA* 访问的每个节点都已经包含了它相邻节点的引用，因此当你在调用堆栈中有这个节点（上图中的黄色节点）时，你可以迭代它们。 - Tamir Vered

在A*算法中，当你沿着一条路径向下搜索时，你可能会发现另一个节点有更好的f(n)值，于是开始沿着另一条路径继续搜索。但是IDA*算法不会这样做，因为它不会将节点存储在优先队列中，除非f(n)值大于阈值，否则它会忽略f(n)值来选择下一个要搜索的子节点。 - tcui222

抱歉，我编辑了我的上一条评论，你能确认它是否正确吗？ - tcui222

让我们在聊天中继续这个讨论：http://chat.stackoverflow.com/rooms/91793/discussion-between-tcui222-and-tamir-vered。 - tcui222