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

Question

我正在读这本书 - 人工智能是一种现代的方法.我遇到了这句话,描述了统一成本搜索的时间复杂性

统一成本搜索以路径成本而非深度为指导,因此其复杂性不易用b和d表征.相反,让C成为最优解的成本,7并假设每个动作至少花费ε.然后算法的最坏情况时间和空间复杂度为O(b ^(1 + C /ε)),其可以远大于bd.

至于我的理解,C是最优解的成本,每个动作至少花费ε,因此C /ε将是到达目的地的步数.但我不知道这种复杂性是如何产生的,谢谢.

Answer 1

如果分支因子为b,则每次展开节点时,都会遇到更多节点.因此,有

• 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开始并在结束时C /ε,所以你在距离上采取步骤

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

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

希望这可以帮助!

Answer 2

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

\n