performance - 广度优先搜索分支因子

Question

BFS 的运行时间是 O(b^d)

b 是分支因子d 是图从起始节点开始的深度(# of level)。

我在谷歌上搜索了一段时间，但我仍然没有看到有人提到他们是如何计算出这个“b”的

所以我知道分支因子是指“每个节点的子节点数”

例如，二叉树的分支因子是 2。

所以对于 BFS 图，b= 平均我们图中每个节点的所有分支因子。

或b = MAX(在每个节点的所有分支因子中)？

此外，无论我们选择 b 的哪种方式，在接近我们的运行时间时仍然显得模棱两可。例如，如果我们的图有 30000 个节点，只有 5 个节点有 10000 个分支，其余所有 29955 个节点只有 10 个分支。我们将深度设置为 100。

似乎 O(b^d) 在这种情况下没有意义。

谁能解释一下。谢谢!

Answer 1

更常被引用的运行时间是 BFS 是 O(m + n)，其中 m 是边的数量，n 是节点的数量。这是因为每个顶点被处理一次，每条边最多处理两次。

我认为 O(b^d) 在使用 BFS 时会用到，例如，暴力破解国际象棋游戏，其中每个位置都有相对恒定的分支因子，您的引擎需要深入搜索一定数量的位置。例如，国际象棋的 b 约为 35，而深蓝的搜索深度为 6-8(上升到 20)。

在这种情况下，因为图是相对无环的，b^d 与 m + n 大致相同(它们对于树来说是相等的)。 O(b^d) 更有用，因为 b 是固定的，d 是您可以控制的。