人工智能：IDA* 搜索的时间复杂度
Artificial Intelligence: Time Complexity of IDA* Search
我正在研究知情搜索算法，对于迭代深化 A* 搜索，我知道 space 复杂度为 O(d)，其中 d 是最浅目标节点的深度。我试图找出它的时间复杂度是多少，但我无法在在线资源上找到关于它的任何确切信息。 IDA* Search 的确切时间复杂度未知吗？任何见解表示赞赏。
- 时间复杂度：O(b^d)
Space 复杂度：O(d)
b: 分支因子
- d: 第一解的深度
您可以找到时间复杂度 here 的证明和示例。
IDA 的时间复杂度*：在 IDA* 你不能笼统地说它是 O(b^d) 时间，仅此而已。时间复杂度不同于在二叉树或不平衡树或具有圆圈或无限图等的图中进行搜索。
所以它首先取决于搜索环境。现在时间还取决于必须扩展多少节点，这取决于您将进行多少次迭代，这取决于您使用的启发式算法以及启发式函数将给出多少个不同的值。启发式给出的不同值越多，IDA* 将执行的迭代次数越多。检查伪代码可以看到，每次 f(n) 值大于迭代中的实际阈值时，它都会重新开始迭代。
在最坏的情况下，您必须进行所有可能的扩展和所有迭代到树的最深处。这可能以不同的方式发生在二叉树或不平衡树中。
Richard E. Korf, Time complexity of iterative-deepening-A∗ (2001): 》 IDA∗的运行时间通常与扩展的节点数成正比。
这取决于最优解的成本，brute-force中的节点数
搜索树和启发式函数。"
Space IDA* 的复杂性：O(d) space 不是正确的估计，即使对于 IDDFS 也是如此。 Space 两者的复杂性可以用相同的方式估算，因为它们使用深度优先搜索，众所周知，它需要的内存比 BFS 甚至 A* 少得多——事实上，这就是开发 IDA* 的原因。 space 树的复杂度为 O(bd)，因为您始终只存储算法在迭代中探索的实际路径，在最坏的情况下可能是树的“最深”点或说树底。在那之前，您必须存储所有已扩展的节点，即分支因子乘以树的“最深层次”= b*d。所以它是 O(bd).
使用this源代码，看看IDA*的创建者自己是如何进行估算的。
注意：@David Speck 之前的回答甚至不是针对 IDA*，而是针对迭代深化 depth-first 搜索 (IDDFS)。 IDA* 使用启发式来指导 IDDFS 不使用的搜索，IDDFS 是一种 brute-force 搜索技术，它们是不一样的。
实际上，IDA* 的 space 复杂度不是 O(d)。在最坏的情况下，它就像一个简单的 DFS，它的 O(b*d) 为：
- b 分支因子和
- d你第一个解的深度
现在在最好的情况下，由于启发式可接受性和一致性，space 复杂度将是 O(b * C*/e) 和
- C* 您解决方案的成本
- e 是您的弧的最低成本
对于时间复杂度来说，就像A*和O(b^d)一样。
我正在研究知情搜索算法，对于迭代深化 A* 搜索，我知道 space 复杂度为 O(d)，其中 d 是最浅目标节点的深度。我试图找出它的时间复杂度是多少，但我无法在在线资源上找到关于它的任何确切信息。 IDA* Search 的确切时间复杂度未知吗？任何见解表示赞赏。
- 时间复杂度：O(b^d)
Space 复杂度：O(d)
b: 分支因子
- d: 第一解的深度
您可以找到时间复杂度 here 的证明和示例。
IDA 的时间复杂度*：在 IDA* 你不能笼统地说它是 O(b^d) 时间，仅此而已。时间复杂度不同于在二叉树或不平衡树或具有圆圈或无限图等的图中进行搜索。 所以它首先取决于搜索环境。现在时间还取决于必须扩展多少节点，这取决于您将进行多少次迭代，这取决于您使用的启发式算法以及启发式函数将给出多少个不同的值。启发式给出的不同值越多，IDA* 将执行的迭代次数越多。检查伪代码可以看到，每次 f(n) 值大于迭代中的实际阈值时，它都会重新开始迭代。
在最坏的情况下，您必须进行所有可能的扩展和所有迭代到树的最深处。这可能以不同的方式发生在二叉树或不平衡树中。
Richard E. Korf, Time complexity of iterative-deepening-A∗ (2001): 》 IDA∗的运行时间通常与扩展的节点数成正比。 这取决于最优解的成本，brute-force中的节点数 搜索树和启发式函数。"
Space IDA* 的复杂性：O(d) space 不是正确的估计，即使对于 IDDFS 也是如此。 Space 两者的复杂性可以用相同的方式估算，因为它们使用深度优先搜索，众所周知，它需要的内存比 BFS 甚至 A* 少得多——事实上，这就是开发 IDA* 的原因。 space 树的复杂度为 O(bd)，因为您始终只存储算法在迭代中探索的实际路径，在最坏的情况下可能是树的“最深”点或说树底。在那之前，您必须存储所有已扩展的节点，即分支因子乘以树的“最深层次”= b*d。所以它是 O(bd).
使用this源代码，看看IDA*的创建者自己是如何进行估算的。
注意：@David Speck 之前的回答甚至不是针对 IDA*，而是针对迭代深化 depth-first 搜索 (IDDFS)。 IDA* 使用启发式来指导 IDDFS 不使用的搜索，IDDFS 是一种 brute-force 搜索技术，它们是不一样的。
实际上，IDA* 的 space 复杂度不是 O(d)。在最坏的情况下，它就像一个简单的 DFS，它的 O(b*d) 为：
- b 分支因子和
- d你第一个解的深度
现在在最好的情况下，由于启发式可接受性和一致性，space 复杂度将是 O(b * C*/e) 和
- C* 您解决方案的成本
- e 是您的弧的最低成本
对于时间复杂度来说，就像A*和O(b^d)一样。