我的书（人工智能现代方法）中提到，均匀成本搜索算法的最坏情况时间和空间复杂度为O(b[C*/e])，其中b是分支因子，C*是最优解的成本，每个动作的成本至少为e。但为什么会这样呢？

回答：

首先，复杂度是O(B^(C/e)) [在C/e上是指数级的]。

为了理解这一点，首先考虑一个简单的例子：

设G=(V,E)为一个图，其分支因子为B。该图是无权重的（每个e的w(e) = 1）。

考虑从S到T寻找最短路径。
在这种情况下，算法实际上是BFS，它将发现路径上长度至SOL的所有节点，其中SOL是最短路径的长度，即O(B^|SOL|)

对于一般情况 – 同样的想法适用，你需要发现成本至C的所有节点。因此，你需要发现深度至C/e的节点，这给你O(B^(C/e))总共需要探索的节点数。

指数因子是因为：第一级（根）有B^0=1个节点，第二级有B个节点。从这些节点中你发现B个节点，给你B^2，依此类推…

编辑：
之前遗漏了，标题询问的是空间复杂度而不是时间复杂度。然而，答案仍然相同，因为均匀成本搜索会保持一个visited集合，用于已访问的节点。由于你发现的每个节点也被添加到其中 – 答案仍然是O(B^(C/e))