(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

Solved

Posted on 2011-10-30

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?

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?

5 Comments

Title | # Comments | Views | Activity |
---|---|---|---|

Does high color HSV saturation imply that it must originate from a coherent laser source? | 21 | 77 | |

Statistics & Data Sceicne | 2 | 62 | |

Group Data Frequency Distribution | 9 | 34 | |

Graph function | 4 | 40 |

how to add IIS SMTP to handle application/Scanner relays into office 365.

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

Connect with top rated Experts

**19** Experts available now in Live!