algorithm - 统一成本搜索的时间复杂度

Question

我正在阅读《人工智能：一种现代方法》一书。我遇到了这句话描述统一成本搜索的时间复杂度：

统一成本搜索由路径成本而不是深度指导，因此其复杂性不容易用 b 和 d 来表征。相反，让 C 为最优解的成本，并假设每个动作的成本至少为 ε。那么算法的最坏情况时间和空间复杂度为O(b^(1+C/ε))，可以远大于b^d。

据我了解，C 是最优解的成本，每个动作的成本至少为 ε，因此 C/ε 是到达目的地的步数。但我不知道复杂性是如何得出的。

Answer 1

如果分支因子为b，那么每次展开一个节点，就会遇到k个以上的节点。因此，有

• 0 级的 1 个节点，
• b 级别 1 的节点，
• b ²级的 2 个节点，
• b ³级的 3 个节点，
• ...
• b ^k层 k 的节点。

因此，我们假设在您达到 k 级后搜索停止。发生这种情况时，您将访问的节点总数将为

1 + b + b ² + ... + b ^k = (b ^k+1 - 1) / (b - 1)

该等式来自几何级数的总和。恰好是 b ^k+1 / (b - 1) = O(b ^k )，所以如果你的目标节点在第 k 层，那么你必须扩展 O(b ^k ) 个节点才能找到一个你想要的。

如果 C 是您的目标成本，并且每一步都使您 ε 更接近目标，则您需要采取的步数由 C / ε + 1 给出。+1 的原因是您从距离 0 开始并在距离 0 结束C / ε，因此您可以远距离迈步

0, ε, 2ε, 3ε, ..., (C / ε)ε

这里总共有 1 + C / ε 步。因此，有 1 + C / ε 层，因此您需要扩展的状态总数为 O(b ^{(1 + C / ε)} )。

希望这可以帮助！

Answer 2

templatetypedef 的回答有些不正确。+1 与起始深度为 0 无关。如果每一步成本至少为 ε > 0，最优解的成本为 C，则最优解的最大深度出现在 floor(C /ε)。但最坏情况下的时间/空间复杂度实际上是 O(b ^{(1+floor(C/ε)} )。+1 的出现是因为在 UCS 中，我们只在选择节点进行扩展时检查它是否是目标，并且不是在我们生成它时（这是为了确保最优性）。所以在最坏的情况下，我们可能会生成目标节点驻留级别之后的整个节点级别（这解释了+1）。相比之下，BFS 应用生成节点时的目标测试，因此没有对应的+1因子，这是他错过的一个非常重要的点。