** Next:** Experimenting with MICRO-HILLARY
** Up:** MICRO-HILLARY
** Previous:** Using MICRO-HILLARY for a

A problem solver is *complete* if it terminates with a solution
when one exists [29, p. 75].
If, when starting from a solvable state, we never reach unsolvable
states, and if the range of the heuristic function is finite,
then a complete set of macros yields a complete problem solver.
Let *S* be a set of states and *O* a set of basic operators. Let
be a set of solvable problems with the
following
property:

Let *h* be a well-behaved heuristic function with a finite range, *R*_{h},
over S (
).
Let *M* be a complete set of macros. Then, SolveProblem using *M*
is a complete
problem solver with respect to *P*. Furthermore, the number of
operator applications is bounded by (|O|+*B*_{m}) *R*_{h} where *B*_{m} is the total
length of macros in *M*.

**Proof:**

In every step of the hill-climbing procedure we are guaranteed (by the
completeness of *M*) to find a state with a heuristic value which is
lower than the value of the current state. Since *h* is well-behaved,
and since it has a finite number of values, *R*_{h}, we can make at most
*R*_{h} steps before reaching a goal state with *h*(*s*)=0. At every
step, in the worst case, we try all the basic operators and all the
macros before finding the one that makes progress. Therefore the
total number of operator applications is bounded by (|O|+*B*_{m}) *R*_{h}.

** Next:** Experimenting with MICRO-HILLARY
** Up:** MICRO-HILLARY
** Previous:** Using MICRO-HILLARY for a
*Shaul Markovitch*

*1998-07-21*