2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

Search tree

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.

Dead-end

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.

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.

$\endgroup$
  • $\begingroup$ Solving the formula for $B$, you get $B \approx 2.165$. I wonder what the interpretation of that value is. It's close to the average branching factor of all inner nodes, but not the same. $\endgroup$ – Raphael Aug 2 '12 at 6:50
  • 1
    $\begingroup$ @MAcad In fact, what you are interested in, is not the branching factor, but the effective branching factor which is away to characterize the quality of a heuristic. I'll update my answer. $\endgroup$ – Juho Aug 2 '12 at 9:42
  • $\begingroup$ @Juho I think If I use Branching factor formula I will test many numbers in the LHS and calculate it and check equal with RHS as the following: B=1 ==> 1 + 1 + 1 ^ 2 + 1 ^ 3 = 4 not equal T = 17 so we need to test B=2 ==> 1 + 2 + 2 ^ 2 + 2 ^ 3 = 15 the result near from T so we can test B = 2.1 and so on until reach the result T !!!! I think this formula can use like this :)))) $\endgroup$ – MAcad Aug 3 '12 at 1:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.