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?
(N-2)^2 is the number of non-edge squares on the map, (4N-8) is the number of edge squares, but (N^2-1) seems inconsistent with the rest of the formula
And yes, for the denominator I am assuming the start node is the only node that can not be the end node so it's the non-terminal (if I'm getting your nomenclature right).
0
Question has a verified solution.
Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.