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

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

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

回答：

如果分支因子是b，每次你展开一个节点时，你会遇到k个更多的节点。因此，有

• 第0层有1个节点，
• 第1层有b个节点，
• 第2层有b²个节点，
• 第3层有b³个节点，
• …
• 第k层有b^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 / ε)})。

希望这对你有帮助！