Cheap and Secure Web Hosting Provider : See Now

# [Solved]: Can the effective branching factor be negative?

, ,
Problem Detail:

I've implemented A* algorithm in Python, after that I calculated the effective branching factor \$ B^* \$

\$\$ T+1=1+B^*+(B^*)^2+\dots +(B^*)^L\$\$

where \$T\$ is the number of expanded nodes.

My question is: is it possible in theory that the effective branching factor calculated is negative? And if not possible, is the solution to take only positive root?

#### Answered By : Yuval Filmus

I don't know what effective branching factor is, but let me make a few comments anyway:

1. Presumably the effective branching factor is a parameter such that if the branching factor is constant, then it should equal the effective branching factor. It is some kind of average branching factor. Under this interpretation, a negative branching factor makes no sense.

2. You should focus on understanding what the effective branching factor is before calculating it. It is pointless to calculate something whose significance you don't understand. In real life you don't just "plug and chug" – you have a goal in mind. In this case, presumably the goal in mind is to estimate how difficult the problem is – the larger the effective branching factor is, the shallower you can afford to explore the corresponding tree. You estimate the effective branching factor in order to estimate how deep you can go, and in order to compare the difficulty of various problems. The formula itself is less important.

3. As \$B^*\$ increases monotonically from \$0\$ to infinity, so \$1+B^*+\cdots+(B^*)^L\$ increases from \$1\$ to infinity. Therefore your equation has a unique positive root (assuming \$T > 0\$).

4. If \$B^*\$ is "large", then you can estimate \$1+\cdots+(B^*)^L\$ by just the last term \$(B^*)^L\$, and so roughly speaking, \$B^* \approx T^{1/L}\$. You can use this estimate as a basis for an iterative algorithm for calculating \$B^*\$. The formula for the sum of a geometric series might be useful here.