• 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?
  • 3
2 Solutions
(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
It asked for the average branching so he is dividing the whole equation by the number of nodes. (-1 for the starting node)
humansgAuthor 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?
Yes. I just noticed that myself. Good catch.
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).
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.

Join & Write a Comment

Featured Post

Get your problem seen by more experts

Be seen. Boost your question’s priority for more expert views and faster solutions

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