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

Question

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

Answer 1

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

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

让我们G=(V,E)成为一个带有分支因子的图B。该图未加权（w(e) = 1对于每个e）。

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

对于一般情况 - 相同的想法成立，您需要发现所有节点到 cost C。因此，您可以发现深度节点C/e，从而为您O(B^(C/e))提供需要探索的总节点。

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

---

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

Answer 2

C*/e表示在搜索过程中应该访问的平均节点数，对于访问每个节点，您应该查看所有可能的b分支（至少是根节点），因此您应该在搜索中检查 b ^[C*/e]节点。这是您的搜索时间复杂度，这是通过假设每个节点上的过程需要 O(1)。

_{PS：最坏的情况是 Ω(b ^{[C*/e] )}}