我在这里的书(人工智能现代方法)说统一成本搜索算法的最坏情况时间和空间复杂度为 O(b[C*/e]) ,其中 b 是分支因子,C* 是最优解的代价,每个 Action 至少花费 e。但为什么会这样呢?
最佳答案
首先,复杂度为 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))
关于algorithm - 统一成本搜索算法的最坏情况时间和空间复杂度是多少?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11967719/