Solved

# 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?