![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/6/66/Red-black_tree_example.svg/langzh-hant-640px-Red-black_tree_example.svg.png&w=640&q=50)
分支因子
維基百科,自由的 encyclopedia
在電腦運算、樹數據結構、博弈論領域中,分支因子(英語:branching factor)是每個結點(英語:Node (computer science))下的子結點數,即出度。如果各個結點分支因子不同,則可以計算平均分支因子。
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/6/66/Red-black_tree_example.svg/640px-Red-black_tree_example.svg.png)
例如,在國際象棋中,如把一步合法走法算作一個「結點」,那麼平均分支因子據信約為35。[1][2]這表示,棋手每一步走棋平均有大約35種合法走法。相比之下,圍棋的分支因子為250。[1]
因結點數呈指數增長,所以分支因子越大,需要遍歷所有分支的算法(如暴力搜索法(英語:Brute-force search))的計算量越大。
例如,若分支因子為10,則當前位置下一層會有10個結點,下兩層會有102即100個結點,下三層會有103即1,000個結點,依此類推。分支因子越大,指數爆炸越快。剪枝算法(英語:Pruning (decision trees))可以減小分支因子。