• Status: Solved
• Priority: Medium
• Security: Public
• Views: 1093
• Last Modified:

# Average branching factor of a problem

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?
0
humansg
Asked:
• 3
2 Solutions

Commented:
(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
0

Commented:
It asked for the average branching so he is dividing the whole equation by the number of nodes. (-1 for the starting node)
0

Author Commented:
ozo: thanks got it!

tommy: I thought it should be -1 due to non-terminal nodes or something?

4+3×((N-2)^2-1) + 2×(4N-8)+ 1×4 / (N^2- 1)

Do I need to minus one in here (N-2)^2?
0

Commented:
Yes. I just noticed that myself. Good catch.
0

Commented:
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.

Have a better answer? Share it in a comment.

## Featured Post

• 3
Tackle projects and never again get stuck behind a technical roadblock.