分支因子

维基百科,自由的百科全书
跳到导航 跳到搜索
一棵分支因子为2的红黑树

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

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

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

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

参见[编辑]

参考文献[编辑]

  1. ^ 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]. 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. 
  2. ^ Laramée, François Dominic. Chess Programming Part IV: Basic Search. GameDev.net. 6 August 2000 [2007-05-01].