Expected performance of m-solution backtracking

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)114-127
Number of pages14
JournalSIAM Journal on Computing
Issue number1
StatePublished - 1988
Externally publishedYes

ASJC Scopus subject areas

  • General Computer Science
  • General Mathematics


Dive into the research topics of 'Expected performance of m-solution backtracking'. Together they form a unique fingerprint.

Cite this