Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

EFFICIENT SEARCHING TECHNIQUE

IP.com Disclosure Number: IPCOM000039433D
Original Publication Date: 1987-Jun-01
Included in the Prior Art Database: 2005-Feb-01
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

Stone, HS: AUTHOR [+2]

Abstract

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.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 54% of the total text.

Page 1 of 2

EFFICIENT SEARCHING TECHNIQUE

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. The invention is a rule that states the order in which to explore the possible choices that remain to be explored. The invention works in a general context and does not need to have information specific to the search itself.

This article contains an example of the use of the invention in which it reduced the amount of computation by a factor of 4,000 over the effort required by a lexicographic implementation of a search. The following assumptions are made about the search: 1. The search can be conducted in depth-first fashion. 2. The objective is to find any solution or to show that no solution exists. 3. Each search node is associated with some abstract object in the search. The search conducted at each search node corresponds to

selection of one value for the abstract object out of a set of

possible mutually exclusive choices. The choices can be explored

in any order. If after exploring all choices available at a search

node, no solution is discovered, then no solution exists for the

set of choices that have been made in order to reach that node in

the search tree. 4. After making an arbitrary choice at a search node, the search descends one level in the search tree, at which point the search

operates on a different abstract object, and must select the value

for that abstract object. 5. In case the search fails to find a satisfactory value for some abstract object, the search backtracks to the previous node in the

tree and selects a new value for the object at that node. The

search then continues.

(Image Omitted)

At a node in the search tree, the choices available for that node are called the sons of that node. The sequence in which abstract objects are examined in the search tree is called the expansion sequence. The invention gives a rule for deter...