分支因子
維基百科,自由的 encyclopedia
在电脑运算、树数据结构、博弈论领域中,分支因子(英語:branching factor)是每个结点(英语:Node (computer science))下的子结点数,即出度。如果各个结点分支因子不同,则可以计算平均分支因子。
例如,在国际象棋中,如把一步合法走法算作一个“结点”,那么平均分支因子据信约为35。[1][2]这表示,棋手每一步走棋平均有大约35种合法走法。相比之下,围棋的分支因子为250。[1]
因结点数呈指数增长,所以分支因子越大,需要遍历所有分支的算法(如暴力搜索法(英语:Brute-force search))的计算量越大。
例如,若分支因子为10,则当前位置下一层会有10个结点,下两层会有102即100个结点,下三层会有103即1,000个结点,依此类推。分支因子越大,指数爆炸越快。剪枝算法(英语:Pruning (decision trees))可以减小分支因子。