BFS 的运行时间是 O(b^d)
b 是分支因子 d 是图从起始节点开始的深度(# of level)。
我在谷歌上搜索了一段时间,但我仍然没有看到有人提到他们是如何计算出这个“b”的
所以我知道分支因子是指“每个节点的子节点数”
例如,二叉树的分支因子是 2。
所以对于 BFS 图,b= 平均我们图中每个节点的所有分支因子。
或b = MAX(在每个节点的所有分支因子中)?
此外,无论我们选择 b 的哪种方式,在接近我们的运行时间时仍然显得模棱两可。 例如,如果我们的图有 30000 个节点,只有 5 个节点有 10000 个分支,其余所有 29955 个节点只有 10 个分支。我们将深度设置为 100。
似乎 O(b^d) 在这种情况下没有意义。
谁能解释一下。谢谢!
最佳答案
更常被引用的运行时间是 BFS 是 O(m + n),其中 m 是边的数量,n 是节点的数量。这是因为每个顶点被处理一次,每条边最多处理两次。
我认为 O(b^d) 在使用 BFS 时会用到,例如,暴力破解国际象棋游戏,其中每个位置都有相对恒定的分支因子,您的引擎需要深入搜索一定数量的位置。例如,国际象棋的 b 约为 35,而深蓝的搜索深度为 6-8(上升到 20)。
在这种情况下,因为图是相对无环的,b^d 与 m + n 大致相同(它们对于树来说是相等的)。 O(b^d) 更有用,因为 b 是固定的,d 是您可以控制的。
关于performance - 广度优先搜索分支因子,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15489329/