Example using Penetrance & Branching Factor in State-space Heuristic Search

Question

I need an example for how to calculate penetrance and branching factor of the search tree in in state-space heuristic search. The definitions are as following. Penetrance $P$ is defined by

$\qquad \displaystyle P = \frac{L}{T}$

and branching factor $B$ is defined by

$\qquad \displaystyle \frac{B}{(B-1)} \cdot (B^L – 1) = T$

where $L$ is the length of the path from the root to the solution and $T$ the total number of nodes expanded.

Answer 1

Consider the following search tree. Your heuristic search algorithm starts the search at the root node. Unexpanded nodes are marked gray.

For some reason, the heuristic is being guided towards the left-most subtree, when in fact the goal node is in the right-most subtree, marked with green.

Nodes that have been expanded are marked red. After the appealing left-most subtree turned out to be a dead-end, the heuristic is now luckily being guided directly towards the goal. From the situation of the previous figure, we'll expand a total of three new nodes before arriving at the goal.

From the figure above, the length of the path to the goal is $3$. There are $17$ expanded nodes. Therefore, the penetrance is $3/17 \approx 0.43$.

The branching factor is the maximum number of successors of any node. For example, the branching factor of a binary tree is $2$ since each node has at most two children. Likewise, in the above search tree the branching factor is $3$.

What you seem to be interested in is not the branching factor, but the effective branching factor $B^*$ which is a way to characterize the quality of a heuristic. If the total number of expanded nodes is $T$, and the length of the path to the goal is $L$ (this is more commonly known as depth), then $B^*$ is the branching factor that a uniform tree of depth $L$ would have in order to contain $T+1$ nodes. Therefore,

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

If you plug-in the values we obtained in search, that is, $T=17$ and $L=3$, you get $B^* \approx 2.165$. This is exactly the same value you get from using your equation; it's just merely a different representation for the same thing.

The effective branching factor can vary across instances, but is somewhat constant for hard enough problems. A well-designed heuristic would have a value of $B^*$ close to $1$, allowing fairly large problems to be solved reasonable cheaply.