分支因子
在電腦運算、樹資料結構、博弈論領域中，分支因子（英語：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）.