To calculate the branching number, do I need leaf nodes?

 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.

Answered by Anil Jha

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, the number of edges going into a node is known as the in-degree of the corresponding node and the branching number of edges coming out of a node is known as the 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!



Your Answer

Interviews

Parent Categories