algorithm - 人工智能 : Time Complexity of IDA* Search

Question

我在研究informed search算法，对于Iterative Deepening A* Search，我知道空间复杂度是O(d)，其中d是最浅目标节点的深度。我试图找出它的时间复杂度是多少，但我无法在在线资源上找到关于它的任何确切信息。 IDA* Search 的确切时间复杂度未知吗？任何见解都值得赞赏。

Answer 1

IDA 的时间复杂度*:在 IDA*，您不能笼统地说它是 O(b^d) 时间，仅此而已。时间复杂度不同于在二叉树或不平衡树或具有圆圈或无限图等的图中进行搜索。所以它首先取决于搜索环境。现在时间还取决于必须扩展多少节点，这取决于您将进行多少次迭代，这取决于您使用的启发式算法以及启发式函数将给出多少个不同的值。启发式给出的不同值越多，IDA* 将执行的迭代次数越多。检查伪代码可以看到，每次 f(n) 值大于迭代中的实际阈值时，它都会重新开始迭代。

在最坏的情况下，您必须进行所有可能的扩展和所有迭代，直到树的最深处。在二叉树或不平衡树中，这可能以不同的方式发生。

Richard E. Korf, Time complexity of iterative-deepening-A∗ (2001): “IDA∗ 的运行时间通常与扩展的节点数成正比。这取决于最佳解决方案的成本、暴力破解中的节点数量搜索树和启发式函数。”

IDA 的空间复杂度*:O(d) 空间不是正确的估计，即使对于 IDDFS 也是如此。两者的空间复杂度可以用相同的方式估算，因为它们使用深度优先搜索，众所周知，它需要的内存比 BFS 甚至 A* 少得多——事实上，这就是开发 IDA* 的原因。空间复杂度对于树来说是 O(bd)，因为你总是只存储算法在迭代中探索的实际路径，在最坏的情况下可能是树的“最深”点或者说底部那个树。在那之前，您必须存储所有已扩展的节点，即分支因子乘以树的“最深层次”= b*d。所以它是 O(bd)。

使用this来源，看看 IDA* 的创建者自己是如何进行估算的。

注意:@David Speck 之前的回答甚至不是针对 IDA*，而是针对迭代加深深度优先搜索 (IDDFS)。 IDA* 使用启发式来指导搜索，而 IDDFS 没有，IDDFS 是一种蛮力搜索技术，它们是不一样的。