分支因子

在电脑运算、树数据结构、博弈论领域中，分支因子（英语：branching factor）是每个结点（英语：Node (computer science)）下的子结点数，即出度。如果各个结点分支因子不同，则可以计算平均分支因子。

例如，在国际象棋中，如把一步合法走法算作一个“结点”，那么平均分支因子据信约为35。^[1]^[2]这表示，棋手每一步走棋平均有大约35种合法走法。相比之下，围棋的分支因子为250。^[1]

因结点数呈指数增长，所以分支因子越大，需要遍历所有分支的算法（如暴力搜索法（英语：Brute-force search））的计算量越大。

例如，若分支因子为10，则当前位置下一层会有10个结点，下两层会有10²即100个结点，下三层会有10³即1,000个结点，依此类推。分支因子越大，指数爆炸越快。剪枝算法（英语：Pruning (decision trees)）可以减小分支因子。

参见