假设:’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)
。