Menu
A particular search tree has 6 nodes at level 3. At the next level, there are 24 nodes. What is the branching factor at level 3?
The answer is 4, but can someone tell me why, I thought that it was 2.
321
We say that a binary tree has a branching factor of 2. In a binary tree, the children are usually ordered, so B is the left child and root of the left subtree, and H is the right child and root of the right subtree. Nodes that have no children are called leaves. Each node in a tree has a height and a depth.
How does this differ from the effective branching factor of your program (average or typical number of moves that it searches from a position before pruning stops the search)? (Note, you can compute the effective branching factor by the formula b=x1/d where x is the total number of nodes searched and d is the search ...
We have found the first optimal solutions to a complete set of random instances of the Twenty-Four Puzzle, a problem with almost 1025 states. The branching fac- tor is 2. 3 68, and the optimal solutions average over 100 moves long.
The maximum branching factor is 3, and this happens when the agent is stationary. While stationary it can take the following 3 actions - fast, left, right.
From Wikipedia:
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.
You have 6 nodes at level 3, 24 nodes at level 4, so the average number of children per node at level 3 is 24/6=4.
96
On different types of trees the branching factor can be either a static value throughout the tree, which only happens in perfect binary trees or an average branching factor which is most time the case for trees.
The branching factor is one characteristic of a node next to depth and gives a clue how complex a tree gets. For example, for the GO Game on a 19x19 board, the branching factor on the first level is 361, after 4 more moves at depth 4 you end up having 10 billion nodes. (possible moves)
Source: An Introduction To Artificial Intelligence, Janet Finlay
32
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
