algorithm - 统一成本搜索算法的最坏情况时间和空间复杂度是多少？

Question

我在这里的书(人工智能现代方法)说统一成本搜索算法的最坏情况时间和空间复杂度为 O(b[C*/e]) ，其中 b 是分支因子，C* 是最优解的代价，每个 Action 至少花费 e。但为什么会这样呢？

Answer 1

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

要理解它，先想一个简单的例子:

设 G=(V,E) 是一个图，分支因子为 B。该图未加权(每个 e 的 w(e) = 1)。

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

对于一般情况 - 同样的想法成立，您需要发现所有节点，直到花费 C。因此，您发现深度为 C/e 的节点，需要探索的节点总数为 O(B^(C/e)) .

指数因子是因为:第一层(根)有B^0=1个节点，第二层有B个节点。从每一个你发现 B 节点，给你 B^2, ....

---

编辑:
到目前为止没看懂，但标题要求的是空间复杂度而不是时间复杂度。然而，答案保持不变，因为统一成本搜索为已经访问过的节点保留了一个 visited 集。由于您发现的每个节点也被添加到它 - 答案仍然是 O(B^(C/e))