Average branching factor of a problem

Posted on 2011-10-30
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?
Question by:humansg
    LVL 84

    Accepted Solution

    (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
    LVL 37

    Assisted Solution

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

    Author Comment

    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?
    LVL 37

    Expert Comment

    Yes. I just noticed that myself. Good catch.
    LVL 37

    Expert Comment

    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).

    Featured Post

    Looking for New Ways to Advertise?

    Engage with tech pros in our community with native advertising, as a Vendor Expert, and more.

    Join & Write a Comment

    This algorithm (in C#) will resize any image down to a given size while maintaining the original aspect ratio. The maximum width and max height are both optional but if neither are given, the original image is returned. This example is designed t…
    Article by: Nadia
    Suppose you use Uber application as a rider and you request a ride to go from one place to another. Your driver just arrived at the parking lot of your place. The only thing you know about the ride is the license plate number. How do you find your U…
    It is a freely distributed piece of software for such tasks as photo retouching, image composition and image authoring. It works on many operating systems, in many languages.
    how to add IIS SMTP to handle application/Scanner relays into office 365.

    729 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

    Need Help in Real-Time?

    Connect with top rated Experts

    19 Experts available now in Live!

    Get 1:1 Help Now