The B* Tree Search Algorithm. A Best-First Proof Procedure
Abstract
In this paper we present a new algorithm for searching trees. The algorithm, which we have named B*, finds a proof that an arc at the root of a search tree is better than any other. It does this by attempting to find both the best arc at the root and the simplest proof, in best-first fashion. This strategy determines the order of node expansion. Any node that is expanded is assigned two values: an upper (or optimistic) bound and a lower (or pessimistic) bound. During the course of a search, these bounds at a node tend to converge, producing natural termination of the search. As long as all nodal bounds in a sub-tree are valid, B* will select the best arc at the root of that sub-tree. The B* method assigns a greater responsibility for guiding the search to the evaluation functions that compute the bounds than has been done before. In this way knowledge, rather than a set of arbitrary predefined limits can be used to terminate the search itself. It is interesting to note that the evaluation functions may, measure any properties of the domain, thus resulting in selecting the arc that leads to the greatest quantity of whatever is being measured.
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 1978
- Accession Number
- ADA059391
Entities
People
- Hans J. Berliner
Organizations
- Carnegie Mellon University