Adaptive Optimization of Recursive Search Trees
Original Publication Date: 1988-Jun-01
Included in the Prior Art Database: 2005-Feb-15
A technique is described whereby adaptive searching is applied to recursively defined search trees, as used in artificial intelligence search algorithms, so as to minimize the average cost of a search. Discussed are ways of reordering recursive rules without changing the semantics, such that ordering takes place in the same ratio that determines the ordering of nonrecursive search trees. Adaptive optimization of recursive search trees establishes that when techniques are applied to recursively defined search trees, the nodes of the recursive tree should be ordered according to descending values of the ratio p/c, where p is the probability of the successful termination of the rule and c is the cost of application of the rule.