我刚开始学习人工智能，正在阅读Peter Norvig的书。我已经查看了这个问题广度优先搜索生成的节点数量是多少？。答案中提到，如果我们在选择节点进行扩展时对每个节点应用目标测试，那么节点数量为1 + b + b^2 + b^3 + … + b^d + (b^(d+1) – b)。但是，如果我的目标状态是最终深度的叶节点，那么在目标之后就没有深度了。那b^(d+1)该如何计算呢？例如，在最大深度为3的树中，如果我的目标位于深度3，那么当没有第4层时，如何计算b^(3+1)呢？请解答我的疑惑，提前感谢！

回答：

请注意，你链接的答案提到的是在最坏情况下生成的节点数量。

生成意味着并非所有这些节点都会被测试以查看它们是否是目标；它们只是被生成并存储，以便在目标尚未找到的情况下最终与目标进行比较。

最坏情况有两个重要的含义。试着想象广度优先搜索从左到右进行，然后向下一层，再从左到右，然后再向下，等等。在最坏情况下，我们假设无论目标位于哪个深度层d，目标都是最右边的节点。这意味着它左边的所有节点都会与目标节点进行比较，并且它们的任何后继/子节点也会被生成。

我知道你说在你的情况下，在深度层d以下没有节点，但说最坏情况的第二个含义是我们假设基本上存在无限多的深度层。

确实，对于你的情况，该方程并不完全正确，但这仅仅是因为你没有遇到最坏情况。在你的情况下，搜索过程确实不需要生成方程中最后的(b^(d+1) – b)个节点。

关于你使用的术语的最后一点说明：你问如果在深度层d = 3以下没有深度层，如何计算b^(d+1)（例如，b^(3+1)）。从数学上讲，计算这个术语仍然没有问题。即使在你的情况下没有第4层深度，我们仍然可以数学上计算术语b^(3+1)。在你的情况下这样做没有意义，因为它不正确，但我们仍然可以很好地计算这个术语。