广度优先搜索生成的节点数是多少？ [英] What is the number of nodes generated by breadth-first search?
问题描述
没有。根据我的书，广度优先搜索生成的节点数为：
N（BFS）= b + b ^ 2 + .... + b ^ d +（b ^（d +1）-b）其中， b 是分支因子， d 是最浅节点的深度。但是不应该只是 b + b ^ 2 + .... + b ^ d 吗？因为那对我来说是不。节点直到目标的深度。那么为什么会有 +（b ^（d + 1）-b）？
The no. of nodes generated by breadth-first search is, according to my book:
N(BFS) = b + b^2 + .... + b^d + ( b^(d+1) - b ) where b is the branching factor and d is the depth of the shallowest node. But should't it just be b + b^2 + .... + b^d ? because that, according to me is the no. of nodes till the depth of the goal. So why's there the + ( b^(d+1) - b )?
推荐答案
根据您使用的算法的变体，通过广度优先搜索生成的节点数量有所不同。
There is a difference in a number of generated nodes by breadth first search depending on the variant of the algorithm you use.
如果应用目标测试选择每个节点进行扩展时（从打开的列表/队列中弹出）到每个节点，则生成的节点数将是（在最坏的情况下）：
If you apply the goal test to each node when it is selected for expansion (popped out of the open list/queue) then number of generated nodes will be (in the worst case):
1 + b + b ^ 2 + b ^ 3 + ... + b ^ d +（b ^（d + 1）-b），
其中， d 是解的深度， b 是分支因子（最大数
where d is the solution depth, and b is the branching factor (maximum number of successor of any node).
这是因为在实际选择要扩展的目标节点之前，您将必须生成目标节点的兄弟节点的子节点。而且在最坏的情况下，目标节点将是打开列表中最后一个要进行扩展的对象。
This is because you will have to generate children of the goal node's siblings before you actually choose the goal node for expansion. And in the worst case, the goal node will be the last in the open list to be chosen for expansion.
但是，在此常规图形上有一个小的调整，搜索算法，即目标测试在生成时即应用于每个节点，而不是在选择进行扩展时应用。
But, there is one slight tweak on this general graph-search algorithm, which is that the goal test is applied to each node when it is generated rather than when it is selected for expansion.
因此，假设解决方案再次位于 d 的深度。同样，在最坏的情况下，它是在该级别生成的最后一个节点。那么生成的节点总数为：
So, suppose that the solution is again at the depth d. Again, in the worst case it is the last node generated at that level. Then the total number of nodes generated is:
1 + b + b ^ 2 + b ^ 3 + ... + b ^ d 。
因此，第一种情况下的空间复杂度为：
O（b ^（d + 1 ）），
，在第二种情况下：
O（b ^ d）。
So the space complexity in the first case is:
O(b^(d+1)),
and in the second case:
O(b^d).
这篇关于广度优先搜索生成的节点数是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
