Expected performance of m-solution backtracking

This paper derives upper bounds on the expected number of search tree modes 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 visted 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.