Why is the effective branching factor used for measuring performance of a heuristic function?

Question

For search algorithms with heuristic functions, the performance of heuristic functions are measured by the effective branching factor ${b^*}$, which involves the total number of nodes expanded ${N}$ and the depth of the solution ${d}$.

I'm not able to find out how different values of ${d}$ affect the performance keeping the same ${N}$. Put another way, why not use just the ${N}$ as the performance measure instead of ${b^*}$?

Answer 1

I also walked into that trap the first few times. The difference is the following:

• $N$ is the number of expanded nodes
• $b^*$ is the effective branching factor
  • $b^*$ depends on the depth $d$ of the goal and the number of generated nodes, lets call that $M$
  • $b^*$ is the solution to $M+1=1+b^*+(b^*)^2+(b^*)^3+...+(b^*)^d$

So, you could argue that instead of comparing $b_1^*$ and $b_2^*$ of two algorithms, you can also directly compare $M_1$ and $M_2$, because $b_1^*>b_2^*\Leftrightarrow M_1>M_2$.

But you can imagine an algorithm $A_2$ that expands fewer nodes than $A_1$ (so $N_1>N_2$), but also different nodes so that it generates more nodes (so $M_1<M_2$). Since the cost is defined by the number of generated nodes, comparing $N$ might give the wrong result.

The effective branching factor is more general than the number of generated nodes, because you can average $b^*$ for one algorithm over many search problems, but averaging over the number of nodes (which might differ greatly) is not possible or rather nonsensical.

Answer 2

As you found $N$ is the number of nodes that are expanded. The cost of expansion of each node is equal to the number of children of that node. Hence, we use $b^*$ for each node. In other words, the total number of nodes that are involved in the expansion process is $N \times b^*$.