algorithm - 深度优先搜索生成的节点总数是多少

Question

假设:“d”是树的有限深度； 'b' 是分支因子； 'g' 是最浅的目标节点。

据我所知，最坏的情况是目标节点位于树中最后一个右下节点。因此，假设生成的节点总数是 O(bg)，对吗？然而，我的导师告诉我这是错误的，因为最坏的情况是除了以目标节点为根的子树之外的所有树都被探索过。他提到了一些关于 O(bd) - O(b(g-d)) .... 我不太确定。

我不太明白他的意思，所以谁能告诉我哪个答案是正确的？

Answer 1

我建议画一棵树，标记探索的节点，并计算有多少个。

如果您使用广度优先搜索，您的推理是正确的，因为您只会达到每个分支的深度 g(总共探索了 O(b**g) 个节点)。

如果你使用深度优先搜索，你的老师的推理是正确的，因为除了目标 (O(b**d - b**(d-g) ) 探索的节点)。

目标是绿色圆圈。

探索了蓝色节点。

红色节点未被探索。

为了计算探索的数量，我们计算树中的总数，并去掉红色的。

深度=2=d

深度目标 = 1 = g

分支因子 = b = 3

请注意，我将树中的节点总数称为O(b**d)。严格来说，总数是 b**d + b**(d-1) + b**(d-2) + ... + 1，但这是 O( b**d).