View source

In [[computing]], [[tree data structure]]s, and [[game theory]], the '''branching factor''' is the number of [[child node|children]] of each [[node (computer science)|node]]. If this value is not uniform, an '''average branching factor''' can be calculated.

For example, in [[Chess]], if a "node" is considered to be a legal position, the average branching factor has been said to be about 35.<ref>{{cite web | url=http://www.gamedev.net/reference/articles/article1171.asp | title=Chess Programming Part IV: Basic Search | author=François Dominic Laramée | publisher=[[GameDev.net]] | accessdate=2007-05-01}}</ref> This means that at each move, on average, a player has about 35 legal moves, and so, for each legal position (or "node") there are, on average, 35 positions that can follow (when a move is made).

An exhaustive [[brute-force search]] of the tree (i.e. by following every branch at every node) usually becomes computationally more expensive the higher the branching factor, due to the [[exponential growth|exponentially increasing]] number of nodes ([[combinatorial explosion]]). For example, if the branching factor is 10, then there will be 10 nodes one level from the current position, 10<sup>2</sup> = 100 nodes two levels down, 10<sup>3</sup> = 1000 three levels down, and so on. The higher the branching factor, the faster this "explosion" occurs. The branching factor can be cut down by a [[pruning (algorithm)|pruning]] algorithm.

== See also ==
* [[Hierarchy]]
* [[Hierarchical organization]]

== References ==
<references/>


[[nl:Vertakkingsfactor]]

{{Wiki}}