Artificial Intelligence Stack Exchange is a question and answer site for people interested in conceptual questions about life and challenges in a world where "cognitive" functions can be mimicked in purely digital environment. It only takes a minute to sign up.
Sign up to join this community
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.
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!
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!
