假设：'d'是树的有限深度; 'b'是一个分支因子; 'g'是最浅的目标节点 .
据我所知，最糟糕的情况是目标节点位于树中最后一个右下角节点 . 因此，据说生成的节点总数是O（bg），对吧？但是，我的导师告诉我这是错误的，因为最糟糕的情况是除了根据目标节点生成的子树之外，所有树都被探索 . 他提到了关于O（bd） - O（b（g-d））的一些事情....我不完全确定 .
我真的不明白他的意思，所以有人能告诉我哪个答案是正确的吗？
我建议绘制一棵树，标记探索的节点，并计算有多少 .
如果您使用广度优先搜索，那么您的推理是正确的，因为您只会为每个分支达到g的深度（总共探索了节点） .
如果您使用深度优先搜索，则教师的推理是正确的，因为除了具有目标的那个部分（探索了 O(b**d - b**(d-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) .
O(b**d)
b**d + b**(d-1) + b**(d-2) + ... + 1
1 回答
我建议绘制一棵树，标记探索的节点，并计算有多少 .
如果您使用广度优先搜索，那么您的推理是正确的，因为您只会为每个分支达到g的深度（总共探索了节点） .
如果您使用深度优先搜索，则教师的推理是正确的，因为除了具有目标的那个部分（探索了
O(b**d - b**(d-g))节点）之外，树的所有部分都达到了d的深度 .目标是绿色圈子 .
探索蓝色节点 .
没有探索红色节点 .
为了计算探索的数量，我们计算树中的总数，并取走红色的数量 .
深度= 2 = d
深度目标= 1 = g
分支因子= b = 3
请注意，我已调用树中的节点总数
O(b**d). 严格来说，总数是b**d + b**(d-1) + b**(d-2) + ... + 1，但这是O(b**d).