3

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

4

3 回答 3

2

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

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

Richard E. Korf, Time complex of iterative-deepening-A∗ (2001)：“IDA∗ 的运行时间通常与扩展的节点数成正比。这取决于最优解的成本，即蛮力搜索树和启发式函数。”

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

使用此来源了解 IDA* 的创建者本人如何进行估算。

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

于 2020-09-13T13:12:11.100 回答
0
  • 时间复杂度：O(b^d)

  • 空间复杂度：O(d)

  • b：支化因子

  • d：第一个解决方案的深度

您可以在此处找到时间复杂度的证明和示例。

于 2019-02-03T22:41:47.910 回答
0

实际上，IDA* 的空间复杂度不是 O(d)。在最坏的情况下，它就像一个简单的 DFS，它的 O(b*d) 有：

  • b 分支因子和
  • d 你第一个解决方案的深度

现在在最好的情况下，由于启发式可接纳性和一致性，空间复杂度将为 O(b * C*/e)

  • C* 解决方案的成本
  • e 是你的弧的最低成本

对于时间复杂度，它就像 A* 与 O(b^d)。

于 2022-01-23T19:09:57.293 回答