Expected Performance of m-Solution Backtracking

This paper derives upper bounds on the expected number of search tree nodes visited during an m-solution backtracking search, a search which terminates after some preselected number m problem solutions are found. The search behavior is assumed to have a general probabilistic structure. Our results are stated in terms of node expansion and contraction. A visited search tree node is said to be expanding if the mean number of its children visited by the search exceeds 1, and is contracting otherwise. We show that if every node expands, or if every node contracts, then the number of search tree nodes visited by a search has an upper bound which is linear in the depth of the tree, in the mean number of children a node has, and in the number of solutions sought. Bounds linear in the depth of the tree are derived for the case where the upper portion of the tree contracts while the lower portion expands. We derive linear bounds for some special cases of an expanding upper portion and contracting lower portion; however, in the general case we have exponentially complex bounds. While previous analyses of 1-solution backtracking have concluded that the expected performance is always linear in the tree depth, our model allows super-linear expected performance. By generalizing previous work in the expected behavior of backtracking, we are better able to identify classes of trees which can be searched in linear expected time.