没有。根据我的书，广度优先搜索生成的节点数是:
N(BFS) = b + b^2 + .... + b^d + ( b^(d+1) - b ) 其中 b 是分支因子和d是最浅节点的深度。但它不应该只是 b + b^2 + .... + b^d 吗？因为根据我的说法，这是不行的。节点的数量直到目标的深度。那么为什么会有 + ( b^(d+1) - b ) ？
最佳答案
根据您使用的算法的变体，广度优先搜索生成的节点数量会有所不同。
如果在选择扩展(从打开列表/队列中弹出)时对每个节点应用目标测试，则生成的节点数量将是(在最坏的情况下):
1 + b + b^2 + b^3 + ... + b^d + (b^(d+1) - b),
其中d是解决方案深度，b是分支因子(任何节点的后继者的最大数量)。
这是因为在实际选择目标节点进行扩展之前，您必须生成目标节点同级节点的子节点。在最坏的情况下，目标节点将是开放列表中最后一个被选择进行扩展的节点。
但是，这种通用图搜索算法有一个细微的调整，即目标测试在生成每个节点时应用到每个节点，而不是选择它进行扩展时。
因此，假设解再次位于深度d。同样，在最坏的情况下，它是该级别生成的最后一个节点。那么生成的节点总数为:
1 + b + b^2 + b^3 + ... + b^d。
所以第一种情况的空间复杂度为:
O(b^(d+1)),
在第二种情况下:
O(b^d)。
关于algorithm - 广度优先搜索生成的节点数是多少？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11990358/