Branching factor - Revision history

Karl Jones: /* Higher branching factors */

2016-04-25T20:30:44Z

‎Higher branching factors

Karl Jones: /* External links */

2016-04-22T01:17:17Z

‎External links

Karl Jones: /* See also */

2016-02-07T23:05:00Z

‎See also

Karl Jones at 23:04, 7 February 2016

2016-02-07T23:04:47Z

Karl Jones: Created page with "In computing, tree data structures, and game theory, the '''branching factor''' is the number of children at each node, the outdegree. If th..."

2016-02-07T22:59:46Z

Created page with "In computing, tree data structures, and game theory, the '''branching factor''' is the number of children at each node, the outdegree. If th..."

New page

In [[computing]], [[Tree (data structure)|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.

== Example ==

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.

By comparison, the branching factor for the game [[Go]] is 250.

== Higher branching factors ==

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]].

== See also ==

* [[Computing]]
* [[Game theory]]
* [[Pruning algorithm]]
* [[Tree (data structure)]]

== External links ==

* [https://en.wikipedia.org/wiki/Branching_factor Branching factor]

← Older revision		Revision as of 01:17, 22 April 2016
Line 29:		Line 29:

	* [https://en.wikipedia.org/wiki/Branching_factor Branching factor]		* [https://en.wikipedia.org/wiki/Branching_factor Branching factor]
		+
		+	[[Category:Computation]]
		+	[[Category:Computing]]

@@ Line 15: / Line 15: @@
 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]].
+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.
 == See also ==

@@ Line 22: / Line 22: @@
 * [[Computing]]
 * [[Game theory]]
-* [[Node (computer science)
+* [[Node (computer science)]]
 * [[Pruning algorithm]]
 * [[Tree (data structure)]]

@@ Line 1: / Line 1: @@
-In [[computing]], [[Tree (data structure)|tree data structures]], and [[game theory]], the '''branching factor''' is the number of children at each node, the outdegree.
+In [[computing]], [[Tree (data structure)|tree data structures]], and [[game theory]], the '''branching factor''' is the number of children at each [[Node (computer science)|node]], the outdegree.
 If this value is not uniform, an average branching factor can be calculated.
@@ Line 13: / Line 13: @@
 == Higher branching factors ==
-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.
+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]].
@@ Line 19: / Line 19: @@
 == See also ==
 * [[Computing]]
 * [[Game theory]]
 * [[Pruning algorithm]]
 * [[Tree (data structure)]]