In computing

Computing

Computing is usually defined as the activity of using and improving computer hardware and software. It is the computer-specific part of information technology...

, tree data structures, and game theory

Game theory

Game theory is a mathematical method for analyzing calculated circumstances, such as in games, where a person’s success is based upon the choices of others...

, the branching factor is the number of children at each node

Node (computer science)

A node is a record consisting of one or more fields that are links to other nodes, and a data field. The link and data fields are often implemented by pointers or references although it is also quite common for the data to be embedded directly in the node. Nodes are used to build linked, often...

. If this value is not uniform, an average branching factor can be calculated.

For example, in chess

Chess

Chess is a two-player board game played on a chessboard, a square-checkered board with 64 squares arranged in an eight-by-eight grid. It is one of the world's most popular games, played by millions of people worldwide at home, in clubs, online, by correspondence, and in tournaments.Each player...

, 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

Brute-force search

In computer science, brute-force search or exhaustive search, also known as generate and test, is a trivial but very general problem-solving technique that consists of systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem's...

, computationally more expensive due to the exponentially increasing

Exponential growth

Exponential growth occurs when the growth rate of a mathematical function is proportional to the function's current value...

 number of nodes, leading to combinatorial explosion

Combinatorial explosion

In administration and computing, a combinatorial explosion is the rapidly accelerating increase in lines of communication as organizations are added in a process...

.

For example, if the branching factor is 10, then there will be 10 nodes one level down from the current position, 10² (or 100) nodes two levels down, 10³ (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

Pruning (algorithm)

Pruning is a technique in machine learning that reduces the size of decision trees by removing sections of the tree that provide little power to classify instances...

 algorithm

Algorithm

In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

.