EFFICIENT SEARCHING TECHNIQUE
Original Publication Date: 1987-Jun-01
Included in the Prior Art Database: 2005-Feb-01
This invention describes a means for looking ahead in a search to plan the order for visiting subsequent nodes in the search in a way that tends to reduce the total overall search effort. In certain Artificial Intelligence applications and in certain other programs, a program traverses a search tree looking for solutions to subproblems that have arisen in the course of the computation. For example, some Artificial Intelligence programs contain a theorem prover that attempts to construct a proof of conjectures produced by the program during a computation. To construct such a proof, the theorem prover searches a tree of possible logical inferences. The invention is a method for conducting such a search so as to substantially reduce the number of nodes visited during the search.