假设：’d’ 是树的有限深度；’b’ 是分支因子；’g’ 是最浅的目标节点。
据我所知，最坏情况是目标节点位于树的最右下角节点。因此，总生成的节点数应该是 O(bg)，对吗？然而，我的老师告诉我这是错误的，因为最坏情况是除了以目标节点为根的子树外，所有的树都被探索了。他提到了一些关于 O(bd) – O(b(g-d)) 的事情…. 我不完全确定。
我不太明白他的意思，所以有人能告诉我哪个答案是正确的吗？
回答：
我建议你画一棵树，标记被探索的节点，并计算它们的数量。
如果你使用广度优先搜索，你的推理是正确的，因为你只会到达每个分支的深度 g（总共探索了 O(b**g) 个节点）。
如果你使用深度优先搜索，你老师的推理是正确的，因为除了包含目标的部分外，你会到达树的所有部分的深度 d（总共探索了 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)。
