分支因子

在電腦運算、樹資料結構、博弈論領域中，分支因子（英語：branching factor）是每個結點（英語：Node (computer science)）下的子結點數，即出度。如果各個結點分支因子不同，則可以計算平均分支因子。

例如，在西洋棋中，如把一步合法走法算作一個「結點」，那麼平均分支因子據信約為35。^[1]^[2]這表示，棋手每一步走棋平均有大約35種合法走法。相比之下，圍棋的分支因子為250。^[1]

因結點數呈指數增長，所以分支因子越大，需要遍歷所有分支的算法（如暴力搜索法（英語：Brute-force search））的計算量越大。

例如，若分支因子為10，則當前位置下一層會有10個結點，下兩層會有10²即100個結點，下三層會有10³即1,000個結點，依此類推。分支因子越大，指數爆炸越快。剪枝算法（英語：Pruning (decision trees)）可以減小分支因子。

參見