?
Solved

Average branching factor of a problem

Posted on 2011-10-30
5
Medium Priority
?
962 Views
Last Modified: 2012-06-27
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
Comment
Question by:humansg
  • 3
5 Comments
 
LVL 85

Accepted Solution

by:
ozo earned 1000 total points
ID: 37053076
(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
 
LVL 37

Assisted Solution

by:TommySzalapski
TommySzalapski earned 1000 total points
ID: 37053190
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 Comment

by:humansg
ID: 37053283
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
 
LVL 37

Expert Comment

by:TommySzalapski
ID: 37053300
Yes. I just noticed that myself. Good catch.
0
 
LVL 37

Expert Comment

by:TommySzalapski
ID: 37053303
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

Featured Post

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

We are taking giant steps in technological advances in the field of wireless telephony. At just 10 years since the advent of smartphones, it is crucial to examine the benefits and disadvantages that have been report to us.
Lithium-ion batteries area cornerstone of today's portable electronic devices, and even though they are relied upon heavily, their chemistry and origin are not of common knowledge. This article is about a device on which every smartphone, laptop, an…
This is a video describing the growing solar energy use in Utah. This is a topic that greatly interests me and so I decided to produce a video about it.
Although Jacob Bernoulli (1654-1705) has been credited as the creator of "Binomial Distribution Table", Gottfried Leibniz (1646-1716) did his dissertation on the subject in 1666; Leibniz you may recall is the co-inventor of "Calculus" and beat Isaac…
Suggested Courses

864 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question