Tree search

Hi to all,

you have a problem. Its search speace is modeled with a tree with
finite height. You have an evaluation function (heuristic) that says,
at every level i of the tree, if a node is better than another. The
heuristic is not perfect in the sense that it has some error. The
solutions is a path from the root to a node on the leaves that has some
property. Obviously, you don't heave enough information to decide
anything else: you must search.

I want to use A* (or best-first search) and study the aveage number of
nodes expandend before a solution is found.

How should i proceed? How should i specify the error the heuristic make
in order to simplify the analysis?

For example: the heuristic h is strictly monotonic, the tree is binary
and the problem is a minimization one.

I start to search with a b-f search. If, at level i, i make the wrong
decisions, i must search the whole sub-tree rooted at the son selected
before i can use the right node:

[i] level i
| \
| \
[1] [2] sons of level i

Since h([1]) < h([2]), than for every node n in the subtree rooted at
[1], h(n) < h([2]).

So, the "delay" is exponential....

I'am interested in the case that h is not strictly monotonic....

Any suggestion? Any paper? Any book?

Thank you,
Lucas

.