广度优先搜索分支因子

Question

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

B是分支因子d是从起始节点开始的图的深度(级别#)。

我用谷歌搜索了一段时间，但我仍然没有看到任何人提到他们是如何计算出这个"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，而Deep Blue的搜索深度为6-8 (最高可达20)。

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

Answer 2

在图O(b^d)中，图b=。因为这是最坏的情况。从普林斯顿http://www.princeton.edu/~achaney/tmve/wiki100k/docs/Breadth-first_search.html查看此链接-转到时间复杂性部分

Answer 3

引用斯图尔特·罗素和彼得·诺维格的《人工智能-现代方法》：

的时间和空间复杂度总是考虑到一定程度的问题难度。在理论计算机科学中，典型的度量是状态空间图的大小|V |+ |E|，其中V是图的顶点(节点)集合，E是边(链接)的集合。当图形是输入到搜索程序的显式数据结构时，这是合适的。(罗马尼亚的地图就是一个例子。)在AI中，图通常由初始状态、动作和转换模型隐式表示，并且经常是模糊的。由于这些原因，复杂性用三个量来表示: b，任何节点的分支因子或最大后继数；d，最浅目标节点的深度(即，沿着从根开始的路径的步数)；以及m，状态空间中任何路径的最大长度。时间通常是根据搜索期间生成的节点数量来衡量的，空间则是根据存储在内存中的最大节点数量来衡量的。在很大程度上，我们描述了在树上搜索的时间和空间复杂性；对于图，答案取决于状态空间中的路径有多“冗余”。

这应该会让您清楚地了解O(|V|+|E|)和b^d之间的区别