I would like to calculate the effective branching factor of a tree in order to assess the quality of my heuristic in A* search.

The post here offer a very good explanation of the formula : N 1=1 B∗ (B∗)^2 ⋯ (B∗)^d, presented in the AI: A Modern Approach (by Stuart Russell and Peter Norvig) book. Where, N is the number of nodes searched and the solution depth is d and "b* is the branching factor that a uniform tree of depth d would have to have in order to contain N 1 nodes"

I am really puzzled with the example presented in the book. They say:

For example, if A* finds a solution at depth 5 using 52 nodes, then the effective branching factor is 1.92.

How did they come up with this value? As explained here an approximation to this formula is given by B∗≈N^(1/d).

Using that formula with values in the example from the book I get 2.20 = 52 ^ (1/5), which is a bit far off the value presented in the book as a solution (which btw is not said to be an approximation).

So, my question is how did they come up with the value 1.92? What am I missing?

CodePudding user response：

The approximation of N 1 = 1 B∗ (B∗)^2 ⋯ (B∗)^d by the equation B∗ ≈ N^(1/d) is only accurate for larger values of B∗. The true formula is ((B∗)^(d 1) - 1) / (B∗ - 1) = N 1. When B∗ is not significantly larger than 1, the error of the approximation can be very high.

If you solve for B∗ in the equation 53 = ((B∗)^(d 1) - 1) / (B∗ - 1), for example using Newton's method or another numerical solver, the true value (to 6 s.f.) is B∗ ≈ 1.916729, or B∗ ≈ 1.92 in the textbook.