5
$\begingroup$

In the search tree below, there are 11 nodes, 5 of which are leaves. There are 10 branches.

Is the average branching factor given by 10/6, or 10/11?

Are leaves included in the calculation? Intuitively, I would think not, since we are interested in nodes with branches. However, a definition given to me by my professor was "The average number of branches of all nodes in the tree", which would imply leaves are included.

Search tree

$\endgroup$
  • $\begingroup$ Great question. I've taken the liberty of adding the "ai-basics" tag. Welcome to Stack:AI! $\endgroup$ – DukeZhou Apr 4 '18 at 19:24
1
$\begingroup$

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.

Outdegree meaning - In case of directed graphs, number of edges going into a node is known as in-degree of the corresponding node and number of edges coming out of a node is known as out-degree of the corresponding node.

You forgot the outdegree part. In AI we generally draw directed graphs from one state to another, and outdegree is the number of paths leaving a particular node. In your graph direction is not given. Also your graph is not symmetrical, but you can still find out the branching factor (with a little difficulty) of non-symmetrical directed graphs as given here. So technically your conclusion is correct about leaf nodes not being counted (assuming they are the last state from which no other state can be reached - dead end). Hope this helps!

$\endgroup$
0
$\begingroup$

I'd say that the leaves per se count, too, but only if they're real leaves, like e.g., checkmate positions in chess.

Such a node has really no children and no further calculation is needed. Unlike with nodes which weren't expanded yet.

Note that always counting the leaves provably leads to (n-1)/n for every n-node thee!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.