分支因子
在电脑运算、树数据结构、博弈论领域中，分支因子（英語：branching factor）是每个结点下的子结点数，即出度。如果各个结点分支因子不同，则可以计算平均分支因子。
例如，在国际象棋中，如把一步合法走法算作一个“结点”，那么平均分支因子据信约为35。[1][2]这表示，棋手每一步走棋平均有大约35种合法走法。相比之下，围棋的分支因子为250。[1]
因结点数呈指数增长，所以分支因子越大，需要遍历所有分支的算法（如暴力搜索法）的计算量越大。
例如，若分支因子为10，则当前位置下一层会有10个结点，下两层会有102即100个结点，下三层会有103即1,000个结点，依此类推。分支因子越大，指数爆炸越快。剪枝算法可以减小分支因子。
参见
[编辑]参考文献
[编辑]- ^ 1.0 1.1 Levinovitz, Alan. The Mystery of Go, the Ancient Game That Computers Still Can’t Win. Wired. 12 May 2014 [2014-06-02]. （原始内容存档于2020-12-14）.
The rate at which possible positions increase is directly related to a game’s “branching factor,” or the average number of moves available on any given turn. Chess’s branching factor is 35. Go’s is 250. Games with high branching factors make classic search algorithms like minimax extremely costly.
- ^ Laramée, François Dominic. Chess Programming Part IV: Basic Search. GameDev.net. 6 August 2000 [2007-05-01]. （原始内容存档于2012-02-08）.