没有。根据我的书，由广度优先搜索生成的节点数是：
N(BFS) = b + b^2 + .... + b^d + ( b^(d+1) - b )其中b是分支因子，d是最浅节点的深度。但不应该只是b + b^2 + .... + b^d 吗？因为那，在我看来是没有的。节点直到目标的深度。那么为什么会有+ ( b^(d+1) - b )呢？
问问题
7494 次
2 回答
2
根据您使用的算法的变体，通过广度优先搜索生成的节点数量会有所不同。
如果在选择扩展时将目标测试应用于每个节点（从打开列表/队列中弹出），则生成节点的数量将是（在最坏的情况下）：
1 + b + b^2 + b^3 + ... + b^d + (b^(d+1) - b),
其中d是解深度，b是分支因子（任何节点的最大后继数）。
这是因为在实际选择目标节点进行扩展之前，您必须生成目标节点的兄弟节点的子节点。在最坏的情况下，目标节点将是打开列表中最后一个被选择进行扩展的节点。
但是，这个通用的图搜索算法有一个细微的调整，那就是目标测试是在生成每个节点时应用到每个节点，而不是在选择它进行扩展时。
因此，假设解决方案再次位于 depth d。同样，在最坏的情况下，它是在该级别生成的最后一个节点。那么生成的节点总数为：
1 + b + b^2 + b^3 + ... + b^d.
所以第一种情况下的空间复杂度是：
O(b^(d+1))，而第二种情况下：
O(b^d)。
于 2013-04-29T02:18:13.697 回答
0
我认为您所指的情况是在生成节点时评估测试条件；然后 BFS 以最小深度扩展“目标”下方的所有节点，目标节点本身的子节点除外。如果目标位于 depth d，最坏的情况是最后一片叶子没有展开（因为它是目标）：
1 + b + b^2 + ... + b*(b^d - 1) = 1 + b + b^2 + ... + b^(d+1) - b = (b^(d+2) - 1) / (b - 1)
于 2012-08-16T18:08:01.950 回答