IDA* 与 A* 算法的重点是什么

What is the point of IDA* vs A* algorithm

我不明白IDA*如何节省内存space。我怎么理解IDA*是A*迭代加深。

A* 使用的内存量与 IDA* 使用的内存量有何区别。

IDA* 的最后一次迭代会不会与 A* 完全一样并使用相同数量的内存。当我跟踪 IDA* 时，我意识到它还必须记住低于 f(n) 阈值的节点的优先级队列。

我知道 ID-深度优先搜索允许深度优先搜索像搜索一样进行广度优先搜索，而不必记住每个节点。但我认为 A* 已经表现得像深度优先，因为它忽略了沿途的一些子树。 Iteratively deepening如何让它占用更少的内存？

另一个问题是使用迭代加深的深度优先搜索允许您通过使其表现得像广度优先来找到最短路径。但是 A* 已经 returns 最佳最短路径（假设启发式是可以接受的）。迭代加深如何帮助它。我觉得 IDA* 的最后一次迭代与 A*.

相同

在IDA*中，与A*不同，您不需要保留一组您打算访问的暂定节点，因此，您的内存消耗仅用于局部变量递归函数。

虽然该算法对内存的消耗较低，但也有其自身的缺陷：

Unlike A*, IDA* doesn't utilize dynamic programming and therefore often ends up exploring the same nodes many times. (IDA* In Wiki)

为了不扫描整个图，仍然需要为您的情况指定启发式函数，但每个时刻扫描所需的内存只是您当前正在扫描的路径，没有其周围节点。

下面是每个算法所需内存的演示：

在 A* 算法中，所有节点及其周围的节点都需要包含在 "need to visit" 列表中，而在 IDA* 中，您将获得下一个节点 "lazily" 当您到达其预览节点时，您无需将其包含在额外的集合中。