Average branching factor of a problem
Posted on 2011-10-30
I got a 15 by 15 sized map. It is a search problem where I have a start point and I need to find the end point. I am asked to find the average branching factor of this problem.
I have 4 operators, which means I can move North/South/East/West.
My friend told me this
"The first node has 4 paths, almost the rest of the nodes have 3 paths as one path is going backward, for the side it has 2 paths and the corner which has 1 path. Thus,
Branches/Non-terminal nodes= 4+3*(N-2)^2 + 2*(4N-8)+ 1*4 / (N^2-1)
Can anyone give a more detailed explaination on why (N-2)^2, (4N-8) and why need to divide by (N^2-1) at the end?