Iterative Weakening: Optimal and Near-Optimal Policies for the Selection of Search Bias

Decisions made in setting up and running search programs bias the searches that they perform.  Search bias refers to the definition of a search space and the definition of the program that navigates the space.  This paper addresses the problem of using knowledge regarding the complexity of various syntactic search biases to form a policy for selecting bias.  In particular, this paper shows that a simple policy, iterative weakening, is optimal or nearly optimal in cases where the biases can be ordered by computational complexity and certain relationships hold between the complexity of the various biases.  The results are obtained by viewing bias selection as a (higher-level) search problem.  Iterative weakening evaluates the states in order of increasing complexity.  An offshoot of this work is the formation of a near-optimal policy for selecting both breadth and depth bounds for depth-fist search with very large (possibly unbounded) breadth and depth.