广度优先搜索生成的节点数是多少？

2 回答

• 0

  根据您使用的算法的变体，通过广度优先搜索生成的节点数存在差异 .

  如果在选择进行扩展（从打开的列表/队列中弹出）时将目标测试应用于每个节点，那么生成的节点数将是（在最坏的情况下）：

  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) .

  回复于 2024-05-09T11:14:21+08:00
• 2

  我认为你指的是在生成节点时评估测试条件的情况;然后BFS以最小深度扩展"target"以下的所有节点，目标节点本身的子节点除外 . 如果目标位于深度 d ，最坏的情况是最后一个叶子未展开（因为它是目标）：

  1 + b + b^2 + ... + b*(b^d - 1) = 1 + b + b^2 + ... + b^(d+1) - b = (b^(d+2) - 1) / (b - 1)
  

  回复于 2024-05-09T11:14:21+08:00