In computing, tree data structures, and game theory, the branching factor is the number of children at each node, the outdegree. 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. This means that, on average, a player has about 35 legal moves at his disposal at each turn.
Higher branching factors make algorithms that follow every branch at every node, such as exhaustive brute force searches, computationally more expensive due to the exponentially increasing number of nodes, leading to combinatorial explosion.
For example, if the branching factor is 10, then there will be 10 nodes one level down from the current position, 102 (or 100) nodes two levels down, 103 (or 1,000) nodes 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.
Famous quotes containing the words branching and/or factor:
“The moose will, perhaps, one day become extinct; but how naturally then, when it exists only as a fossil relic, and unseen as that, may the poet or sculptor invent a fabulous animal with similar branching and leafy horns ... to be the inhabitant of such a forest as this!”
—Henry David Thoreau (1817–1862)
“In his very rejection of art Walt Whitman is an artist. He tried to produce a certain effect by certain means and he succeeded.... He stands apart, and the chief value of his work is in its prophecy, not in its performance. He has begun a prelude to larger themes. He is the herald to a new era. As a man he is the precursor of a fresh type. He is a factor in the heroic and spiritual evolution of the human being. If Poetry has passed him by, Philosophy will take note of him.”
—Oscar Wilde (1854–1900)